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

Re: Hash tables with O(1) worst-case lookup and space efficiency [pdf]

#41

Post by leif » Mon, Feb 21, 2011, 5:14 AM UTC

ithayer wrote: post #33

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?

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 efficiency [pdf]

#42

Post by jemfinch » Mon, Feb 21, 2011, 2:03 PM UTC

jules wrote: post #7

jemfinch wrote: post #6

Earlier quoted context omitted.

"Linear-time worst case" is different from "amortized constant time", which is what cuckoo hashing provides. Almost all the containers we use on a regular basis provide only amortized constant time inserts.

Linear time worst case and amortized constant time are not mutually exclusive. You are right that most containers that we use have amortized constant time complexity, but they also have linear worst case complexity. Most times this is because an internal array has to be resized and the contents have to be copied over to the new enlarged array.

No, they're not mutually exclusive. But what actually matters in most software is "amortized constant time": linear time worst case only matters in hard real-time systems which can't tolerate any deviation from the expected runtime.

Even algorithms like binary trees can end up with very bad worst cases unless great care is taken in allocating their nodes.

Re: Hash tables with O(1) worst-case lookup and space efficiency [pdf]

#43

Post by silentbicycle » Mon, Feb 21, 2011, 2:28 PM UTC

ot wrote: post #25

pmjordan wrote: post #19

Earlier quoted context omitted.

Chaining requires a memory allocation and list insertion on collisions - is it fair to call that absolute constant time? Probability of this happening depends on the number of elements in the container.

As silentbycicle said, list insertion at the head is constant time. About allocation, I agree with you that it is "slow", but all reasonable computation models count a memory allocation as a constant time operation. If we want to go down that road and measure also memory operations, even random memory access would not be worst-case constant time: the MMU has to map the page to the physical location, and this is usual…

Yeah, allocation is usually included in the constant factors. Keep them in mind, though - things like locality can have a big impact.

Re: Hash tables with O(1) worst-case lookup and space efficiency [pdf]

#44

Post by tripzilch » Mon, Feb 21, 2011, 6:11 PM UTC

sambeau wrote: post #2

"WHY ELSE IS THIS COOL?" seems a very casual heading for an academic article.

I dig--if you're going to use an informal expression and risk being completely dated within half a decade, why not pre-empt the retro wave with WHY ELSE IS THIS GROOVY?

Re: Hash tables with O(1) worst-case lookup and space efficiency [pdf]

#45

Post by tripzilch » Mon, Feb 21, 2011, 6:21 PM UTC

ithayer wrote: post #33

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?

> 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!