Хэширование

Хэш - это результат обработки неких данных хеш-функцией. В рамках Python значение хэша это целое число.

Хэш функция - это правило по которому элементам одного множества (Область значения) однозначно сопоставляется элемент из другого множества (из области определения). Выражаясь математически это сюръективное отображение.
Хэширование - это процесс однозначного сопоставления элементам из области определения элементов из области значения. Сопоставление производится с помощью хэш-функции. Например отпечаток пальца - это хэш человека

Свойства хэширования:

  1. Хэш уникален. Каждому элементу из области определения соответствует только один элемент из области значения (хэш);
  2. Коллизии допустимы. Каждому хэшу может соответствовать несколько элементов из области определения, такие ситуации называются коллизиями, это связано с тем что хэш-функции не идеальны. Для разрешения коллизиев существуют специальные алгоритмы.
  3. При самом незначительном изменении данных хэш меняется кардинально.
  4. Хэш-функция не обратима. Не существует обратной функции, которая из хэша может восстановить исходный массив информации. Пример с хранением и передачей пароля.
  5. Высокая скорость работы. Хэширование позволяет достаточно быстро вычислять хэш для больших значений из области определения.
Потенциал хэширования раскрывается когда речь идет о быстром поиске элементов в коллекциях. Например поиск в списке (перебор элементов) занимает линейное время, поиск в отсортированном списке занимает логарифмическое время, но хэширование позволяет добиться еще большего ускорения.

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

Во встроенных коллекциях Python множества и словари реализуют структуру данных хэш-таблицы.

Пример:

Определим параметры хэш-таблицы:

Область определения: числа от 0 до 100 включительно
Область значения: все действительные числа.
Размер таблицы: 11
Хэш-функция: "методом остатков", элемент из области определения делится на размер таблицы, возвращая остаток в качестве хэша.
Инициализируем пустую таблицу.
Пусть мы хотим добавить в хэш-таблицу набор целых чисел 54, 26, 93, 17, 77 и 31 (числа из области определения). Преобразуем каждый элемент хэш функцией для получения уникального хэша:
Заполняем хэш таблицу используя хэши в качестве индексов элементов:
Фактор загрузки хэш-таблицы - это отношение количества заполненных ячеек к общему кол-ву. Python увеличивает хэш-таблицу в 2 раза когда фактор загрузки становится ⅔.

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

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

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

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