mercredi 4 mai 2016

How does std::unordered_map handle collisions?

std::unordered_map guarantees O(1) time search, but how does it manage collision?

Cppreference claims

Unordered map is an associative container that contains key-value pairs with unique keys. Search, insertion, and removal of elements have average constant-time complexity.

Assuming a situation where all the Hash codes are same, how is the collision handled internally?

My assumption would be totally wrong if the hash code is unique to every key. In that case how is the unique hash code created where there are no collisions at all?

What approach does std::unordered_map's hash function take to guarantee O(1) search?

Aucun commentaire:

Enregistrer un commentaire