Хеширование в 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»
Хешируемый объект должен удовлетворять двум основным требованиям:
- у него можно получить хеш через
hash(); - его хеш должен оставаться неизменным в течение времени, пока объект используется как хешируемый ключ.
Кроме того, хеш должен быть согласован с оператором:
==
Обычно хешируемыми являются знакомые нам неизменяемые типы:
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. Если хеши одинаковые,
объекты не обязательно равны.
Последняя ситуация возможна из-за:
коллизий
К способам разрешения коллизий и внутреннему устройству хеш-таблиц вернёмся позже.