Re:Hash tables with O(1) worst-case lookup and space efficie...
by tripzilch on Monday February 21, 2011 @01:21PM
(#2246485)
> 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!
Re:Hash tables with O(1) worst-case lookup and space efficie...
by leif on Monday February 21, 2011 @12:14AM
(#2244352)
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.
Re:Hash tables with O(1) worst-case lookup and space efficie...
by pbewig on Sunday February 20, 2011 @07:55PM
(#2243740)
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.
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?