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: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.