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

There are no comments on this comment yet.