A Lock-Free Hash Table (google video)

Dan murpsoft at hotmail.com
Mon Apr 2 09:35:18 PDT 2007


It seems to me that this is the only optimal form for hashtables - a massively scaleable one.  Why?

For cases where n < 8, a linear search is typically faster than any other search algorithm.  The reason is less overhead.

For cases where n < 1024, a level order binary search array is typically faster than any other search algorithm I've learned about, including a hashtable.  The reason is again less overhead.

For cases where n > 1024, I currently think that O(log(n)) in a level order binary search array is actually more expensive than that to manage a hashtable.

For cases where n > 1048576, the data set is getting quite large.  Assuming, through heuristics, that the number of gets and puts is also increasing, it becomes very practical to parallelize the hashtable.

My understanding is that we tend to organize data either very small or very large, rarely between 1024 and 1048576.  So implementing a hashtable, to me, suggests it ought to always be parallelizeable.  Especially considering the low overhead involved if it's done right.




More information about the Digitalmars-d mailing list