Hash tables with O(1) worst-case lookup and space efficiency [pdf] | Hacker News

Hash tables with O(1) worst-case lookup and space efficiency [pdf] | Hacker News

Mitzenmacher, the author of Probability and Computing, has an interesting survey on cookoo hashing. In it there are a number of open research problems that, for those of you with interest, a worth looking over. The 7th is very interesting to me, regarding optimal ways to maintain a hash table in a parallel computing environment. http://www.eecs.harvard.edu/~michaelm/postscripts/esa2009.pd... -----

ithayer 1611 days ago Every time I've tried comparing cuckoo hashing vs traditional hash algorithms in practice, the time taken to compute the additional hash functions outweighs any gains in performance. Counter-intuitively, I've also noticed in many cases that using binary search over sorted elements in contiguous memory is actually faster than using a hash table at all. Has anyone else found this? -----

tripzilch 1610 days ago > the time taken to compute the additional hash functions outweighs any gains in performance. Sounds like you're using the wrong hash functions. Are you using secure cryptographic hash functions perchance? (such as MD5, SHA, etc) Because they're not intended for use in data structures. Most data structure algorithms just require a hash function with good avalanche behaviour and a statistically even bit dispersion. The FNV hash will do this for you with just a MUL and a XOR per byte, which is (rough guess) at least 100 times faster than SHA. FNV hash (http://www.isthe.com/chongo/tech/comp/fnv/) it's super-effective! -----

leif 1610 days ago It very much depends on your hash table implementation, but I'm betting that your hash table is storing pointers to objects stored elsewhere. In this case, an array of elements in contiguous memory will be much faster because of locality. It's sometimes surprising how badly most of the data structures we think about treat caches. -----

pbewig 1611 days ago I almost always prefer some kind of balanced tree to a hash table, because no matter the original specifications, sometime during the development of a program I usually need the elements in order. -----

Read full article from Hash tables with O(1) worst-case lookup and space efficiency [pdf] | Hacker News