Теперь, каково значение хеша в этом контексте, если для проверки уникальности (например, при построении набора) нам все равно нужно проверять каждый отдельный элемент в тех итерациях, которые есть в наборе в любом случае?
Да, но хеш используется для консервативной оценки, если два объекта могут быть равными, а также используется для присвоения "корзины" элементу. Если хеш-функция разработана тщательно, то вполне вероятно (не точно), что большинство, если не все, окажутся в другом сегменте, и в результате мы создадим алгоритмы membercheck / inserttion / removal / ... / ... работать в среднем в константе времени O (1) вместо O (n) , что типично для списков.
Таким образом, ваш первый ответ частично верен, хотя нужно учитывать, что сегменты, безусловно, также повышают производительность и на самом деле важнее, чем консервативная проверка.
Фон
Примечание : Я буду здесь использовать упрощенную модель, которая проясняет принцип, в действительности реализация словаря является более сложной. Например, хэши - это просто цифры, которые показывают принцип.
Хэш-набор и словарь реализованы в виде массива «сегментов». Хеш элемента определяет, в каком контейнере мы храним элемент. Если количество элементов увеличивается, то количество сегментов увеличивается, и элементы, уже находящиеся в словаре, обычно «переназначаются» в сегменты.
Например, пустой словарь может выглядеть, как внутри:
+---+
| |
| o----> NULL
| |
+---+
| |
| o----> NULL
| |
+---+
Итак, два блока, если мы добавим элемент 'a', тогда хеш будет 123. Давайте рассмотрим простой алгоритм для размещения элемента в сегменте, здесь есть два сегмента, поэтому мы назначим элементы с четным хешем для первого блока и нечетный хэш для второго блока. Поскольку хэш 'a' нечетен, мы присваиваем 'a' второму сегменту:
+---+
| |
| o----> NULL
| |
+---+
| | +---+---+
| o---->| o | o----> NULL
| | +-|-+---+
+---+ 'a'
Таким образом, это означает, что если мы теперь проверим, является ли 'b' членом словаря, мы сначала вычислим hash('b'), что составляет 456, и, таким образом, если бы мы добавили это в словарь, это было бы в первое ведро. Так как первое ведро пустое, нам никогда не нужно искать элементы во втором ведре, чтобы точно знать, что 'b' не является членом.
Если мы, например, захотим проверить, является ли 'c' членом, мы сначала сгенерируем хеш 'c', который равен 789, поэтому мы снова добавляем его во второй сегмент, например:
+---+
| |
| o----> NULL
| |
+---+
| | +---+---+ +---+---+
| o---->| o | o---->| o | o----> NULL
| | +-|-+---+ +-|-+---+
+---+ 'c' 'a'
Так что теперь, если мы снова проверим, является ли 'b' членом, мы обратимся к первому сегменту, и, опять же, нам никогда не придется перебирать 'c' и 'a', чтобы точно знать, что 'b' is not член словаря.
Теперь, конечно, можно утверждать, что если мы продолжим добавлять больше символов, таких как 'e' и 'g' (здесь мы считаем, что они имеют нечетный хэш), то этот бак будет достаточно полным, и, таким образом, если мы позже проверим если 'i' является членом, нам все равно придется перебирать элементы. Но в случае увеличения количества элементов, как правило, также увеличивается количество сегментов, и элементам в словаре назначается новый сегмент.
Например, если мы теперь хотим добавить 'd' в словарь, словарь может заметить, что количество элементов после вставки 3 больше количества сегментов 2, поэтому мы создаем новый массив ведер:
+---+
| |
| o----> NULL
| |
+---+
| |
| o----> NULL
| |
+---+
| |
| o----> NULL
| |
+---+
| |
| o----> NULL
| |
+---+
и мы переназначаем членов 'a' и 'c'. Теперь все элементы с хешем h с h % 4 == 0 будут назначены первому сегменту, h % 4 == 1 - второму сегменту, h % 4 == 2 - третьему сегменту и h % 4 == 3 - последнему сегменту. Это означает, что 'a' с хешем 123 будет сохранено в последнем контейнере, а 'c' с хешем 789 будет сохранено во втором сегменте, поэтому:
+---+
| |
| o----> NULL
| |
+---+
| | +---+---+
| o---->| o | o----> NULL
| | +-|-+---+
+---+ 'c'
| |
| o----> NULL
| |
+---+
| | +---+---+
| o---->| o | o----> NULL
| | +-|-+---+
+---+ 'a'
Затем мы добавляем 'b' с хешем 456 к первому сегменту, поэтому:
+---+
| | +---+---+
| o---->| o | o----> NULL
| | +-|-+---+
+---+ 'b'
| | +---+---+
| o---->| o | o----> NULL
| | +-|-+---+
+---+ 'c'
| |
| o----> NULL
| |
+---+
| | +---+---+
| o---->| o | o----> NULL
| | +-|-+---+
+---+ 'a'
Таким образом, если мы хотим проверить членство в 'a', мы вычисляем хеш, знаем, что если 'a' есть в словаре, мы должны искать в третьем сегменте и найти его там. Если мы ищем 'b' или 'c', то же самое происходит (но с другим сегментом), и если мы ищем 'd' (здесь с хешем 12), то мы будем искать в третьем сегменте и будем никогда не нужно проверять равенство с одним элементом, чтобы знать, что он не является частью словаря.
Если мы хотим проверить, является ли 'e' членом, то мы вычисляем хеш 'e' (здесь 345) и ищем во втором сегменте. Поскольку эта корзина не пуста, мы начинаем ее перебирать.
Для каждого элемента в корзине (здесь есть только один), алгоритм сначала будет искать, если ключ, который мы ищем, и ключ в узле ссылаются на один и тот же объект (однако два разных объекта могут быть равны), поскольку это не так, мы пока не можем утверждать, что 'e' есть в словаре.
Далее мы сравним хеш ключа, который мы ищем, и ключ узла. Большинство реализаций словаря (словари и наборы CPython, если я правильно помню), затем сохраняют хэш в узле списка. Таким образом, здесь проверяется, равен ли 345 789, поскольку это не так, мы знаем, что 'c' и 'e' не совпадают. Если сравнить два объекта было бы дорого, мы могли бы сэкономить несколько циклов.
Если хэши равны, это не означает, что элементы равны, поэтому в этом случае мы, таким образом, проверим, эквивалентны ли два объекта, если это так, мы знаем, что элемент находится в словаре иначе мы знаем, что это не так.