Комментарий переводчика
Автор использует термин
хэш-код
(hash code
). Синонимы: хэш, хеш, хэш-сумма, хэш-значение (hash value).-
Термины приводятся в английском написании, чтобы:
избежать путаницы, например такой: «множество атрибутов» (что имелось в виду?)
иметь под рукой оригинальную терминологию
Предисловие
Типы dict
и set
в Python построены на основе хэш-таблиц. В этой статье объясняется как использование хэш-таблиц определяет сильные и слабые стороны этих типов контейнеров.
Вот некоторые вопросы, на которые отвечает эта статья:
Насколько эффективны
dict
иset
в Python?Почему элементы множества неупорядоченны?
Почему мы не можем использовать любой объект Python в качестве ключа
dict
или элементаset
?Почему порядок ключей
dict
зависит от порядка вставки?
Содержание
-
3. Хэш-таблицы в
set
-
4. Хэш-таблицы в
dict
4.1. Как компактный
dict
экономит место и сохраняет порядок4.2 Алгоритм добавления элементов в компактный
dict
4.3.
dict
с общим доступом к ключам4.4. Практические выводы по тому как работает
dict
? Вам не нужно знать все эти детали, чтобы эффективно использовать словари и множества. Но идеи реализации прекрасны, поэтому я их описываю. Для получения практических советов вы можете перейти к разделам 3.2. Практические выводы по тому как работает
set
и 4.4. Практические выводы по тому как работаетdict
.
Чтобы мотивировать изучение хэш-таблиц, мы начнем с демонстрации удивительной производительности dict
и set
на примере простого теста с миллионами элементов.
1. Эксперимент с производительностью
? Репозиторий: https://github.com/AllenDowney/fluent-python-notebooks/tree/master/03-dict-set/support
По опыту все питонисты знают, что dict
и set
— это быстро. Мы подтвердим это с помощью контролируемого эксперимента.
Чтобы посмотреть, как размер dict
, set
или list
влияет на производительность поиска с помощью оператора in
, я сгенерировал массив из 10 млн различных чисел типа float
— это будет haystack
(стог сена). Затем я сгенерировал массив: 1000 чисел типа float
, 500 из которых были выбраны из haystack
, а 500 проверены на отсутствие в нем — это будут needles
(иголки).
Для теста производительности dict
я использовал dict.fromkeys()
, чтобы создать dict
с именем haystack
с 1000 числами типа float
. Это сетап для теста dict
. Собственно код, который я засекал с помощью модуля timeit
, приведен в примере 1.
Пример 1. Поиск needles
в haystack
и подсчет найденных
found = 0
for n in needles:
if n in haystack:
found += 1
Я повторил тест пять раз, каждый раз увеличивая размер haystack
в десять раз, от 1000 до 10 млн элементов. Результат теста приведен на рис. 1.
Если говорить конкретно, то для проверки наличия 1000 ключей типа float
в словаре с 1000 элементов, время обработки на моем ноутбуке составило 0.099 мс, а тот же поиск в словаре с 10 млн элементов занял 0.512 мс. Другими словами, среднее время поиска в словаре haystack
с 10 миллионами элементов составляло 0,512 мс. Да, это примерно половина микросекунды на иголку (на элемент из needles
). Когда пространство поиска стало в 10 000 раз больше, время поиска увеличилось чуть более чем в 5 раз. Мило.
Чтобы сравнить с другими коллекциями, я повторил бенчмарк с тем же haystack
все большего размера, но храня его как set
и как list
. Для тестов с set
, помимо тайминга цикла for
в примере 1, я также засекал время выполнения однострочника: пример 2, который дает тот же результат: подсчет количества элементов из needles
, которые также есть в haystack
, если оба являются set
.
Пример 2. Используйте пересечение множеств для подсчета иголок, которые встречаются в haystack
found = len(needles & haystack)
На рис. 2 показаны результаты тестов рядом друг с другом. Наилучшее время находится в столбце set& time
, где показаны результаты для оператора set
&
с использованием кода из примера 2. Как и ожидалось, худшее время находится в столбце list time
, потому что не существует хэш-таблицы для поддержки поиска с помощью оператора in
в list
, поэтому необходимо выполнить полное сканирование, если элемент needles
(иголка) отсутствует, что приводит к времени, которое линейно растет с размером haystack
.
Если ваша программа выполняет любой вид ввода-вывода, время поиска ключей в словарях или множествах будет незначительным, независимо от размера словаря или множества (пока он помещается в оперативной памяти).
Теперь, когда у нас есть конкретное доказательство скорости работы dict
и set
, давайте рассмотрим, как это достигается с помощью хэш-таблиц.
Прежде чем изучать хэш-таблицы, нам нужно узнать больше о хэш-кодах и о том как они связаны с равенством.
2. Хэши и равенство (equality)
Built-in функция hash()
работает напрямую с built-in типами и переключается на вызов __hash__
для типов, определяемых пользователем. Если два объекта сравниваются между собой, их хэш-коды также должны быть одинаковыми, иначе алгоритм хэш-таблицы не работает. Например, поскольку 1 == 1.0
— это True
, то hash(1) == hash(1.0)
тоже должно быть True, даже несмотря на то, что внутренние представления int
и float
сильно отличаются(1).
Кроме того, чтобы быть эффективными в качестве индексов хэш-таблиц, хэш-коды должны быть как можно более разбросаны по пространству индексов. Это означает, что в идеале объекты, которые схожи, но не одинаковы, должны иметь сильно отличающиеся хэш-коды. Пример 3 — вывод скрипта для сравнения битовых шаблонов хэшей. Обратите внимание, что хэш-коды 1
и 1.0
одинаковы, а хэш-коды 1.0001
, 1.0002
и 1.0003
сильно отличаются.
Пример 3. Сравнение битовых шаблонов хэшей 1, 1.0001, 1.0002 и 1.0003 на 32-битной сборке Python (биты, отличающиеся в хэшах выше и ниже, выделены символом !
, а в правой колонке показано количество отличающихся битов)
32-bit Python build
1 00000000000000000000000000000001
!= 0
1.0 00000000000000000000000000000001
------------------------------------------------
1.0 00000000000000000000000000000001
! !!! ! !! ! ! ! ! !! !!! != 16
1.0001 00101110101101010000101011011101
------------------------------------------------
1.0001 00101110101101010000101011011101
!!! !!!! !!!!! !!!!! !! ! != 20
1.0002 01011101011010100001010110111001
------------------------------------------------
1.0002 01011101011010100001010110111001
! ! ! !!! ! ! !! ! ! ! !!!! != 17
1.0003 00001100000111110010000010010110
------------------------------------------------
? Начиная с Python 3.3, при вычислении хэшей для объектов
str
,bytes
иdatetime
используется случайное значение соли, как описано в выпуске 13703-Hash collision security issue. Значение соли постоянно в рамках процесса Python, но меняется между запусками интерпретатора. В PEP-456 Python 3.4 принял криптографическую функциюSipHash
для вычисления хэшей для объектовstr
иbytes
. Случайная соль иSipHash
— это меры безопасности для предотвращения DoS-атак. Подробности приведены в примечании в документации к специальному методу__hash__
.
2.1 Коллизии хэша
Как уже говорилось, в 64-битном CPython хэш-код — это 64-битное число, а это 2⁶⁴ возможных значения, что больше, чем 10¹⁹. Но большинство типов Python могут представлять гораздо больше различных значений. Например, строка из 10 печатных символов ASCII, выбранных наугад, имеет 100¹⁰ возможных значений — больше, чем 2⁶⁶. Поэтому хэш-код объекта обычно содержит меньше информации, чем фактическое значение объекта. Это означает, что разные объекты могут иметь одинаковый хэш.
? При правильной реализации, хэширование гарантирует, что разные хэш-коды всегда означают разные объекты, но обратное неверно: разные объекты не всегда имеют разные хэш-коды. Когда разные объекты имеют одинаковый хэш — это хэш-коллизия.
Имея базовое представление о хэшах и равенстве объектов, мы готовы перейти к рассмотрению принципов работы хэш-таблиц и обработки хэш-коллизий.
3. Хэш-таблицы в set
Хэш-таблицы — замечательное изобретение. Давайте посмотрим, как используется хэш-таблица при добавлении элементов в set
.
Допустим, у нас есть set
с сокращенными названиями рабочих дней, созданный следующим образом:
>>> workdays = {'Mon', 'Tue', 'Wed', 'Thu', 'Fri'}
>>> workdays
{'Tue', 'Mon', 'Wed', 'Fri', 'Thu'}
Структурой данных в основе set
в Python является хэш-таблица, содержащая не менее 8 строк. Традиционно строки в хэш-таблице называются buckets
(2).
Хеш-таблица, содержащая элементы рабочих дней, выглядит так, как показано на рис. 3.
В CPython, для 64-битного процессора, каждый bucket
в set
имеет два поля: 64-битный хэш-код и 64-битный указатель на значение элемента, который является объектом Python, хранящимся в другом месте в памяти. Поскольку buckets
имеют фиксированный размер, доступ к отдельным buckets
осуществляется по смещению от начала хэш-таблицы. Другими словами, индексы от 0 до 7 на рис. 3 не хранятся, это просто смещения.
3.1. Алгоритм хэш-таблицы
Сначала мы сосредоточимся на внутреннем устройстве set
, а затем перенесем эти понятия на dict
.
? Это упрощенное представление того, как Python использует хэш-таблицу для реализации
set
. Все подробности смотрите в комментированном исходном коде CPython дляset
иfrozenset
в Include/setobject.h и Objects/setobject.c.
Давайте посмотрим как Python создает set
{'Mon', 'Tue', 'Wed', 'Thu', 'Fri'}
, шаг за шагом. Алгоритм проиллюстрирован блок-схемой на рис. 4 и описан далее.
Шаг 0: инициализация хэш-таблицы
Как упоминалось ранее, хэш-таблица для set
начинается с 8 пустых bucket
. По мере добавления элементов, Python следит за тем, чтобы по крайней мере ⅓ buckets
были пустыми, удваивая размер хэш-таблицы, когда требуется больше места. Поле хэша каждого bucket
инициализируется значением -1
, что означает «нет хэша»(3).
Шаг 1: вычисление хэша для элемента
Для {'Mon', 'Tue', 'Wed', 'Thu', 'Fri'}
, Python получает хэш-код для первого элемента, 'Mon'
. Пример реального значения хэша для 'Mon'
— вы, вероятно, получите другой результат из-за случайной соли, которую Python использует для вычисления хэша строк:
>>> hash('Mon')
4199492796428269555
Шаг 2: процесс проверки хэш-таблицы на индекс, полученный из хэша
Чтобы найти индекс хэш-таблицы, Python берет хэш-код по модулю размер таблицы. Иными словами — остаток от деления значения хэша на значение размера таблицы. Здесь размер таблицы равен 8, а модуль равен 3:
>>> 4199492796428269555 % 8
3
Процесс проверки заключается в вычислении индекса из хэша и последующем просмотре соответствующего bucket
в хэш-таблице. В данном случае Python просматривает bucket
по смещению 3
и находит -1
в поле хэша, обозначая пустой bucket
.
Шаг 3: поместить элемент в пустой bucket
Python сохраняет хэш-код нового элемента 4199492796428269555
в поле хэша по смещению 3
и указатель на строковый объект 'Mon'
в поле указателя на элемент. На рис. 5 показано текущее состояние хэш-таблицы.
Шаги для оставшихся элементов
Для второго элемента, 'Tue'
, повторяются шаги 1, 2, 3, описанные выше. Хэш-код для 'Tue'
— 2414279730484651250
, а результирующий индекс — 2
.
>>> hash('Tue')
2414279730484651250
>>> hash('Tue') % 8
2
Хэш-код и указатель на элемент 'Tue'
помещаются в bucket
2
, который также был пуст. Теперь у нас есть рис. 6
Шаги при коллизии
При добавлении 'Wed'
в set
, Python вычисляет хэш-код (-5145319347887138165
) и индекс (3
). Python проверяет bucket
3
и видит, что он уже занят. Но хранящийся там хэш-код 4199492796428269555
отличается. Как уже говорилось в разделе 2. Хэши и равенство (equality), если два объекта имеют разные хэш-коды, то и их значение тоже разное. Это коллизия индексирования. Затем Python проверяет следующий bucket
и находит его пустым. Таким образом, 'Wed'
оказывается в индексе 4
, как показано на рис. 7.
Добавлять следующий элемент 'Thu'
скучно: коллизий нет и он попадает в свой естественный bucket
, с индексом 7
.
Размещение 'Fri'
более интересно. Его хэш-код 7021641685991143771
подразумевает индекс 3
, который занят элементом 'Mon'
. Опросив следующий bucket
(с индексом 4
), Python находит в нем хэш-код для 'Wed'
. Хэш-коды не совпадают, так что это еще одна коллизия индексов. Python проверяет следующий bucket
. Он пустой, поэтому 'Fri'
оказывается в индексе 5
. Конечное состояние хэш-таблицы показано на рис. 8.
? Увеличение индекса после коллизии называется линейным зондированием (linear probing). Это может привести к образованию скоплений (кластеров) занятых
buckets
, что может ухудшить производительность хэш-таблицы, поэтому CPython подсчитывает количество линейных зондирований и после определенного порога применяет генератор псевдослучайных чисел для получения другого индекса из других битов хэша. Эта оптимизация особенно важна для большихset
.
Когда в проверяемом bucket
есть элемент и хэш-коды совпадают, Python также необходимо сравнить фактические значения объектов. Это связано с тем, что, как объясняется в разделе 2.1 Коллизии хэша, возможно, что два разных объекта имеют одинаковый хэш, хотя для строк это редкость, благодаря качеству алгоритма Siphash
(4). Это объясняет почему хэшируемые объекты должны реализовывать как __hash__
, так и __eq__
.
Если в нашу хэш-таблицу добавить новый элемент, она будет заполнена более чем на ⅔, что увеличит вероятность коллизий индексов. Чтобы предотвратить это, Python выделит новую хэш-таблицу с 16 ячейками и заново вставит туда все элементы.
Все это может показаться большой работой, но даже при миллионах элементов в set
многие вставки происходят без коллизий, а среднее количество коллизий на одну вставку составляет от одной до двух. При обычном использовании даже самые неудачливые элементы могут быть размещены после устранения горстки коллизий.
Учитывая то, что мы уже видели, следуйте схеме на рис. 4.
Что произойдет, если к set
s
добавить целое число 1
?
>>> s = {1.0, 2.0, 3.0}
>>> s.add(1)
Сколько элементов в s
сейчас? Заменяет ли 1
элемент 1.0
? Когда вы получите ответ, проверьте его с помощью консоли Python.
Поиск элементов в хэш-таблице
Рассмотрим set
workdays
с помощью хэш-таблицы, показанной на рис. 8. Есть ли в ней элемент 'Sat'
? Это самый простой путь выполнения для выражения 'Sat'
в workdays
:
Вызвать
hash('Sat')
, чтобы получить хэш-код. Допустим, это4910012646790914166
.Получить индекс хэш-таблицы из хэш-кода, используя
hash_code % table_size
. В данном случае индекс равен6
.Проверить смещение
6
— оно пустое. Это означает, что'Sat'
отсутствует вset
. ВозвращаемFalse
.
Теперь рассмотрим простейший путь для элемента, который присутствует в set
. Чтобы оценить 'Thu'
в workdays
:
Вызвать
hash('Tue')
. Представьте, что результат —6166047609348267525
.Вычислить индекс:
6166047609348267525 % 8
->5
.-
Смещение
5
:Сравнить хэш-коды. Они равны.
Сравнить значения объектов. Они равны. Возвращаем
True
.
Коллизии обрабатываются так же как и при добавлении элемента. Фактически, схема на рис. 4 применима и к поиску, за исключением конечных узлов — прямоугольников с закругленными углами. Если найден пустой bucket
, то элемент отсутствует, поэтому Python возвращает False
, в противном случае, когда и хэш-код и значения искомого элемента совпадают с элементом в хэш-таблице, возвращается True
.
3.2. Практические выводы по тому как работает set
Типы set
и frozenset
реализованы с помощью хэш-таблиц, что приводит к следующим результатам:
Элементы множества должны быть хэшируемыми объектами. Они должны реализовывать соответствующие методы
__hash__
и__eq__
(«Python. К вершинам мастерства» 2-е изд. — Словари и множества — Что значит "хэшируемый"?, стр. 105)Проверка принадлежности очень эффективна. В
set
могут быть миллионы элементов, ноbucket
для элемента можно найти напрямую, вычислив хэш-код элемента и получив индексное смещение, с возможными накладными расходами на небольшое количество проб для поиска совпадающего элемента или пустогоbucket
.set
требуют значительных затрат памяти. Наиболее компактной внутренней структурой данных для контейнера был бы массив указателей(5). По сравнению с ним, хэш-таблица добавляет хэш-код для каждой записи и не менее ⅓ пустыхbuckets
, чтобы минимизировать риск возникновения коллизий.Порядок элементов зависит от порядка вставки, но не является полезным или надежным способом. Если два элемента участвуют в коллизии, то
bucket
, в котором хранится каждый из них, зависит от того, какой элемент был добавлен первым.Добавление элементов в
set
может изменить порядок других элементов. Это происходит потому что по мере заполнения хэш-таблицы Python может потребоваться пересоздать ее, чтобы хотя бы ⅓buckets
оставались пустыми. Когда это происходит, элементы вставляются заново и могут возникнуть различные коллизии.
Примечания
Поскольку я только что упомянул
int
, вот деталь реализации CPython: хэш-кодint
, который помещается в машинное слово, является значением самогоint
, за исключением хэша-1
, который равен-2
.
Слово
bucket
имеет больше смысла для описания хэш-таблиц, в которых хранится более одного элемента в строке. В Python хранится только один элемент в строке, но мы будем придерживаться красочного традиционного термина.
Встроенная функция
hash()
никогда не возвращает-1
для любого объекта Python. Еслиx.hash()
возвращает-1
, тоhash(x)
возвращает-2
.
В 64-битном CPython коллизии хэшей строк настолько редки, что я не смог привести пример для этого объяснения. Если вы найдете такой пример, дайте мне знать.
Вот как хранятся кортежи.
Комментарии (4)
Chamber6821
19.07.2024 12:26Почему Python не использует цепочки указателей? Из-за нарушения локальности?
Dmitri-D
19.07.2024 12:26+2все интересное происходит при удалении -- если нам надо удалить первый элемент, приведший к коллизии. Если мы просто вычеркнем его из таблицы, то потом рискуем не найти элемент, который столкнулся с удаленным. Поэтому вводят флаги - признаки - этот слот "просто пустой" и не инициализирован или "там было что-то" и поэтому при lookup нам нужно продолжить поиск до "просто пустой" -- согласитесь, это важный элемент устройства хеш таблиц с открытым размещением.
Chamber6821
Повторяется 2 раза подряд
And23ym Автор
Спасибо, поправил!