What is KeyEqual in std :: unordered_set?

Question

What is the purpose of the third parameter KeyEqualin 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. Switching to C ++ from Python / PHP :)

Now my implementations KeyEqualalways duplicate Hashimpl. So I was wondering if I was doing it right.

Answer 1

But what if we have a hash collision?

The figure shows that two different elements have the same hash value. As a result, the hash value may not be unique when it comes to hashing.

---

Quoting ref std::unordered_set :

_ , , ( ).

, ! -, !

---

, - !

Answer 2

, , . KeyEqual - .

, , , , .

Answer 3

. , std::string, 2 ^ N std::size_t std::hash<std::string>()(s), "-" , .

std::unordered_set std::unordered_map , , .

Answer 4

, , int -, mod %

struct IntMod {
    constexpr std::size_t operator()(int i) const { return i % 10; }
};

std::unordered_set<int, IntMod> s;

, , , , .

s.insert(25);  // hash == 5
s.insert(35);  // hash == 5
assert(*s.find(25) == 25);  // both 25 and 35 are present despite the same hash
assert(*s.find(35) == 35);

If we add KeyEqualthat just uses a hash function (for example, you suggest doing it by default), it splits into the second insert.

struct IntEq {
  constexpr bool operator()(int a, int b) const {
    return IntMod{}(a) == IntMod{}(b);
  }
};

std::unordered_set<int, IntMod, IntEq> s;
s.insert(25);  // hash == 5
s.insert(35);  // hash == 5
assert(*s.find(25) == 25);
assert(*s.find(35) == 35);  // now this fails. s.find(35) returns iterator to 25