4 ms·
Chaining requires a memory allocation and list insertion on collisions - is it fair to call that absolute constant time? Probability of this happening depends o
by pmjordan 16y ago
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.
- silentbicycle 16y agoPooling 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).
- ot 16y agoAs 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.
- silentbicycle 16y agoYeah, allocation is usually included in the constant factors. Keep them in mind, though - things like locality can have a big impact.