Хеширование в Python: hash() и хеш-таблицы

Обновлено:

На следующем этапе мы познакомимся с новым типом данных:

dict

Чтобы лучше понимать, почему словарь работает именно так, сначала познакомимся с:

hash()

и очень поверхностно разберём устройство хеш-таблицы.


1. Функция hash()

Встроенная функция:

hash()

возвращает целое число — хеш объекта.

Например:

print(
    hash('Python')
)

Результатом будет некоторое целое число:

-483291765...

Конкретное значение запоминать не нужно.


2. Хеш целого числа

print(
    hash(100)
)

Для обычных небольших целых чисел в CPython обычно получим:

100

Например:

print(hash(10))
print(hash(500))
print(hash(-20))

Для большинства небольших int хеш совпадает с самим числом.

Но это не универсальное правило для абсолютно любого целого числа.

Например, существуют специальные случаи и очень большие целые числа обрабатываются иначе.

Поэтому правильнее запомнить:

hash() всегда возвращает целое число, но не нужно рассчитывать, что оно обязательно будет совпадать с самим объектом.


3. Хеш строки

text = 'Python'

print(
    hash(text)
)

Получим некоторое целое число.

Важно:

Хеш строк в Python не следует сохранять и использовать как постоянный идентификатор.

Для строк хеш может отличаться между разными запусками Python.

Например, сегодня:

hash('Python') → 5362...

а после нового запуска программы значение может быть другим.

Внутри одного запуска программы хеш объекта остаётся согласованным с правилами хеширования.


4. Хеш кортежа

Некоторые кортежи тоже можно хешировать:

coordinates = (
    10,
    20,
)

print(
    hash(coordinates)
)

Получим целое число.

Но есть важное условие:

Все элементы кортежа тоже должны быть хешируемыми.

Например:

data = (
    10,
    [20, 30],
)

print(
    hash(data)
)

приведёт к:

TypeError

Потому что внутри находится:

list

а список не является хешируемым.


Хешируемые объекты

5. Что значит «hashable»

Хешируемый объект должен удовлетворять двум основным требованиям:

  1. у него можно получить хеш через hash();
  2. его хеш должен оставаться неизменным в течение времени, пока объект используется как хешируемый ключ.

Кроме того, хеш должен быть согласован с оператором:

==

Обычно хешируемыми являются знакомые нам неизменяемые типы:

int
float
str
tuple — если его элементы тоже хешируемы

Неизменяемость часто делает объект подходящим для хеширования, но понятия:

immutable

и:

hashable

не являются абсолютно одним и тем же.

Для работы со словарями важно именно понятие хешируемости.


6. Изменяемый список хешировать нельзя

numbers = [
    10,
    20,
    30,
]

print(
    hash(numbers)
)

Возникнет:

TypeError: unhashable type: 'list'

Список может менять своё содержимое:

numbers.append(40)

Поэтому Python не разрешает использовать обычный list как хешируемый ключ.


Почему это важно

7. Ключ должен оставаться доступным

Представим, что некоторый объект использовался как ключ.

Для него был вычислен хеш:

ключ
↓
hash
↓
место в хеш-таблице

Если бы после изменения объекта изменился и его хеш:

старый hash → одно место

новый hash → другое место

то структура могла бы больше не найти элемент там, куда он был первоначально помещён.

Именно поэтому для ключей хеш-таблицы нужны объекты с корректным и стабильным хешем.


Первое знакомство с dict

8. Словарь

Словарь хранит пары:

ключ → значение

Например:

user = {
    'name': 'Alex',
    'age': 30,
    'city': 'Tbilisi',
}

Здесь:

'name' → 'Alex'
'age'  → 30
'city' → 'Tbilisi'

9. Получение значения по ключу

print(
    user['name']
)

Результат:

Alex

Мы не спрашиваем:

user[0]

как у списка.

Мы обращаемся по ключу:

user['name']

10. Изменение значения

user['age'] = 31

print(user)

Получим:

{
    'name': 'Alex',
    'age': 31,
    'city': 'Tbilisi',
}

Если такой ключ уже существует, значение заменяется.


11. Добавление новой пары

user['language'] = 'Python'

Теперь:

print(user)

получим:

{
    'name': 'Alex',
    'age': 31,
    'city': 'Tbilisi',
    'language': 'Python',
}

Если ключа раньше не было, появляется новая пара:

ключ → значение

Что находится под капотом dict

12. Хеш-таблица

В CPython словарь:

dict

реализован с использованием хеш-таблицы.

Подробно хеш-таблицы мы будем изучать позже.

Пока достаточно очень упрощённой модели.

Можно представить некоторый внутренний массив:

[ ][ ][ ][ ][ ][ ][ ][ ]

В отдельные позиции которого помещаются записи словаря.

Например:

ключ + значение

13. Ключ не является индексом напрямую

Важно понимать:

user['name']

не означает, что строка:

'name'

сама является индексом массива.

Сначала Python получает хеш ключа:

hash('name')

Например, условно:

482739182...

После этого данные хеша используются внутренним алгоритмом хеш-таблицы для поиска подходящей позиции.

Очень упрощённо:

ключ
↓
hash(key)
↓
вычисление позиции / последовательности поиска
↓
нужная запись

14. Упрощённый пример

Есть:

user = {
    'name': 'Alex',
    'age': 30,
}

При добавлении:

user['name'] = 'Alex'

можно представить работу примерно так:

'name'
↓
hash('name')
↓
хеш-таблица определяет,
где должна находиться запись
↓
['name', 'Alex']

После этого при:

user['name']

Python снова:

получает hash('name')
↓
ищет соответствующую позицию
↓
проверяет ключ
↓
возвращает 'Alex'

Почему поиск быстрый

15. Средняя сложность O(1)

В списке, если мы ищем значение:

value in numbers

может потребоваться последовательно проверить:

элемент 0
элемент 1
элемент 2
...

Поэтому такой поиск обычно:

O(n)

В словаре поиск по ключу устроен иначе.

Хеш позволяет быстро определить, где искать нужную запись.

Поэтому операции:

user[key]
user[key] = value

в среднем имеют сложность:

O(1)

То есть время поиска обычно не растёт линейно вместе с количеством элементов.


16. O(1) — средняя, а не абсолютная гарантия

Для хеш-таблицы корректно говорить:

average O(1)

— средняя сложность O(1).

В некоторых неблагоприятных ситуациях работа может быть дороже.

Например, на неё влияют:

  • коллизии;
  • перестройка таблицы;
  • особенности сравнения ключей.

Подробнее это будет изучаться позже.


Коллизия

17. Два разных объекта могут иметь одинаковый хеш

Хеш — это число ограниченного диапазона.

Разных возможных объектов гораздо больше.

Поэтому иногда два разных объекта могут получить одинаковый хеш:

object_1
↓
12345

object_2
↓
12345

Такая ситуация называется:

коллизия хешей.


18. Одинаковый хеш не означает одинаковый объект

Хеш-таблица не может просто сказать:

хеш совпал
→ значит ключ тот же

После нахождения потенциальной записи Python также должен убедиться, что ключ действительно подходит.

Именно поэтому в таблице хранится не только значение, но и информация о ключе.

Упрощённо:

hash
key
value

Три важных правила

19. Если объекты равны — их хеши должны быть равны

Если:

first == second

возвращает:

True

и оба объекта хешируемы, то обязательно должно выполняться:

hash(first) == hash(second)

Например:

first = 10
second = 10.0

print(
    first == second
)

Результат:

True

Поэтому:

print(
    hash(first)
    == hash(second)
)

тоже:

True

20. Если хеши разные — объекты точно не равны

Если:

hash(first) != hash(second)

то равными эти объекты быть не могут.

Почему?

Потому что для равных хешируемых объектов действует обязательное правило:

равные объекты
→ одинаковые хеши

Следовательно:

разные хеши
→ объекты не равны

21. Но одинаковые хеши не гарантируют равенство

Обратное правило неверно.

Может существовать:

hash(first) == hash(second)

при этом:

first != second

Именно это и называется возможностью коллизии.

Поэтому:

одинаковый hash

ещё не означает:

одинаковый объект

22. Не стоит искать коллизию на случайных строках

Например, не нужно рассчитывать, что:

hash('')

обязательно совпадёт с:

hash(0)

на каждой реализации или версии Python.

Конкретные значения хешей — детали реализации.

Главная идея:

Коллизии возможны в принципе, поэтому хеш-таблица умеет с ними работать.


Почему ключ хранится вместе со значением

23. Одного хеша недостаточно

Представим:

key_1 → hash 123
key_2 → hash 123

Если бы таблица хранила только:

123 → value

она не могла бы определить, какой именно ключ нужен.

Поэтому при поиске используется не только хеш.

Упрощённо:

получили hash
↓
нашли потенциальную позицию
↓
проверили сам ключ
↓
получили нужное значение

Почему ключи словаря должны быть хешируемыми

24. Строка подходит

user = {
    'name': 'Alex',
}

str хешируем:

hash('name')

работает.

Поэтому строка может быть ключом.


25. Число подходит

data = {
    10: 'ten',
}

int является хешируемым.


26. Подходящий tuple

points = {
    (
        10,
        20,
    ): 'Point A',
}

Такой кортеж состоит из хешируемых элементов:

int
int

поэтому его можно использовать как ключ.


27. list не подходит

data = {
    [10, 20]: 'Point A',
}

так написать нельзя.

Получим:

TypeError: unhashable type: 'list'

Неизменяемость и хешируемость

28. Упрощённое правило для начала

На текущем этапе удобно запомнить:

В качестве ключей dict обычно используются неизменяемые хешируемые объекты.

Например:

int
float
str
tuple из хешируемых элементов

А знакомый нам:

list

ключом быть не может.

Позже мы увидим, что понятие hashable немного шире, чем просто «неизменяемый тип».


Изменение существующего ключа

29. Новый ключ не создаётся

Например:

user = {
    'name': 'Alex',
}

user['name'] = 'Emma'

Ключ:

'name'

уже существует.

Поэтому Python находит его через хеш-таблицу и заменяет только значение:

было:

'name' → 'Alex'

стало:

'name' → 'Emma'

Очень упрощённая модель словаря

Можно представить работу:

user = {
    'name': 'Alex',
    'age': 30,
}

так:

             dict
               ↓
         хеш-таблица
               ↓

'name'
   ↓
hash('name')
   ↓
позиция в таблице
   ↓
['name', 'Alex']


'age'
   ↓
hash('age')
   ↓
другая позиция
   ↓
['age', 30]

Это лишь учебная модель.

Реальное устройство dict в CPython значительно сложнее и специально оптимизировано.


Хеш-таблица и динамический массив

30. Почему таблице нужна дополнительная свободная ёмкость

Хеш-таблица не должна быть заполнена полностью.

Если свободного места становится слишком мало, возрастает количество столкновений и поиск становится менее эффективным.

Поэтому внутренняя таблица обычно имеет свободные позиции.

Условно:

[запись][ ][запись][ ][ ][запись][ ][ ]

Когда таблица становится слишком заполненной, реализация может создать более крупную внутреннюю таблицу и перестроить расположение записей.

Точные размеры вроде:

9 элементов → 16 ячеек

запоминать не нужно.

Это внутренние детали реализации CPython, которые могут меняться.


Главное по теме

Функция:

hash()

возвращает целое число — хеш объекта:

hash('Python')
hash(100)
hash((10, 20))

Но работает она только с хешируемыми объектами.

Например:

hash([10, 20])

приведёт к:

TypeError

dict в CPython построен на основе хеш-таблицы.

Упрощённо работа выглядит так:

ключ
↓
hash(key)
↓
поиск позиции в хеш-таблице
↓
проверка ключа
↓
значение

Поэтому обращение:

dictionary[key]

в среднем выполняется за:

O(1)

Ключ словаря должен быть:

hashable

То есть иметь стабильный хеш и корректно участвовать в сравнении.


Три важнейших правила:

1. Если объекты равны,
   их хеши обязательно равны.

2. Если хеши разные,
   объекты точно не равны.

3. Если хеши одинаковые,
   объекты не обязательно равны.

Последняя ситуация возможна из-за:

коллизий

К способам разрешения коллизий и внутреннему устройству хеш-таблиц вернёмся позже.