Для чего нужен KeyEqual в std::unordered_set?

Какова цель 3-го параметра KeyEqual в std::unordered_set? Разве хеш-уникальности недостаточно?

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

Извините, если этот вопрос звучит наивно. Переход на C++ из Python/PHP:)

На данный момент мои реализации KeyEqual всегда дублирует Hash осущ. Поэтому мне было интересно, правильно ли я это делаю.

Источник

4 ответа

Решение

Но что, если у нас будет коллизия хешей?

На рисунке показан случай, когда два разных элемента имеют одинаковые значения хеш-функции. В результате значение хеш-функции может быть не уникальным, когда дело доходит до хеширования.

Цитируя ссылку std::unordered_set:

Внутренне, элементы в unordered_set не сортируются в каком-либо определенном порядке, а организованы в сегменты в зависимости от их значений хеш-функции, чтобы обеспечить быстрый доступ к отдельным элементам непосредственно по их значениям (с постоянной средней сложностью по времени в среднем).

Таким образом, ведро может иметь более одного элемента! Эти два элемента будут иметь одинаковое хеш-значение, которое не обязательно будет уникальным!

Единственное, что гарантированно будет уникальным - это ключ!

Источник

Давайте возьмем для примера набор intс хэш-функцией, которая просто делает простой мод % операция

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);

Если мы добавим KeyEqual которая просто использует хеш-функцию (как вы предлагаете по умолчанию), она прерывается при второй вставке.

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
Источник

Разные значения не обязательно имеют разные хэши. Например, существует практически бесконечное количество std::string объекты, но только 2^N std::size_t объекты для результата std::hash<std::string>()(s)поэтому некоторые "коллизии хешей" неизбежны, хотя алгоритм пытается сделать их маловероятными.

Следовательно std::unordered_set а также std::unordered_map нужен способ проверить, являются ли элементы равными или неравными, даже если их значения хеш-функции равны.

Источник

Проще говоря, набор должен знать, равны ли два ключа. KeyEqual это механизм для этого.

Имейте в виду, что два ключа, которые не сравнивают равные, могут хэшироваться с одним и тем же значением, и набор должен иметь возможность проверить это.

Источник
Другие вопросы по тегам