3 ms·
The linear time behavior of cuckoo hashing is not triggered only when the table has to be enlarged, like standard containers (say, std::vector or python list):
by ot 16y ago
The linear time behavior of cuckoo hashing is not triggered only when the table has to be enlarged, like standard containers (say, std::vector or python list): a linear numbers of keys can be "cuckooed" out of their slots for an insertion even when the load factor is under the capacity threshold.
In standard containers if you pre-define the capacity (say with std::vector::reserve) all the insertions are guaranteed to be constant time. Cuckoo hashing can't give this guarantee.
- pmjordan 16y agoI'm unaware of any hash table implementations which successfully insert elements in absolute constant time in the event of collisions.
- ot 16y agoChained hash tables have constant time insertion, but I'm not sure about the amortized lookup time (the worst case is linear)
- pmjordan 16y agoChaining 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.
- ckuehne 16y agoYou are kidding, right? The name chain itself suggest linear worst case behavior.
- ckuehne 16y agoWell, 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 http://en.wikipedia.org/wiki/Perfect_hash_function