What is the fastest free C hashtable implementation
scholz...@gmail.com
everything needs to be keept in a hashtable.
So i would need a highly optimized multithread safe hashtable.
David Schwartz
There is no "fastest" hash table. There are only relative advantages
and disadvantage.
For example, Larson's Algorithm is extremely helpful for hashes whose
size is not even approximately known at compile time. But it performs
very badly for hashes that rapidly oscillate between very large and
very small sizes. It also requires a power-of-two size, which is a
problem for data with poor distribution of the hash value but fine for
data with a random-like distribution of hash values.
Some algorithms have very fast modifications but compromise search
times. Some have extremely fast search times but are very slow to
modify.
And when you put thread safety into the mix, it comes down to what
kind of operations you see a lot of. For example, the implementation
for read-mostly hash tables will look nothing like one that's balanced
between reads and writes.
And there's always a trade-off between hash values that are easily
computed and hash values that provide very good distribution.
There is no substitute for studying the literature and finding what
best meets your particular requirements. You may need a 'bake off' to
see what hash best solves your particular mix of requirements.
DS
Chris M. Thomasson
news:6f7c8819-46a9-4bed...@w9g2000yqa.googlegroups.com...
> I'm going to experiment with a new scripting language where almost
> everything needs to be keept in a hashtable.
> So i would need a highly optimized multithread safe hashtable.
You can try converting this slick C++ implementation into C:
http://groups.google.com/group/lock-free/files
As for a ready made implementation in C, nothing comes to mind right off the
bat. Let me think. BTW, what type of accesses will be hitting the table more
frequently? Mostly reads?
James
nonblocking hashtable:
http://code.google.com/p/nbds/
BTW, it will be much faster if you can use a single thread version of
hashtable for general case, and inflate to a thread-safe version for
necessary case.
Chris M. Thomasson
> > I'm going to experiment with a new scripting language where almost
> > everything needs to be keept in a hashtable.
> > So i would need a highly optimized multithread safe hashtable.
> "James" <gan...@gmail.com> wrote in message
> news:c6117645-7e11-4f65...@a7g2000yqk.googlegroups.com...
> Following project provides a C implementation of Cliff Click's
> nonblocking hashtable:
> http://code.google.com/p/nbds/
> BTW, it will be much faster if you can use a single thread version of
> hashtable for general case, and inflate to a thread-safe version for
> necessary case.
I forgot about that one:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/702aedc141b34fa1
Wenwei Peng
> everything needs to be keept in a hashtable.
> So i would need a highly optimized multithread safe hashtable.
Author: pengwenwei
Email:
Language: c++
Platform: Windows, linux
Technology: Perfect hash algorithm
Level: Advanced
Description: Map algorithm with high performance
Section MFC c++ map stl
SubSection c++ algorithm
License: (GPLv3)
Download demo project - 1070 Kb
Download source - 1070 Kb
Introduction:
For the c++ program, map is used everywhere.And bottleneck of program performance is often the performance of map.Especially in the case of large data,and the business association closely and unable to realize the data distribution and parallel processing condition.So the performance of map becomes the key technology.
In the work experience with telecommunications industry and the information security industry, I was dealing with the big bottom data,especially the most complex information security industry data,all can’t do without map.
For example, IP table, MAC table, telephone number list, domain name resolution table, ID number table query, the Trojan horse virus characteristic code of cloud killing etc..
The map of STL library using binary chop, its has the worst performance.Google Hash map has the optimal performance and memory at present, but it has repeated collision probability.Now the big data rarely use a collision probability map,especially relating to fees, can’t be wrong.
Now I put my algorithms out here,there are three kinds of map,after the build is Hash map.We can test the comparison,my algorithm has the zero probability of collision,but its performance is also better than the hash algorithm, even its ordinary performance has no much difference with Google.
My algorithm is perfect hash algorithm,its key index and the principle of compression algorithm is out of the ordinary,the most important is a completely different structure,so the key index compression is fundamentally different.The most direct benefit for program is that for the original map need ten servers for solutions but now I only need one server.
Declare: the code can not be used for commercial purposes, if for commercial applications,you can contact me with QQ 75293192.
Download:
https://sourceforge.net/projects/pwwhashmap/files
Applications:
First,modern warfare can’t be without the mass of information query, if the query of enemy target information slows down a second, it could lead to the delaying fighter, leading to failure of the entire war. Information retrieval is inseparable from the map, if military products use pwwhashMap instead of the traditional map,you must be the winner.
Scond,the performance of the router determines the surfing speed, just replace open source router code map for pwwHashMap, its speed can increase ten times.
There are many tables to query and set in the router DHCP ptotocol,such as IP,Mac ,and all these are completed by map.But until now,all map are using STL liabrary,its performance is very low,and using the Hash map has error probability,so it can only use multi router packet dispersion treatment.If using pwwHashMap, you can save at least ten sets of equipment.
Third,Hadoop is recognized as the big data solutions at present,and its most fundamental thing is super heavy use of the map,instead of SQL and table.Hadoop assumes the huge amounts of data so that the data is completely unable to move, people must carry on the data analysis in the local.But as long as the open source Hadoop code of the map changes into pwwHashMap, the performance will increase hundredfold without any problems.
Background to this article that may be useful such as an introduction to the basic ideas presented:
http://blog.csdn.net/chixinmuzi/article/details/1727195