News for hackers. Stuff that matters.
Re:Hash tables with O(1) worst-case lookup and space efficie... by ot on Sunday February 20, 2011 @09:23AM (#2241893)
Cuckoo 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.
Re:Hash tables with O(1) worst-case lookup and space efficie... by arnoldoMuller on Sunday February 20, 2011 @11:31AM (#2242221)
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 efficie... by jemfinch on Sunday February 20, 2011 @09:43AM (#2241937)
"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.

Re:Hash tables with O(1) worst-case lookup and space efficie... by jules on Sunday February 20, 2011 @09:44AM (#2241941)
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.
Re:Hash tables with O(1) worst-case lookup and space efficie... by jemfinch on Monday February 21, 2011 @09:03AM (#2245407)
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 efficie... by ot on Sunday February 20, 2011 @10:51AM (#2242091)
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 efficie... by pmjordan on Sunday February 20, 2011 @12:08PM (#2242334)
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 efficie... by ot on Sunday February 20, 2011 @12:16PM (#2242348)
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 efficie... by pmjordan on Sunday February 20, 2011 @12:34PM (#2242396)
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 efficie... by silentbicycle on Sunday February 20, 2011 @01:07PM (#2242522)
Pooling memory for allocating links turns the allocation into amortized constant time.

List insertion is O(1) if you insert it at the head, and while moving the most-recently-accessed link to the head of the chain doesn't change the worst case behavior, it greatly improves the average in practice (and is dead easy).

Re:Hash tables with O(1) worst-case lookup and space efficie... by ot on Sunday February 20, 2011 @01:43PM (#2242640)
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 usually a logarithmic or amortized constant time operation.

Re:Hash tables with O(1) worst-case lookup and space efficie... by silentbicycle on Monday February 21, 2011 @09:28AM (#2245498)
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 efficie... by ckuehne on Sunday February 20, 2011 @12:43PM (#2242425)
You are kidding, right? The name chain itself suggest linear worst case behavior.
Re:Hash tables with O(1) worst-case lookup and space efficie... by s3graham on Sunday February 20, 2011 @04:10PM (#2243094)
"insertion".
Re:Hash tables with O(1) worst-case lookup and space efficie... by ckuehne on Sunday February 20, 2011 @05:54PM (#2243415)
My fault. Just saw constant time and chain in one sentence and panicked ;)
Re:Hash tables with O(1) worst-case lookup and space efficie... by ckuehne on Sunday February 20, 2011 @12:57PM (#2242486)
Well, there is perfect hashing [1]. Of course it does only work under several assumptions. And you pay for it in terms of time it takes to construct the hash function or in terms of space.

[1] http://en.wikipedia.org/wiki/Perfect_hash_function