Предисловие

Типы dict и set в Python построены на основе хэш-таблиц. В этой статье объясняется как использование хэш-таблиц определяет сильные и слабые стороны этих типов контейнеров.

Вот некоторые вопросы, на которые отвечает эта статья:

• Насколько эффективны dict и set в Python?

• Почему элементы множества неупорядоченны?

• Почему мы не можем использовать любой объект Python в качестве ключа dict или элемента set?

• Почему порядок ключей dict зависит от порядка вставки?

Содержание

• 1. Эксперимент с производительностью

• 2. Хэши и равенство (equality)

  • 2.1 Коллизии хэша

• 3. Хэш-таблицы в set

  • 3.1. Алгоритм хэш-таблицы

  • 3.2. Практические выводы по тому как работает 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:

1. Вызвать hash('Sat'), чтобы получить хэш-код. Допустим, это 4910012646790914166.

2. Получить индекс хэш-таблицы из хэш-кода, используя hash_code % table_size. В данном случае индекс равен 6.

3. Проверить смещение 6 — оно пустое. Это означает, что 'Sat' отсутствует в set. Возвращаем False.

Теперь рассмотрим простейший путь для элемента, который присутствует в set. Чтобы оценить 'Thu' в workdays:

1. Вызвать hash('Tue'). Представьте, что результат — 6166047609348267525.

2. Вычислить индекс: 6166047609348267525 % 8 -> 5.

3. Смещение 5:

   1. Сравнить хэш-коды. Они равны.

   2. Сравнить значения объектов. Они равны. Возвращаем 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 оставались пустыми. Когда это происходит, элементы вставляются заново и могут возникнуть различные коллизии.

Примечания

1. Поскольку я только что упомянул int, вот деталь реализации CPython: хэш-код int, который помещается в машинное слово, является значением самого int, за исключением хэша -1, который равен -2.

2. Слово bucket имеет больше смысла для описания хэш-таблиц, в которых хранится более одного элемента в строке. В Python хранится только один элемент в строке, но мы будем придерживаться красочного традиционного термина.

3. Встроенная функция hash() никогда не возвращает -1 для любого объекта Python. Если x.hash() возвращает -1, то hash(x) возвращает -2.

4. В 64-битном CPython коллизии хэшей строк настолько редки, что я не смог привести пример для этого объяснения. Если вы найдете такой пример, дайте мне знать.

5. Вот как хранятся кортежи.

↑ К содержанию

→ Часть 2