c++dictionaryhashmaphash-collision

Is there any possibility that std::unordered_map collides?

I seen a post in here that you could "meet with the Birthday problem." while using std::unordered_map

When should I use unordered_map and not std::map

Which really surprises me, that is the same that saying std::unordered_map is unsafe to use. Is that true? If i'm not explaining myself, let me show you an example:

unordered_map<size_t, size_t> m;
for (size_t i = 0; i < 100; ++i)
    m[i] = i;
for (size_t i = 0; i < 100; ++i)
    if (m[i] != i)
        cerr << "ERROR!" << endl;

If this code is in main, is there any possibility that it prints ERROR!?

Solution

  • Is there any possibility that std::unordered_map collides?

    It isn't the container that has collisions, but the hash function that you provide for the container.

    And yes, all hash functions - when their output range is smaller than the input domain - have collisions.

    is there any possibility that it prints ERROR!?

    No, it isn't possible. It's completely normal for the hash function to put multiple values into a single bucket. That will happen in case of hash collision, but it also happens with different hash values. The lookup function will get the correct value using linear search. The identity of a key is determined by the equality function, not by the hash function.