Почему ключи Dictionary должны соответствовать Hashable?

Question

Ключи должны быть Hashable, потому что словарь использует хеш-значение для быстрого поиска. Хеш позволяет быстро определить позицию элемента в таблице. Без хеша поиск был бы линейным и медленным. Также Hashable требует корректного сравнения на равенство. Это гарантирует корректную работу словаря.

YeaHub · Accepted Answer

Требование Hashable — фундаментальная часть контракта Dictionary.Что даёт HashableОпределение:Hashable — это протокол, который позволяет получить хеш-значение объекта и сравнивать его с другими.Он требует:реализацию hash(into:)корректную реализацию EquatableКак Hashable используется в DictionaryАлгоритм работы:вычисляется хеш ключапо хешу определяется бакетпри коллизии выполняется сравнение через ==Если два ключа равны (==):они обязаны иметь одинаковый хешОбратное не обязательно.Что будет без HashableБез хеша:нельзя быстро найти элементкаждая операция стала бы O(n)словарь теряет смыслПоэтому компилятор запрещает такие ключи.Практические требования к ключамХороший ключ:имеет стабильный хешне меняется после вставкикорректно реализует ==Изменяемые свойства в ключах — частая причина багов.ВыводHashable — это контракт, на котором держится производительность и корректность Dictionary. Без него словарь не мог бы работать эффективно.