I recently did an exercise on cuckoo hashing at http://programmingpraxis.com/2011/02/01/cuckoo-hashing/.
Hash tables with O(1) worst-case lookup and space efficiency [pdf]
11–20 of 45 posts
Re: Hash tables with O(1) worst-case lookup and space efficiency [pdf]
#12It's been my experience that the O(1) was on average, not worst case.
Cuckoo hashing has O(1) worst-case access time, and O(1) "average" (amortized, to be correct) insert time.
Re: Hash tables with O(1) worst-case lookup and space efficiency [pdf]
#13Cuckoo hashing is not only optimal in theory, it is also very fast in practice. The only downside, though, is that the insert time has linear-time worst case. Thus it may be not the best solution if latency is an issue.
"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.
The linear time behavior of cuckoo hashing is not triggered only when the table has to be enlarged, like standard containers (say, std::vector or python list): a linear numbers of keys can be "cuckooed" out of their slots for an insertion even when the load factor is under the capacity threshold.
In standard containers if you pre-define the capacity (say with std::vector::reserve) all the insertions are guaranteed to be constant time. Cuckoo hashing can't give this guarantee.
Re: Hash tables with O(1) worst-case lookup and space efficiency [pdf]
#14Re: Hash tables with O(1) worst-case lookup and space efficiency [pdf]
#15Cuckoo hashing is not only optimal in theory, it is also very fast in practice. The only downside, though, is that the insert time has linear-time worst case. Thus it may be not the best solution if latency is an issue.
There was a talk around where they were using two replacements at most(or two hash tables), and two hash functions. At insert time you add the object to the first hash table, if there is an object in the bucket, you then try with the second hash table. If you follow this approach a very large percentage of the buckets is going to be full. The remaining objects set (those that cannot be inserted in the first two hash tables because the buckets are full) is so small that you can keep them in a list or in a "standard" hash table. At some point I had a secondary storage implementation of this approach and it was good indeed.
Re: Hash tables with O(1) worst-case lookup and space efficiency [pdf]
#16Re: Hash tables with O(1) worst-case lookup and space efficiency [pdf]
#17Earlier 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.
The linear time behavior of cuckoo hashing is not triggered only when the table has to be enlarged, like standard containers (say, std::vector or python list): a linear numbers of keys can be "cuckooed" out of their slots for an insertion even when the load factor is under the capacity threshold. In standard containers if you pre-define the capacity (say with std::vector::reserve) all the insertions are guaranteed to…
I'm unaware of any hash table implementations which successfully insert elements in absolute constant time in the event of collisions.
Re: Hash tables with O(1) worst-case lookup and space efficiency [pdf]
#18Earlier quoted context omitted.
The linear time behavior of cuckoo hashing is not triggered only when the table has to be enlarged, like standard containers (say, std::vector or python list): a linear numbers of keys can be "cuckooed" out of their slots for an insertion even when the load factor is under the capacity threshold. In standard containers if you pre-define the capacity (say with std::vector::reserve) all the insertions are guaranteed to…
I'm unaware of any hash table implementations which successfully insert elements in absolute constant time in the event of collisions.
Chained hash tables have constant time insertion, but I'm not sure about the amortized lookup time (the worst case is linear)
Re: Hash tables with O(1) worst-case lookup and space efficiency [pdf]
#19Earlier quoted context omitted.
I'm unaware of any hash table implementations which successfully insert elements in absolute constant time in the event of collisions.
Chained hash tables have constant time insertion, but I'm not sure about the amortized lookup time (the worst case is linear)
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.
Re: Hash tables with O(1) worst-case lookup and space efficiency [pdf]
#20Earlier quoted context omitted.
I'm unaware of any hash table implementations which successfully insert elements in absolute constant time in the event of collisions.
Chained hash tables have constant time insertion, but I'm not sure about the amortized lookup time (the worst case is linear)
You are kidding, right? The name chain itself suggest linear worst case behavior.