News for hackers. Stuff that matters.
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