dimanche 28 juin 2015

c++ unordered_map collision handling , resize and rehash

I have not read the C++ standard but this is how I feel that the unordered_map of c++ suppose to work.

  • Allocate a memory block in the heap.
  • With every put request, hash the object and map it to a space in this memory
  • During this process handle collision handling via chaining or open addressing..

I am quite surprised that I could not find much about how the memory is handled by unordered_map. Is there a specific initial size of memory which unordered_map allocates. What happens if lets say we allocated 50 int memory and we ended up inserting 5000 integer?

This will be lot of collisions so I believe there should be kind of like a re-hashing and re-sizing algorithm to decrease the number of collisions after a certain level of collision threshold is reached. Since they are explicitly provided as member functions to the class, I assume they are used internally as well. Is there a such mechanism?

Aucun commentaire:

Enregistrer un commentaire