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.
[ Parent
| on HN ]
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.