[FIXED] How does std::unordered_map differentiate between values in the same bucket?

Issue

I know that std::unordered_map handles key hash collisions by chaining keys with the same hash in a bucket (I think using a linked list). The question I have is how does it know which value, in the same bucket, corresponds to which key?

The naive idea I have is that each value is stored in a std::pair, is this how it is done?

Solution

Yep, that's basically how it's done. Keep in mind that the key is part of the data. One of the things you can do with a map is iterate through its key/value pairs. This would be impossible, even with perfect hashing, if the key itself were not stored.

Answered By - Sneftel

Answer Checked By - Katrina (PHPFixing Volunteer)