Search code examples
c++stdunordered-set

What is KeyEqual in std::unordered_set for?

What is the purpose of 3rd parameter KeyEqual in std::unordered_set? Isn't hash uniqueness enough?

template<
    class Key,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator<Key>
> class unordered_set;

Sorry if this question sounds naive. Moving to C++ from Python/PHP :)

For now my implementations of KeyEqual always duplicates Hash impl. So I was wonder if I do it correctly.

Solution

  • But what if we have a hash collision?

    enter image description here

    The picture demonstrates the case where two different elements, happen to have equal hash values. As a result, the hash value may not be unique when it comes to hashing.

    Quoting the ref of std::unordered_set:

    Internally, the elements in the unordered_set are not sorted in any particular order, but organized into buckets depending on their hash values to allow for fast access to individual elements directly by their values (with a constant average time complexity on average).

    So a bucket can have more than one element! These two elements will have the same hash value, which is not guaranteed to be unique!

    The only thing that is guaranteed to be unique is the key!