Создайте хэш-таблицу на Python с помощью TDD

>>> glossary = {"BDFL": "Benevolent Dictator For Life"}
>>> glossary["GIL"] = "Global Interpreter Lock"  # Add
>>> glossary["BDFL"] = "Guido van Rossum"  # Update
>>> del glossary["GIL"]  # Delete
>>> glossary["BDFL"]  # Search
'Guido van Rossum'
>>> glossary
{'BDFL': 'Guido van Rossum'}


Используя синтаксис квадратных скобок  ([ ]), вы можете добавить в словарь новую пару ключ-значение. Вы также можете обновить значение или удалить существующую пару, идентифицируемую ключом. Наконец, вы можете просмотреть значение, связанное с данным ключом.
Тем не менее, вы можете задать другой вопрос. Как на самом деле работает встроенный словарь? Как он сопоставляет ключи произвольных типов данных и как ему удается это делать так быстро?
Поиск эффективной реализации этого абстрактного типа данных известен как проблема словаря. Одно из наиболее известных решений использует преимущества структуры данных хэш-таблицы, которую вы собираетесь изучить. Однако обратите внимание, что это не единственный способ реализации словаря в целом. Другая популярная реализация строится на вершине красно-черного дерева .
Хэш-таблица: Массив с хэш-функцией
Задумывались ли вы когда-нибудь, почему доступ к элементам последовательности в Python выполняется так быстро, независимо от того, какой индекс вы запрашиваете? Допустим, вы работали с очень длинной строкой символов, например, с этой:

>>> import string
>>> text = string.ascii_uppercase * 100_000_000

>>> text[:50]  # Show the first 50 characters
'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX'

>>> len(text)
2600000000


В переменной text, указанной выше, содержится 2,6 миллиарда символов из повторяющихся  букв ASCII, которые вы можете подсчитать с помощью Python len() функция. Тем не менее, получение первого, среднего, последнего или любого другого символа из этой строки происходит одинаково быстро:

>>> text[0]  # The first element
'A'

>>> text[len(text) // 2]  # The middle element
'A'

>>> text[-1]  # The last element, same as text[len(text) - 1]
'Z'


То же самое верно для всех типов последовательностей в Python, таких как списки и кортежи. Как так вышло? Секрет такой невероятной скорости заключается в том, что последовательности в Python поддерживаются массивом, который представляет собой структуру данных с произвольным доступом. Это следует двум принципам:

Массив занимает  непрерывных блока памяти.
Каждый элемент в массиве имеет фиксированный размер, известный заранее.

Когда вы знаете адрес памяти массива, который называется смещением , вы можете мгновенно добраться до нужного элемента в массиве, вычислив довольно простую формулу:

Формула для вычисления адреса в памяти элемента последовательности
Вы начинаете со смещения массива, которое также является адресом первого элемента массива, с нулевым индексом. Затем вы продвигаетесь вперед, добавляя необходимое количество байт, которое вы получаете, умножая размер элемента на индекс целевого элемента. На умножение и сложение нескольких чисел всегда уходит одинаковое количество времени.
 Примечание: В отличие от массивов, списки Python могут содержать разнородные элементы разного размера, что нарушило бы приведенную выше формулу. Чтобы смягчить это, Python добавляет еще один уровень косвенности, вводя массив из указателей на ячейки памяти вместо того, чтобы хранить значения непосредственно в массиве:

Массив указателей на адреса памяти
Указатели - это просто целые числа, которые всегда занимают одинаковое количество места. Адреса памяти принято обозначать с помощью шестнадцатеричной системы счисления . В Python   и некоторых других языках к таким числам добавляется префикс 0x.
Итак, вы знаете, что поиск элемента в массиве выполняется быстро, независимо от того, где этот элемент физически расположен. Можете ли вы воспользоваться той же идеей и повторно использовать ее в словаре? Да!
Хэш-таблицы получили свое название благодаря трюку под названием хэширование, который позволяет им преобразовывать произвольный ключ в целое число, которое может работать как индекс в обычном массиве. Таким образом, вместо поиска значения по числовому индексу вы будете искать его по произвольному ключу без заметной потери производительности. Это здорово!
На практике хэширование не будет работать с каждым ключом, но большинство встроенных типов в Python могут быть хэшированы. Если вы будете следовать нескольким правилам, то сможете создавать и свои собственные хэшируемые типы. Подробнее о хэшировании вы узнаете в следующем разделе.
Разберитесь в хэш-функции
Хэш-функция  выполняет хэширование, преобразуя любые данные в последовательность байтов фиксированного размера, называемую хэш-значением или хэш-код. Это число, которое может выступать в качестве цифрового отпечатка пальца или дайджеста, обычно намного меньше исходных данных, что позволяет проверить их целостность. Если вы когда-либо загружали большой файл из Интернета, например, образ диска дистрибутива Linux, то, возможно, вы заметили MD5 или SHA-2 контрольная сумма на странице загрузки.
Помимо проверки целостности данных и решения проблемы со словарем, хэш-функции помогают в других областях, включая безопасность и криптографию. Например, обычно вы храните хэшированные пароли в базах данных, чтобы снизить риск утечки данных. Цифровые подписи включают хэширование для создания дайджеста сообщений перед шифрованием. Блокчейн транзакции являются еще одним ярким примером использования хэш-функции в криптографических целях.
 Примечание: Криптографическая хэш-функция - это   особый тип хэш-функции, который должен соответствовать нескольким дополнительным требованиям. Однако в этом руководстве вы познакомитесь только с самой базовой формой хэш-функции, используемой в структуре данных хэш-таблицы.
Хотя существует множество алгоритмов хэширования, все они обладают несколькими общими свойствами, с которыми вы познакомитесь в этом разделе. Правильная реализация хорошей хэш-функции - сложная задача, которая может потребовать понимания продвинутой математики, включающей  простых чисел. К счастью, обычно вам не нужно реализовывать такой алгоритм вручную.
Python поставляется со встроенным модулем hashlib, который предоставляет множество хорошо известных криптографических хэш-функций, а также менее безопасные алгоритмы определения контрольной суммы. В языке также есть глобальная функция hash(), используемая в основном для быстрого поиска элементов в словарях и наборах. Сначала вы можете изучить, как это работает, чтобы узнать о наиболее важных свойствах хэш-функций.
Изучите встроенный в Python hash()
Прежде чем приступить к реализации хэш-функции с нуля, остановитесь на минутку и проанализируйте hash() в Python, чтобы разобраться в ее свойствах. Это поможет вам понять, с какими проблемами приходится сталкиваться при разработке собственной хэш-функции.
 Примечание: Выбор хэш-функции может существенно повлиять на производительность вашей хэш-таблицы. Поэтому при построении пользовательской хэш-таблицы далее в этом руководстве вы будете полагаться на встроенную функцию hash(). Реализация хэш-функции в этом разделе является лишь упражнением.
Для начала попробуйте свои силы в вызове hash() нескольких литералов типов данных, встроенных в Python, таких как числа и строки, чтобы увидеть, как ведет себя функция:

>>> hash(3.14)
322818021289917443

>>> hash(3.14159265358979323846264338327950288419716939937510)
326490430436040707

>>> hash("Lorem")
7677195529669851635

>>> hash("Lorem ipsum dolor sit amet, consectetur adipisicing elit,"
... "sed do eiusmod tempor incididunt ut labore et dolore magna"
... "aliqua. Ut enim ad minim veniam, quis nostrud exercitation"
... "ullamco laboris nisi ut aliquip ex ea commodo consequat."
... "Duis aute irure dolor in reprehenderit in voluptate velit"
... "esse cillum dolore eu fugiat nulla pariatur. Excepteur sint"
... "occaecat cupidatat non proident, sunt in culpa qui officia"
... "deserunt mollit anim id est laborum.")
1107552240612593693


Уже есть несколько замечаний, которые вы можете сделать, посмотрев на результат. Во-первых, встроенная хэш-функция может возвращать разные значения для некоторых входных данных, показанных выше. В то время как числовой ввод, по-видимому, всегда выдает идентичное хэш-значение, строка, скорее всего, этого не делает. Почему это так?» Может показаться, что hash() - это недетерминированная функция, но это не может быть дальше от истины!
Когда вы вызываете hash() с тем же аргументом в рамках существующего сеанса интерпретатора, вы продолжаете получать тот же результат:

>>> hash("Lorem")
7677195529669851635

>>> hash("Lorem")
7677195529669851635

>>> hash("Lorem")
7677195529669851635


Это потому, что хэш-значения являются неизменяемыми и не меняются на протяжении всего срока службы объекта. Однако, как только вы выйдете из Python и запустите его снова, вы почти наверняка увидите разные значения хэша при вызовах Python. Вы можете проверить это, попробовав опцию -c для запуска однострочного скрипта в вашем терминале:


Окна


Linux + macOS



C:\> python -c print(hash('Lorem'))
6182913096689556094

C:\> python -c print(hash('Lorem'))
1756821463709528809

C:\> python -c print(hash('Lorem'))
8971349716938911741



$ python -c 'print(hash("Lorem"))'
6182913096689556094

$ python -c 'print(hash("Lorem"))'
1756821463709528809

$ python -c 'print(hash("Lorem"))'
8971349716938911741


Это ожидаемое поведение, которое было реализовано в Python в качестве контрмеры против атаки типа "Отказ в обслуживании" (DoS), которая использовала известную уязвимость хэш-функций на веб-серверах. Злоумышленники могли использовать слабый алгоритм хэширования для преднамеренного создания так называемых коллизий хэшей, перегружая сервер и делая его недоступным. Типичным мотивом атаки был выкуп, поскольку большинство жертв зарабатывали деньги за счет постоянного присутствия в Сети.
Сегодня Python по умолчанию включает рандомизацию хэша для некоторых входных данных, таких как строки, чтобы сделать значения хэша менее предсказуемыми. Это делает hash() немного более  безопасным и затрудняет атаку. Однако вы можете отключить рандомизацию, установив фиксированное начальное значение с помощью переменной окружения PYTHONHASHSEED, например:


Окна


Linux + macOS



C:\> set PYTHONHASHSEED=1

C:\> python -c print(hash('Lorem'))
440669153173126140

C:\> python -c print(hash('Lorem'))
440669153173126140

C:\> python -c print(hash('Lorem'))
440669153173126140



$ PYTHONHASHSEED=1 python -c 'print(hash("Lorem"))'
440669153173126140

$ PYTHONHASHSEED=1 python -c 'print(hash("Lorem"))'
440669153173126140

$ PYTHONHASHSEED=1 python -c 'print(hash("Lorem"))'
440669153173126140


Теперь каждый вызов Python выдает одно и то же значение хэша для известных входных данных. Это может помочь в разделении или совместном использовании данных в кластере распределенных интерпретаторов Python. Просто будьте осторожны и осознайте риски, связанные с отключением рандомизации хэша. В целом, hash() в Python действительно является детерминированной  функцией, которая является одной из самых фундаментальных особенностей хэш-функции.
Кроме того, hash() кажется довольно универсальным, поскольку он принимает произвольные входные данные. Другими словами, он принимает значения различных типов и размеров. Функция без проблем принимает строки и числа с плавающей запятой независимо от их длины или величины. На самом деле, вы можете вычислять хэш-значения и более экзотических типов:

>>> hash(None)
5904497366826

>>> hash(hash)
2938107101725

>>> class Person:
...     pass
...

>>> hash(Person)
5904499092884

>>> hash(Person())
8738841746871

>>> hash(Person())
8738841586112


Здесь вы вызвали хэш-функцию для  объекта None в Python, саму функцию hash() и даже пользовательскую Person класс с несколькими его экземплярами. Тем не менее, не все объекты имеют соответствующее хэш-значение. Функция hash() вызовет исключение, если вы попытаетесь вызвать ее для одного из этих немногих объектов:

>>> hash([1, 2, 3])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'


Базовый тип входных данных будет определять, сможете ли вы вычислить хэш-значение. В Python экземпляры встроенных изменяемых типов, таких как списки, наборы и dicts, не являются хэшируемыми. Вы получили представление о том, почему это так, но подробнее вы узнаете в следующем разделе. На данный момент вы можете предположить, что большинство типов данных в целом должны работать с хэш-функцией.
Погрузитесь глубже в язык Python. hash()
Еще одной интересной характеристикой hash() является то, что она всегда выдает  результат фиксированного размера независимо от того, насколько большими были входные данные. В Python хэш-значение представляет собой целое число с умеренной величиной. Иногда оно может быть отрицательным, поэтому примите это во внимание, если вы планируете так или иначе полагаться на хэш-значения:

>>> hash("Lorem")
-972535290375435184


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

Задано m элементов и n контейнеров, если m > n, то существует по крайней мере один контейнер с более чем одним элементом.

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

# hash_distribution.py

from collections import Counter

def distribute(items, num_containers, hash_function=hash):
    return Counter([hash_function(item) % num_containers for item in items])

def plot(histogram):
    for key in sorted(histogram):
        count = histogram[key]
        padding = (max(histogram.values()) - count) * " "
        print(f"{key:3} {'■' * count}{padding} ({count})")


В нем используется Counter экземпляр для удобного представления гистограммы хэш-значений предоставленных элементов. Значения хэша распределяются по указанному количеству контейнеров путем их переноса с помощью оператора по модулю. Теперь вы можете взять, например, сто символов ASCII, пригодных для печати, затем вычислить их хэш-значения и показать их распределение:

>>> from hash_distribution import plot, distribute
>>> from string import printable

>>> plot(distribute(printable, num_containers=2))
0 ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ (51)
1 ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■   (49)

>>> plot(distribute(printable, num_containers=5))
0 ■■■■■■■■■■■■■■■            (15)
1 ■■■■■■■■■■■■■■■■■■■■■■■■■■ (26)
2 ■■■■■■■■■■■■■■■■■■■■■■     (22)
3 ■■■■■■■■■■■■■■■■■■         (18)
4 ■■■■■■■■■■■■■■■■■■■        (19)


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

>>> hash("Lorem")
1090207136701886571

>>> hash("Loren")
4415277245823523757


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

>>> hash(42)
42


Хэш-значения небольших целых чисел равны сами себе, что является деталью реализации, которую CPython использует для простоты и эффективности. Имейте в виду, что фактические значения хэша не имеют значения до тех пор, пока вы можете вычислить их детерминированным способом.
И последнее, но не менее важное: вычисление хэш-значения в Python выполняется  быстро даже для очень больших входных данных. На современном компьютере вызов hash() со строкой из 100 миллионов символов в качестве аргумента возвращает результат мгновенно. Если бы это было не так быстро, то дополнительные затраты на вычисление значения хэша в первую очередь свели бы на нет преимущества хэширования.
Определение свойств хэш-функции
Основываясь на том, что вы уже узнали о hash() в Python, теперь вы можете сделать выводы о желаемых свойствах хэш-функции в целом. Вот краткое описание этих функций, сравнивающее обычную хэш-функцию с ее криптографической разновидностью:



Feature
Hash Function
Cryptographic Hash Function




Deterministic
✔️
✔️


Universal Input
✔️
✔️


Fixed-Sized Output
✔️
✔️


Fast to Compute
✔️
✔️


Uniformly Distributed
✔️
✔️


Randomly Distributed

✔️


Randomized Seed

✔️


One-Way Function

✔️


Avalanche Effect

✔️



 Цели обоих типов хэш-функций совпадают, поэтому у них есть несколько общих черт. С другой стороны, криптографическая хэш-функция обеспечивает дополнительные гарантии безопасности.
Прежде чем создавать свою собственную хэш-функцию, вы ознакомитесь с другой функцией, встроенной в Python, которая, по-видимому, является ее наиболее простой заменой.
Сравните Идентификатор Объекта с Его Хэшем
Вероятно, одной из самых простых реализаций хэш-функции, которые только можно вообразить в Python, является встроенная id(), которая сообщает вам идентификатор объекта. В стандартном интерпретаторе Python идентификатор совпадает с адресом памяти объекта, выраженным в виде целого числа:

>>> id("Lorem")
139836146678832


 Функция id() обладает большинством необходимых свойств хэш-функции. В конце концов, она очень быстрая и работает с любыми входными данными. Она возвращает целое число фиксированного размера детерминированным образом. В то же время, вы не сможете легко восстановить исходный объект на основе его адреса в памяти. Сами адреса памяти неизменяемы в течение всего времени существования объекта и в некоторой степени рандомизируются между запусками интерпретатора.
Итак, почему же тогда Python настаивает на использовании другой функции для хэширования?
Прежде всего, назначение id() отличается от hash(), поэтому другие дистрибутивы Python могут реализовывать идентификацию альтернативными способами. Во-вторых, адреса памяти предсказуемы без равномерного распределения, что небезопасно и крайне неэффективно для хэширования. Наконец, одинаковые объекты, как правило, должны выдавать один и тот же хэш-код, даже если они имеют разные идентификаторы.
 Примечание: Позже вы узнаете больше о контракте между равенством значений и соответствующими хэш-кодами.
Покончив с этим, вы, наконец, можете подумать о создании своей собственной хэш-функции.
Создайте свою собственную хэш-функцию
Разработать хэш-функцию, отвечающую всем требованиям, с нуля сложно. Как упоминалось ранее, в следующем разделе вы будете использовать встроенную функцию hash() для создания прототипа вашей хэш-таблицы. Однако попытка создать хэш-функцию с нуля - отличный способ узнать, как она работает. К концу этого раздела у вас будет только элементарная хэш-функция, которая далека от совершенства, но вы получите ценную информацию.
В этом упражнении вы можете сначала ограничиться только одним типом данных и реализовать на его основе грубую хэш-функцию. Например, вы могли бы рассмотреть строки и суммировать порядковые значения отдельных символов в них:

>>> def hash_function(text):
...     return sum(ord(character) for character in text)


Вы выполняете итерацию по тексту, используя генераторное выражение, затем преобразуете каждый отдельный символ в соответствующую  кодовую точку в Юникоде с помощью встроенногов функции ord() и, наконец, суммируйте порядковые значения вместе. Это приведет к выдаче единственного числа для любого заданного текста, предоставленного в качестве аргумента:

>>> hash_function("Lorem")
511

>>> hash_function("Loren")
512

>>> hash_function("Loner")
512


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

>>> def hash_function(key):
...     return sum(ord(character) for character in str(key))

>>> hash_function("Lorem")
511

>>> hash_function(3.14)
198

>>> hash_function(True)
416


Вы можете вызвать hash_function() с аргументом любого типа данных, включая строку, число с плавающей запятой или логическое значение.
Обратите внимание, что эта реализация будет настолько же хороша, насколько и соответствующее строковое представление. Некоторые объекты могут не иметь текстового представления, подходящего для приведенного выше кода. В частности, хорошим примером являются экземпляры пользовательского класса без надлежащим образом реализованных специальных методов .__str__() и .__repr__(). Кроме того, вы больше не сможете различать различные типы данных:

>>> hash_function("3.14")
198

>>> hash_function(3.14)
198


На самом деле, вы бы хотели рассматривать строку "3.14" и число с плавающей запятой 3.14 как разные объекты с разными хэш-кодами. Один из способов смягчить это - заменить str() на repr(),, который содержит представление строк с дополнительными апострофами ('):

>>> repr("3.14")
"'3.14'"

>>> repr(3.14)
'3.14'


Это в некоторой степени улучшит вашу хэш-функцию:

>>> def hash_function(key):
...     return sum(ord(character) for character in repr(key))

>>> hash_function("3.14")
276

>>> hash_function(3.14)
198


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

>>> def hash_function(key):
...     return sum(
...         index * ord(character)
...         for index, character in enumerate(repr(key), start=1)
...     )


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

>>> hash_function("Tiny")
1801

>>> hash_function("This has a somewhat medium length.")
60919

>>> hash_function("This is very long and slow!" * 1_000_000)
33304504435500117


Вы всегда можете решить проблему неограниченного роста, сопоставив модуль (%) вашего хэш-кода с известным максимальным размером, например, сто:

>>> hash_function("Tiny") % 100
1

>>> hash_function("This has a somewhat medium length.") % 100
19

>>> hash_function("This is very long and slow!" * 1_000_000) % 100
17


Помните, что выбор меньшего количества хэш-кодов увеличивает вероятность коллизий с хэш-кодами. Если вы заранее не знаете количество вводимых значений, то лучше отложить это решение на потом, если сможете. Вы также можете установить ограничение на свои хэш-коды, установив разумное максимальное значение, например, sys.maxsize, которое представляет собой наибольшее значение целых чисел, изначально поддерживаемых в Python.
Не обращая внимания на низкую скорость работы функции, вы заметите еще одну странную проблему с вашей хэш-функцией. Это приводит к неоптимальному распределению хэш-кодов с помощью кластеризации и не позволяет использовать все доступные интервалы:

>>> from hash_distribution import plot, distribute
>>> from string import printable

>>> plot(distribute(printable, 6, hash_function))
  0 ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■   (31)
  1 ■■■■                              (4)
  2 ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■   (31)
  4 ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ (33)
  5 ■                                 (1)


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

>>> hash_function("a"), hash_function("b"), hash_function("c")
(350, 352, 354)

>>> def hash_function(key):
...     return sum(
...         index * ord(character)
...         for index, character in enumerate(repr(key).lstrip("'"), 1)
...     )

>>> hash_function("a"), hash_function("b"), hash_function("c")
(175, 176, 177)

>>> plot(distribute(printable, 6, hash_function))
  0 ■■■■■■■■■■■■■■■■   (16)
  1 ■■■■■■■■■■■■■■■■   (16)
  2 ■■■■■■■■■■■■■■■    (15)
  3 ■■■■■■■■■■■■■■■■■■ (18)
  4 ■■■■■■■■■■■■■■■■■  (17)
  5 ■■■■■■■■■■■■■■■■■■ (18)


Вызов str.lstrip() повлияет на строку только в том случае, если она начинается с указанного префикса strip.
Естественно, вы можете продолжать совершенствовать свою хэш-функцию и дальше. Если вам интересно узнать о реализации hash() для строк и байтовых последовательностей в Python, то в настоящее время в нем используется алгоритм SipHash, который может вернуться к модифицированной версии FNV, если первый недоступен. Чтобы узнать, какой алгоритм хэширования использует ваш интерпретатор Python, перейдите к модулю sys:

>>> import sys
>>> sys.hash_info.algorithm
'siphash24'


На данный момент вы довольно хорошо представляете себе хэш-функцию, как она должна работать и с какими трудностями вы можете столкнуться при ее реализации. В следующих разделах вы будете использовать хэш-функцию для построения хэш-таблицы. Выбор конкретного алгоритма хэширования будет влиять на производительность хэш-таблицы. Опираясь на эти знания, вы можете смело использовать встроенный hash().
Создайте прототип хэш-таблицы на Python с помощью TDD
В этом разделе вы создадите пользовательский класс, представляющий структуру данных хэш-таблицы. Он не будет поддерживаться словарем Python, поэтому вы можете создать хэш-таблицу с нуля и попрактиковаться в том, чему вы уже научились. В то же время вы будете моделировать свою реализацию по образцу встроенного словаря, имитируя его наиболее важные функции.
 Примечание: Это всего лишь краткое напоминание о том, что внедрение хэш-таблицы - это всего лишь упражнение и образовательный инструмент, который расскажет вам о проблемах, решаемых этой структурой данных. Как и при кодировании пользовательской хэш-функции ранее, реализация хэш-таблицы на чистом Python не имеет практического применения в реальных приложениях.
Ниже приведен список требований высокого уровня к вашей хэш-таблице, которые вы будете выполнять сейчас. К концу этого раздела ваша хэш-таблица будет обладать следующими  основными функциями. Это позволит вам:

Создайте пустую хэш-таблицу
Вставьте пару ключ-значение в хэш-таблицу
Удалить пару ключ-значение из хэш-таблицы
Найти значение по ключу в хэш-таблице
Обновите значение, связанное с существующим ключом
Проверьте, есть ли в хэш-таблице заданный ключ

В дополнение к этому вы реализуете несколько несущественных, но все же полезных функций. В частности, вы должны уметь:

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

При реализации этих функций вы будете активно использовать разработку на основе тестирования, постепенно добавляя дополнительные функции в свою хэш-таблицу. Обратите внимание, что ваш прототип будет охватывать только основы. Чуть позже в этом руководстве вы узнаете, как справиться с некоторыми более сложными угловыми ситуациями. В частности, в этом разделе не будет рассказано о том, как:

Устранить коллизии хэш-кода
Сохранить порядок вставки
Динамически изменять размер хэш-таблицы
Рассчитать коэффициент загрузки

Не стесняйтесь использовать дополнительные материалы в качестве контрольных точек, если вы застряли или хотите пропустить некоторые промежуточные этапы рефакторинга. Каждый подраздел заканчивается полным этапом внедрения и соответствующими тестами, с которых вы можете начать. Перейдите по следующей ссылке и загрузите вспомогательные материалы с полным исходным кодом и промежуточными шагами, использованными в этом руководстве:
 Исходный код:  Нажмите здесь, чтобы загрузить исходный код, который вы будете использовать для создания хэш-таблицы на Python.
Пройдите ускоренный курс по разработке на основе тестирования
Теперь, когда вы знаете высокоуровневые свойства хэш-функции и ее назначение, вы можете применить подход к разработке на основе тестирования для построения хэш-таблицы. Если вы никогда раньше не пробовали этот метод программирования, то он сводится к трем шагам, которые вы, как правило, повторяете в цикле:

🟥 Red: Придумайте один тестовый пример и автоматизируйте его, используя  модульное тестирование фреймворк по вашему выбору. На этом этапе ваш тест завершится неудачей, но это нормально. Участники тестирования обычно обозначают неудачный тест красным цветом, отсюда и название этой фазы цикла.
🟩 Зеленый: Реализуйте самый минимум, чтобы ваш тест прошел успешно, но не более того! Это обеспечит более высокий  охват кода и избавит вас от написания избыточного кода. После этого отчет о тестировании загорится приятным зеленым цветом.
♻️ Рефакторинг: При необходимости измените свой код, не меняя его поведения, пока все тестовые примеры по-прежнему проходят проверку. Вы можете использовать это как возможность устранить дублирование и улучшить читаемость вашего кода.

Python поставляется с пакетом unittest "из коробки", но сторонняя библиотека pytest имеет, возможно, более низкую степень освоения, так что вы будете использовать это в этом руководстве вместо этого. Продолжайте и установите pytest в свою виртуальную среду прямо сейчас:


Окна


Linux + macOS



(venv) C:\> python -m pip install pytest



(venv) $ python -m pip install pytest


Помните, что вы можете проверить каждый этап реализации с помощью нескольких контрольных точек. Затем создайте файл с именем test_hashtable.py и определите в нем фиктивную тестовую функцию, чтобы проверить, примет ли ее pytest:

# test_hashtable.py

def test_should_always_pass():
    assert 2 + 2 == 22, "This is just a dummy test"


Фреймворк использует встроенную инструкцию assert для запуска ваших тестов и составления отчета об их результатах. Это означает, что вы можете просто использовать обычный синтаксис Python, не импортируя никаких специальных API до тех пор, пока это не станет абсолютно необходимым. Он также распознает тестовые файлы и тестовые функции, если их имена начинаются с префикса test.
Оператор assert принимает логическое выражение в качестве аргумента, за которым следует необязательное сообщение об ошибке. Когда условие принимает значение True, ничего не происходит, как если бы никакого утверждения вообще не было. В противном случае Python вызовет AssertionError и отобразит сообщение в стандартном потоке ошибок (stderr). Тем временем pytest перехватывает ошибки в утверждениях и строит отчет на их основе.
Теперь откройте терминал, измените свой рабочий каталог на тот, в котором вы сохранили тестовый файл, и запустите команду pytest без каких-либо аргументов. Результат должен выглядеть примерно так:


Окна


Linux + macOS



(venv) C:\> python -m pytest
=========================== test session starts ===========================
platform win32 -- Python 3.10.2, pytest-6.2.5, pluggy-1.0.0
rootdir: C:\Users\realpython\hashtable
collected 1 item

test_hashtable.py F                                                 [100%]

================================ FAILURES =================================
_________________________ test_should_always_pass _________________________

    def test_should_always_pass():
>       assert 2 + 2 == 22, "This is just a dummy test"
E       AssertionError: This is just a dummy test
E       assert (2 + 2) == 22

test_hashtable.py:4: AssertionError
========================= short test summary info =========================
FAILED test_hashtable.py::test_should_always_pass - AssertionError: This...
============================ 1 failed in 0.03s ============================



(venv) $ pytest
=========================== test session starts ===========================
platform linux -- Python 3.10.0, pytest-6.2.5, py-1.11.0, pluggy-1.0.0
rootdir: /home/realpython/hashtable
collected 1 item

test_hashtable.py F                                                 [100%]

================================ FAILURES =================================
_________________________ test_should_always_pass _________________________

    def test_should_always_pass():
>       assert 2 + 2 == 22, "This is just a dummy test"
E       AssertionError: This is just a dummy test
E       assert (2 + 2) == 22

test_hashtable.py:4: AssertionError
========================= short test summary info =========================
FAILED test_hashtable.py::test_should_always_pass - AssertionError: This...
============================ 1 failed in 0.03s ============================


Ого. В вашем тесте произошел сбой. Чтобы найти основную причину, увеличьте детализацию выходных данных pytest, добавив к команде флаг -v. Теперь вы можете точно определить, в чем заключается проблема:

    def test_should_always_pass():
>       assert 2 + 2 == 22, "This is just a dummy test"
E       AssertionError: This is just a dummy test
E       assert 4 == 22
E         +4
E         -22


Выходные данные показывают, какими были фактические и ожидаемые значения для неудачного утверждения. В этом случае при сложении двух плюс два получается четыре, а не двадцать два. Вы можете исправить код, исправив ожидаемое значение:

# test_hashtable.py

def test_should_always_pass():
    assert 2 + 2 == 4, "This is just a dummy test"


При повторном запуске pytest сбоев в тестировании больше быть не должно:


Окна


Linux + macOS



(venv) C:\> python -m pytest
=========================== test session starts ===========================
platform win32 -- Python 3.10.2, pytest-6.2.5, pluggy-1.0.0
rootdir: C:\Users\realpython\hashtable
collected 1 item

test_hashtable.py .                                                 [100%]

============================ 1 passed in 0.00s ============================



(venv) $ pytest
=========================== test session starts ===========================
platform linux -- Python 3.10.0, pytest-6.2.5, py-1.11.0, pluggy-1.0.0
rootdir: /home/realpython/hashtable
collected 1 item

test_hashtable.py .                                                 [100%]

============================ 1 passed in 0.00s ============================


Вот и все! Вы только что изучили основные шаги по автоматизации тестовых примеров для вашей реализации хэш-таблицы. Естественно, вы можете использовать IDE, такую как PyCharm, или редактор, такой как VS Code, который интегрируется с платформами тестирования, если вам так удобнее. Далее вы собираетесь применить эти новые знания на практике.
Определите пользовательский класс HashTable
Не забудьте выполнить цикл красный-зеленый-рефакторинг, описанный ранее. Таким образом, вы должны начать с определения вашего первого тестового примера. Например, вы должны иметь возможность создать экземпляр новой хэш-таблицы, вызвав гипотетический класс HashTable, импортированный из модуля hashtable. Этот вызов должен возвращать непустой объект:

# test_hashtable.py

from hashtable import HashTable

def test_should_create_hashtable():
    assert HashTable() is not None


На этом этапе ваш тест откажется выполняться из-за невыполненной инструкции import в верхней части файла. В конце концов, вы находитесь в  красной фазе. Красная фаза - это единственное время, когда вам разрешено добавлять новые функции, поэтому продолжайте и создайте еще один модуль с именем hashtable.py и поместите в него определение класса HashTable:

# hashtable.py

class HashTable:
    pass


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

Разделение экрана в PyCharm
Если вам интересна цветовая гамма, изображенная на скриншоте выше, то это тема Дракула. Он доступен для многих редакторов кода, а не только для PyCharm.
Как только запуск pytest завершится успешно, вы можете начать думать о другом тестовом примере, поскольку пока практически нечего перерабатывать. Например, базовая хэш-таблица должна содержать последовательность значений. На этом раннем этапе вы можете предположить, что последовательность имеет фиксированный размер, установленный во время создания хэш-таблицы. Соответствующим образом измените существующий тестовый пример:

# test_hashtable.py

from hashtable import HashTable

def test_should_create_hashtable():
    assert HashTable(size=100) is not None


Вы указываете размер, используя аргумент ключевого слова. Однако, прежде чем добавлять новый код в класс HashTable, повторно запустите тесты, чтобы убедиться, что вы снова перешли в красную фазу. Наблюдение за неудачным тестом может оказаться бесценным. Когда вы позже реализуете фрагмент кода, вы узнаете, удовлетворяет ли он определенной группе тестов или они остаются незатронутыми. В противном случае ваши тесты могут вас обмануть, подтвердив что-то отличное от того, что вы думали!
После подтверждения того, что вы находитесь в красной фазе, объявите метод .__init__() в классе HashTable с ожидаемой сигнатурой, но не реализовывайте его тело:

# hashtable.py

class HashTable:
    def __init__(self, size):
        pass


Бум! Вы снова вернулись к активной фазе, так как насчет небольшого рефакторинга на этот раз? Например, вы могли бы переименовать аргумент size в capacity, если это более наглядно для вас. Не забудьте сначала изменить тестовый пример, затем запустить pytest и всегда обновлять тестируемый код в качестве последнего шага:

# hashtable.py

class HashTable:
    def __init__(self, capacity):
        pass


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

# test_hashtable.py

from hashtable import HashTable

def test_should_create_hashtable():
    assert HashTable(capacity=100) is not None

def test_should_report_capacity():
    assert len(HashTable(capacity=100)) == 100


Для корректной обработки len() необходимо реализовать специальный метод  .__len__() в вашем классе и запомните емкость, предоставляемую через инициализатор класса:

# hashtable.py

class HashTable:
    def __init__(self, capacity):
        self.capacity = capacity

    def __len__(self):
        return self.capacity


Вы можете подумать, что TDD не продвигает вас в правильном направлении. Возможно, вы не так представляли себе реализацию хэш-таблицы. Где последовательность значений, с которой вы начинали? К сожалению, при разработке на основе тестирования часто критикуют использование  маленьких шагов и внесение большого количества исправлений в курс. Поэтому, возможно, это не подходит для проектов, требующих большого количества экспериментов.
С другой стороны, реализация хорошо известной структуры данных, такой как хэш-таблица, является идеальным применением этой методологии разработки программного обеспечения. У вас есть четкие ожидания, которые легко сформулировать в виде тестовых примеров. Вскоре вы сами увидите, что следующий шаг приведет к небольшим изменениям в реализации. Однако не беспокойтесь об этом, потому что совершенствование самого кода менее важно, чем успешное выполнение ваших тестовых примеров.
Поскольку вы продолжаете добавлять новые ограничения в тестовых примерах, вам часто приходится переосмысливать свою реализацию. Например, новая хэш-таблица, вероятно, должна начинаться с пустых ячеек для сохраненных значений:

# test_hashtable.py

# ...

def test_should_create_empty_value_slots():
    assert HashTable(capacity=3).values == [None, None, None]


Другими словами, новая хэш-таблица должна содержать атрибут .values, имеющий запрошенную длину и заполненный элементами None. Кстати, обычно используются такие подробные названия функций, потому что они будут отображаться в вашем отчете о тестировании. Чем более понятными и описательными будут ваши тесты, тем быстрее вы поймете, какая часть нуждается в исправлении.
 Примечание: Как правило, ваши тестовые примеры должны быть как можно более независимыми и атомарными, что обычно означает использование только одного утверждения для каждой функции. Тем не менее, ваши тестовые сценарии иногда могут нуждаться в некоторой настройке или демонтаже. Они также могут включать в себя несколько шагов. В таких случаях принято структурировать вашу функцию на основе так называемого соглашения дано-когда-затем:

def test_should_create_empty_value_slots():
    # Given
    expected_values = [None, None, None]
    hash_table = HashTable(capacity=3)

    # When
    actual_values = hash_table.values

    # Then
    assert actual_values == expected_values


Часть , приведенная в , описывает начальное состояние и предварительные условия для вашего тестового примера, в то время как , когда , представляет действие вашего тестируемого кода, и , то  отвечает за утверждение конечного результата.
Это один из многих возможных способов выполнить существующие тесты:

# hashtable.py

class HashTable:
    def __init__(self, capacity):
        self.values = capacity * [None]

    def __len__(self):
        return len(self.values)


Вы заменяете атрибут .capacity списком требуемой длины, содержащим только None элемента. Умножение числа на список или наоборот - это быстрый способ заполнить этот список заданным значением или значениями. Кроме этого, вы обновляете специальный метод .__len__(), чтобы все тесты прошли успешно.
 Примечание: Длина словаря Python соответствует фактическому количеству хранимых пар ключ-значение, а не его внутреннему объему. Вскоре вы достигнете аналогичного эффекта.
Теперь, когда вы познакомились с TDD, пришло время углубиться и добавить остальные функции в вашу хэш-таблицу.
Вставьте пару Ключ-значение
Теперь, когда вы можете создать хэш-таблицу, пришло время предоставить ей некоторые возможности для хранения. Традиционная хэш-таблица поддерживается массивом, способным хранить только один тип данных. Из-за этого реализации хэш-таблиц на многих языках, таких как Java, требуют, чтобы вы заранее объявляли тип их ключей и значений:

Map<String, Integer> phonesByNames = new HashMap<>();


Например, эта конкретная хэш-таблица преобразует строки в целые числа. Однако, поскольку массивы не являются встроенными в Python, вы продолжите использовать вместо них список. В качестве побочного эффекта ваша хэш-таблица сможет принимать произвольные типы данных как для ключей, так и для значений, точно так же, как в Python dict.
 Примечание: В Python есть эффективная коллекция array, но она предназначена только для числовых значений. Иногда это может оказаться удобным для обработки необработанных двоичных данных.
Теперь добавьте еще один тестовый пример для вставки пар ключ-значение в вашу хэш-таблицу, используя знакомый синтаксис квадратных скобок:

# test_hashtable.py

# ...

def test_should_insert_key_value_pairs():
    hash_table = HashTable(capacity=100)

    hash_table["hola"] = "hello"
    hash_table[98.6] = 37
    hash_table[False] = True

    assert "hello" in hash_table.values
    assert 37 in hash_table.values
    assert True in hash_table.values


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

# hashtable.py

class HashTable:
    def __init__(self, capacity):
        self.values = capacity * [None]

    def __len__(self):
        return len(self.values)

    def __setitem__(self, key, value):
        self.values.append(value)


Он полностью игнорирует ключ и просто добавляет значение в правый конец списка, увеличивая его длину. Вы можете сразу же подумать о другом тестовом примере. Вставка элементов в хэш-таблицу не должна увеличивать ее размер. Аналогично, удаление элемента не должно приводить к уменьшению хэш-таблицы, но вы только принимаете это к сведению, потому что пока нет возможности удалять пары ключ-значение.
 Примечание: Вы также можете написать тест-заполнитель и попросить pytest безоговорочно пропустить его до следующего раза:

import pytest

@pytest.mark.skip
def test_should_not_shrink_when_removing_elements():
    pass


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

# test_hashtable.py

# ...

def test_should_insert_key_value_pairs():
    hash_table = HashTable(capacity=100)

    hash_table["hola"] = "hello"
    hash_table[98.6] = 37
    hash_table[False] = True

    assert "hello" in hash_table.values
    assert 37 in hash_table.values
    assert True in hash_table.values

    assert len(hash_table) == 100


Сейчас вы находитесь в красной фазе, поэтому перепишите свой специальный метод, чтобы всегда сохранять емкость постоянной:

# hashtable.py

class HashTable:
    def __init__(self, capacity):
        self.values = capacity * [None]

    def __len__(self):
        return len(self.values)

    def __setitem__(self, key, value):
        index = hash(key) % len(self)
        self.values[index] = value


Вы преобразуете произвольный ключ в числовое хэш-значение и используете оператор modulo для ограничения результирующего индекса в пределах доступного адресного пространства. Отлично! Ваш отчет о тестировании снова загорается зеленым.
 Примечание: Приведенный выше код основан на встроенной функции Python hash(), которая, как вы уже узнали, содержит элемент рандомизации. Таким образом, ваш тест может завершиться неудачей в редких случаях, когда два ключа случайно выдают идентичный хэш-код. Поскольку позже вы столкнетесь с коллизиями хэш-кода, вы можете отключить рандомизацию хэша или использовать предсказуемое начальное значение при запуске pytest:


Окна


Linux + macOS



(venv) C:\> set PYTHONHASHSEED=128
(venv) C:\> python -m pytest



(venv) $ PYTHONHASHSEED=128 pytest


Убедитесь, что вы выбрали начальное значение хэша, которое не вызовет никаких коллизий в ваших образцах данных. Поиск такого значения может потребовать проб и ошибок. В моем случае значение 128, казалось, работало нормально.
Но, может быть, вы можете придумать какие-нибудь крайние случаи? Как насчет того, чтобы вставить None в вашу хэш-таблицу? Это привело бы к конфликту между допустимым значением и указанным контрольным значением, которое вы выбрали для указания пробелов в вашей хэш-таблице. Этого следует избегать.
Как всегда, начните с написания тестового примера, чтобы выразить желаемое поведение:

# test_hashtable.py

# ...

def test_should_not_contain_none_value_when_created():
    assert None not in HashTable(capacity=100).values


Одним из способов обойти это было бы заменить None в вашем методе .__init__() другим уникальным значением, которое пользователи вряд ли будут вставлять. Например, вы могли бы определить специальную константу, создав совершенно новый объект для представления пробелов в вашей хэш-таблице:

# hashtable.py

BLANK = object()

class HashTable:
    def __init__(self, capacity):
        self.values = capacity * [BLANK]

    # ...


Вам нужен только один пустой экземпляр, чтобы пометить слоты как пустые. Естественно, вам потребуется обновить старый тестовый пример, чтобы вернуться к зеленой фазе:

# test_hashtable.py

from hashtable import HashTable, BLANK

# ...

def test_should_create_empty_value_slots():
    assert HashTable(capacity=3).values == [BLANK, BLANK, BLANK]

# ...


Затем напишите положительный тестовый пример, использующий  счастливый путь для обработки вставки значения None:

def test_should_insert_none_value():
    hash_table = HashTable(capacity=100)
    hash_table["key"] = None
    assert None in hash_table.values


Вы создаете пустую хэш-таблицу с сотней ячеек и вставляете None, связанный с некоторым произвольным ключом. Это должно сработать как по маслу, если вы внимательно следовали инструкциям до сих пор. Если нет, то ознакомьтесь с сообщениями об ошибках, поскольку они часто содержат подсказки о том, что пошло не так. В качестве альтернативы, ознакомьтесь с примером кода, доступным для скачивания по этой ссылке:
 Исходный код:  Нажмите здесь, чтобы загрузить исходный код, который вы будете использовать для создания хэш-таблицы на Python.
В следующем подразделе вы добавите возможность извлекать значения по связанным с ними ключам.
Найдите значение по ключу
Чтобы извлечь значение из хэш-таблицы, вам потребуется использовать тот же синтаксис квадратных скобок, что и раньше, только без использования оператора присваивания. Вам также понадобится образец хэш-таблицы. Чтобы избежать дублирования одного и того же установочного кода в отдельных тестовых примерах в вашем наборе тестов, вы можете поместить его в  тестовый набор, предоставляемый pytest:

# test_hashtable.py

import pytest

# ...

@pytest.fixture
def hash_table():
    sample_data = HashTable(capacity=100)
    sample_data["hola"] = "hello"
    sample_data[98.6] = 37
    sample_data[False] = True
    return sample_data

def test_should_find_value_by_key(hash_table):
    assert hash_table["hola"] == "hello"
    assert hash_table[98.6] == 37
    assert hash_table[False] is True


Тестовое приспособление - это функция, аннотируемая с помощью @pytest.fixture декоратора. Он возвращает примеры данных для ваших тестовых примеров, таких как хэш-таблица, заполненная известными ключами и значениями. Ваш pytest автоматически вызовет эту функцию для вас и введет ее результат в любую тестовую функцию, которая объявляет аргумент с тем же именем, что и ваш fixture. В этом случае тестовая функция ожидает hash_table аргумент, который соответствует имени вашего устройства.
Чтобы иметь возможность находить значения по ключу, вы можете реализовать поиск элемента с помощью другого специального метода, называемого .__getitem__() в вашем классе HashTable:

# hashtable.py

BLANK = object()

class HashTable:
    def __init__(self, capacity):
        self.values = capacity * [BLANK]

    def __len__(self):
        return len(self.values)

    def __setitem__(self, key, value):
        index = hash(key) % len(self)
        self.values[index] = value

    def __getitem__(self, key):
        index = hash(key) % len(self)
        return self.values[index]


Вы вычисляете индекс элемента на основе хэш-кода предоставленного ключа и возвращаете все, что находится под этим индексом. Но как насчет отсутствующих ключей? На данный момент вы можете возвращать пустой экземпляр, если данный ключ ранее не использовался, что не так уж и полезно. Чтобы воспроизвести то, как Python dict работал бы в таком случае, вы должны создать исключение KeyError вместо этого:

# test_hashtable.py

# ...

def test_should_raise_error_on_missing_key():
    hash_table = HashTable(capacity=100)
    with pytest.raises(KeyError) as exception_info:
        hash_table["missing_key"]
    assert exception_info.value.args[0] == "missing_key"


Вы создаете пустую хэш-таблицу и пытаетесь получить доступ к одному из ее значений с помощью отсутствующего ключа. Платформа pytest включает специальную конструкцию для тестирования исключений. Как указано выше, вы используете pytest.raises диспетчер контекста, чтобы ожидать определенного типа исключения в следующем блоке кода. Обработка этого случая заключается в добавлении  условного оператора к вашему методу доступа:

# hashtable.py

# ...

class HashTable:
    # ...

    def __getitem__(self, key):
        index = hash(key) % len(self)
        value = self.values[index]
        if value is BLANK:
            raise KeyError(key)
        return value


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

# test_hashtable.py

# ...

def test_should_find_key(hash_table):
    assert "hola" in hash_table

def test_should_not_find_key(hash_table):
    assert "missing_key" not in hash_table


В обоих тестовых примерах используются преимущества тестового набора, который вы подготовили ранее, и проверяется .__contains__() специальный метод, который вы можете реализовать следующим образом:

# hashtable.py

# ...

class HashTable:
    # ...

    def __contains__(self, key):
        try:
            self[key]
        except KeyError:
            return False
        else:
            return True


Когда при обращении к данному ключу возникает KeyError, вы перехватываете это исключение и возвращаете False, чтобы указать на отсутствующий ключ. В противном случае вы объединяете try ... except block с предложением else и возвращаете True.  Обработка исключений великолепна, но иногда это может быть неудобно, поэтому dict.get() позволяет указать необязательное значение по умолчанию. Вы можете повторить то же самое в своей пользовательской хэш-таблице:

# test_hashtable.py

# ...

def test_should_get_value(hash_table):
    assert hash_table.get("hola") == "hello"

def test_should_get_none_when_missing_key(hash_table):
    assert hash_table.get("missing_key") is None

def test_should_get_default_value_when_missing_key(hash_table):
    assert hash_table.get("missing_key", "default") == "default"

def test_should_get_value_with_default(hash_table):
    assert hash_table.get("hola", "default") == "hello"


Код .get() выглядит аналогично специальному методу, который вы только что реализовали:

# hashtable.py

# ...

class HashTable:
    # ...

    def get(self, key, default=None):
        try:
            return self[key]
        except KeyError:
            return default


Вы пытаетесь вернуть значение, соответствующее предоставленному ключу. В случае исключения вы возвращаете значение по умолчанию, которое является необязательным аргументом. Когда пользователь оставляет его неопределенным, то он равен None.
Для полноты картины в следующем подразделе вы добавите возможность удаления пары ключ-значение из вашей хэш-таблицы.
Удалить пару Ключ-значение
Словари Python позволяют удалять ранее вставленные пары ключ-значение с помощью встроенного ключевого слова del, которое удаляет информацию как о ключе, так и о значении. Вот как это могло бы работать с вашей хэш-таблицей:

# test_hashtable.py

# ...

def test_should_delete_key_value_pair(hash_table):
    assert "hola" in hash_table
    assert "hello" in hash_table.values

    del hash_table["hola"]

    assert "hola" not in hash_table
    assert "hello" not in hash_table.values


Сначала вы проверяете, есть ли в образце хэш-таблицы нужные ключ и значение. Затем вы удаляете оба, указывая только ключ, и повторяете утверждения, но с перевернутыми ожиданиями. Вы можете выполнить этот тест следующим образом:

# hashtable.py

# ...

class HashTable:
    # ...

    def __delitem__(self, key):
        index = hash(key) % len(self)
        del self.values[index]


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

# test_hashtable.py

# ...

def test_should_delete_key_value_pair(hash_table):
    assert "hola" in hash_table
    assert "hello" in hash_table.values
    assert len(hash_table) == 100

    del hash_table["hola"]

    assert "hola" not in hash_table
    assert "hello" not in hash_table.values
    assert len(hash_table) == 100


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

# hashtable.py

# ...

class HashTable:
    # ...

    def __delitem__(self, key):
        index = hash(key) % len(self)
        self.values[index] = BLANK


Учитывая, что вы снова вступаете в новую фазу, вы можете воспользоваться этой возможностью и потратить некоторое время на рефакторинг. Одна и та же формула индекса появляется три раза в разных местах. Вы можете извлечь ее и упростить код:

# hashtable.py

# ...

class HashTable:
    # ...

    def __delitem__(self, key):
        self.values[self._index(key)] = BLANK

    def __setitem__(self, key, value):
        self.values[self._index(key)] = value

    def __getitem__(self, key):
        value = self.values[self._index(key)]
        if value is BLANK:
            raise KeyError(key)
        return value

    # ...

    def _index(self, key):
        return hash(key) % len(self)


Внезапно, после применения всего лишь этого небольшого изменения, возникает закономерность. Удаление элемента эквивалентно вставке пустого объекта. Итак, вы можете переписать процедуру удаления, чтобы воспользоваться преимуществами метода mutator:

# hashtable.py

# ...

class HashTable:
    # ...

    def __delitem__(self, key):
        self[key] = BLANK

    # ...


Присвоение значения с помощью синтаксиса квадратных скобок делегирует методу .__setitem__(). Ладно, на данный момент достаточно рефакторинга. На данном этапе гораздо важнее подумать о других тестовых примерах. Например, что происходит, когда вы запрашиваете удаление отсутствующего ключа? В Python dict в этом случае возникает исключение KeyError, поэтому вы можете сделать то же самое:

# hashtable.py

# ...

def test_should_raise_key_error_when_deleting(hash_table):
    with pytest.raises(KeyError) as exception_info:
        del hash_table["missing_key"]
    assert exception_info.value.args[0] == "missing_key"


 Выполнить этот тестовый пример относительно просто, поскольку вы можете положиться на код, который вы написали при реализации оператора in:

# hashtable.py

# ...

class HashTable:
    # ...

    def __delitem__(self, key):
        if key in self:
            self[key] = BLANK
        else:
            raise KeyError(key)

    # ...


Если вы найдете ключ в своей хэш-таблице, вы замените связанное с ним значение контрольным значением, чтобы удалить эту пару. В противном случае вы создадите исключение. Итак, осталось рассмотреть еще одну базовую операцию с хэш-таблицей, которую вы будете выполнять далее.
Обновить значение существующей пары
Метод insertion уже должен позаботиться об обновлении пары ключ-значение, поэтому вам нужно только добавить соответствующий тестовый пример и проверить, работает ли он должным образом:

# test_hashtable.py

# ...

def test_should_update_value(hash_table):
    assert hash_table["hola"] == "hello"

    hash_table["hola"] = "hallo"

    assert hash_table["hola"] == "hallo"
    assert hash_table[98.6] == 37
    assert hash_table[False] is True
    assert len(hash_table) == 100


После изменения значения hello существующего ключа и изменения его на hallo вы также проверяете, есть ли другое значение ключа пары, а также длина хэш-таблицы остаются неизменными. Это оно. У вас уже есть базовая реализация хэш-таблицы, но несколько дополнительных функций, которые относительно дешевы в реализации, все еще отсутствуют.
Получаем пары Ключ-значение
Пришло время обратиться к слону в комнате. Словари Python позволяют выполнять итерацию по их ключам , значениям или парам ключ-значение, называемым элементами. Однако ваша хэш-таблица на самом деле представляет собой всего лишь список значений с причудливой индексацией поверх него. Если вы когда-нибудь захотите восстановить исходные ключи, помещенные в вашу хэш-таблицу, то вам не повезет, потому что текущая реализация хэш-таблицы никогда их не запомнит.
В этом подразделе вы проведете масштабный рефакторинг вашей хэш-таблицы, чтобы добавить возможность сохранения ключей и значений. Имейте в виду, что потребуется выполнить несколько шагов, и в результате многие тесты начнут завершаться неудачно. Если вы хотите пропустить эти промежуточные шаги и увидеть эффект, то переходите к защитному копированию.
Подождите минутку. Вы продолжаете читать о парах ключ-значение в этом руководстве, так почему бы не заменить значения кортежами? В конце концов, кортежи в Python понятны. Еще лучше, если вы могли бы использовать именованные кортежи, чтобы воспользоваться поиском именованных элементов в них. Но сначала вам нужно придумать тест.
 Примечание: При разработке тестового примера не забудьте сосредоточиться на высокоуровневой функциональности, ориентированной на пользователя. Не пытайтесь тестировать фрагмент кода, который вы можете предвидеть, основываясь на своем опыте программиста или на интуиции. Именно тесты должны в конечном итоге определять вашу реализацию в TDD, а не наоборот.
Прежде всего, вам понадобится еще один атрибут в вашем классе HashTable для хранения пар ключ-значение:

# test_hashtable.py

# ...

def test_should_return_pairs(hash_table):
    assert ("hola", "hello") in hash_table.pairs
    assert (98.6, 37) in hash_table.pairs
    assert (False, True) in hash_table.pairs


Порядок пар ключ-значение на данном этапе не имеет значения, поэтому вы можете предположить, что они могут отображаться в любом порядке каждый раз, когда вы их запрашиваете. Однако вместо того, чтобы вводить в класс еще одно поле, вы могли бы повторно использовать .values, переименовав его в .pairs и внеся другие необходимые изменения. Есть несколько вариантов. Просто имейте в виду, что это временно приведет к сбою некоторых тестов, пока вы не исправите реализацию.
 Примечание: Если вы используете редактор кода, то вы можете удобно переименовать переменную или элемент класса одним нажатием кнопки, используя возможности рефакторинга. В PyCharm, например, вы можете щелкнуть правой кнопкой мыши по переменной, выбрать Рефакторинг из контекстного меню, а затем Переименовать.... Или вы можете использовать соответствующее сочетание клавиш:

Рефакторинг переименования в PyCharm
Это самый простой и надежный способ изменить имя переменной в вашем проекте. Редактор кода обновит все ссылки на переменные в файлах вашего проекта.
Когда вы переименуете .values в .pairs в hashtable.py и test_hashtable.py, вам также потребуется обновить специальный метод .__setitem__(). В частности, теперь он должен хранить кортежи ключа и связанного с ним значения:

# hashtable.py

# ...

class HashTable:
    # ...

    def __setitem__(self, key, value):
        self.pairs[self._index(key)] = (key, value)


Вставка элемента в вашу хэш-таблицу преобразует ключ и значение в кортеж, а затем помещает этот кортеж с нужным индексом в ваш список пар. Обратите внимание, что изначально ваш список будет содержать только пустые объекты, а не кортежи, поэтому в вашем списке пар вы будете использовать два разных типа данных. Один из них - кортеж, в то время как другой может быть любым, кроме кортежа, для обозначения пустого места.
Из-за этого вам больше не нужна какая-либо специальная контрольная константа, чтобы пометить слот как пустой. Вы можете безопасно удалить свою константу BLANK и при необходимости заменить ее простой константой None, так что продолжайте и сделайте это прямо сейчас.
 Примечание: С удалением кода поначалу может быть трудно смириться, но чем меньше, тем лучше! Как вы можете видеть, разработка на основе тестирования иногда может заставить вас ходить по кругу.
Вы можете сделать еще один шаг назад, чтобы восстановить контроль над удалением элемента:

# hashtable.py

# ...

class HashTable:
    # ...

    def __delitem__(self, key):
        if key in self:
            self.pairs[self._index(key)] = None
        else:
            raise KeyError(key)


К сожалению, ваш метод .__delitem__() больше не может использовать синтаксис квадратных скобок, поскольку это привело бы к переносу любого значения sentinel, которое вы выбрали, в ненужный кортеж. Здесь вы должны использовать явный оператор присваивания, чтобы избежать излишне сложной логики в будущем.
Последним важным элементом головоломки является обновление метода .__getitem__():

# hashtable.py

# ...

class HashTable:
    # ...

    def __getitem__(self, key):
        pair = self.pairs[self._index(key)]
        if pair is None:
            raise KeyError(key)
        return pair[1]


Вы просматриваете индекс, ожидая найти пару ключ-значение. Если вы вообще ничего не получаете, вы создаете исключение. С другой стороны, если вы видите что-то интересное, вы берете второй элемент кортежа с индексом один, который соответствует отображаемому значению. Однако вы можете записать это более элегантно, используя именованный кортеж, как предлагалось ранее:

# hashtable.py

from typing import NamedTuple, Any

class Pair(NamedTuple):
    key: Any
    value: Any

class HashTable:
    # ...

    def __setitem__(self, key, value):
        self.pairs[self._index(key)] = Pair(key, value)

    def __getitem__(self, key):
        pair = self.pairs[self._index(key)]
        if pair is None:
            raise KeyError(key)
        return pair.value

    # ...


Класс Pair состоит из атрибутов .key и .value, которые могут принимать значения любого типа данных. Одновременно ваш класс наследует все свойства обычного кортежа, поскольку он расширяет родительский NamedTuple. Обратите внимание, что вы должны явно вызвать Pair() для вашего ключа и значения в методе .__setitem__(), чтобы воспользоваться доступом к именованному атрибуту в .__getitem__().
 Примечание: Несмотря на использование пользовательского типа данных для представления пар ключ-значение, вы можете написать свои тесты так, чтобы они содержали либо экземпляры Pair, либо обычные кортежи, благодаря совместимости обоих типов.
Естественно, на данный момент вам необходимо обновить несколько тестовых примеров, прежде чем отчет снова станет зеленым. Не торопитесь и внимательно просмотрите свой набор тестов. В качестве альтернативы, если вы чувствуете, что застряли, ознакомьтесь с кодом из вспомогательных материалов или загляните сюда:

# test_hashtable.py

# ...

def test_should_insert_key_value_pairs():
    hash_table = HashTable(capacity=100)

    hash_table["hola"] = "hello"
    hash_table[98.6] = 37
    hash_table[False] = True

    assert ("hola", "hello") in hash_table.pairs
    assert (98.6, 37) in hash_table.pairs
    assert (False, True) in hash_table.pairs

    assert len(hash_table) == 100

# ...

def test_should_delete_key_value_pair(hash_table):
    assert "hola" in hash_table
    assert ("hola", "hello") in hash_table.pairs
    assert len(hash_table) == 100

    del hash_table["hola"]

    assert "hola" not in hash_table
    assert ("hola", "hello") not in hash_table.pairs
    assert len(hash_table) == 100


Будет еще один тестовый пример, который требует особого внимания. В частности, речь идет о проверке того, что в пустой хэш-таблице при создании не было значений None. Вы только что заменили список значений списком пар. Чтобы снова найти значения, вы можете использовать  список для понимания, например, такой:

# test_hashtable.py

# ...

def test_should_not_contain_none_value_when_created():
    hash_table = HashTable(capacity=100)
    values = [pair.value for pair in hash_table.pairs if pair]
    assert None not in values


Если вы беспокоитесь о том, что в тестовом примере будет слишком много логики, то вы будете абсолютно правы. В конце концов, вы хотите протестировать поведение хэш-таблицы. Но пока не беспокойтесь об этом. Вскоре вы вернетесь к этому тестовому примеру.
Использовать защитное копирование
Как только вы вернетесь к "зеленой" фазе, попробуйте разобраться с возможными угловыми вариантами. Например, .pairs отображается как общедоступный атрибут, который любой может намеренно или непреднамеренно изменить. На практике методы доступа никогда не должны допускать утечки информации из вашей внутренней реализации, но должны создавать  защитные копии для защиты изменяемых атрибутов от внешних изменений:

# test_hashtable.py

# ...

def test_should_return_copy_of_pairs(hash_table):
    assert hash_table.pairs is not hash_table.pairs


Всякий раз, когда вы запрашиваете пары ключ-значение из хэш-таблицы, вы ожидаете получить совершенно новый объект с уникальным идентификатором. Вы можете скрыть приватное поле за  свойством Python, поэтому создайте его и замените все ссылки на .pairs на ._pairs только в вашем HashTable классе. Начальное подчеркивание - это стандартное соглашение об именовании в Python, которое указывает на внутреннюю реализацию:

# hashtable.py

# ...

class HashTable:
    def __init__(self, capacity):
        self._pairs = capacity * [None]

    def __len__(self):
        return len(self._pairs)

    def __delitem__(self, key):
        if key in self:
            self._pairs[self._index(key)] = None
        else:
            raise KeyError(key)

    def __setitem__(self, key, value):
        self._pairs[self._index(key)] = Pair(key, value)

    def __getitem__(self, key):
        pair = self._pairs[self._index(key)]
        if pair is None:
            raise KeyError(key)
        return pair.value

    def __contains__(self, key):
        try:
            self[key]
        except KeyError:
            return False
        else:
            return True

    def get(self, key, default=None):
        try:
            return self[key]
        except KeyError:
            return default

    @property
    def pairs(self):
        return self._pairs.copy()

    def _index(self, key):
        return hash(key) % len(self)


Когда вы запрашиваете список пар ключ-значение, хранящихся в вашей хэш-таблице, вы каждый раз получаете их неполную копию. Поскольку у вас не будет ссылки на внутреннее состояние вашей хэш-таблицы, возможные изменения в ее копии не повлияют на нее.
 Примечание: Порядок следования методов класса, к которому вы пришли, может немного отличаться от приведенного в блоке кода, представленном выше. Это нормально, потому что порядок следования методов не имеет значения с точки зрения Python. Однако обычно начинается с статических методов или методов класса, за которыми следует открытый интерфейс вашего класса, на который вы, скорее всего, обратите внимание. Внутренняя реализация, как правило, должна появляться в самом конце.
Чтобы избежать путаницы в коде, рекомендуется организовать методы таким образом, чтобы они напоминали историю. В частности, перед вызываемыми низкоуровневыми функциями следует указывать функции более высокого уровня.
Чтобы еще больше имитировать dict.items() в вашем свойстве, результирующий список пар не должен содержать пустых ячеек. Другими словами, в этом списке не должно быть никаких значений None:

# test_hashtable.py

# ...

def test_should_not_include_blank_pairs(hash_table):
    assert None not in hash_table.pairs


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

# hashtable.py

# ...

class HashTable:
    # ...

    @property
    def pairs(self):
        return [pair for pair in self._pairs if pair]


Вам не нужен явный вызов .copy(), потому что понимание списка создает новый список. Для каждой пары в исходном списке пар ключ-значение вы проверяете, соответствует ли эта конкретная пара действительности, и сохраняете ее в результирующем списке. Однако это приведет к нарушению двух других тестов, которые вам необходимо обновить сейчас:

# test_hashtable.py

# ...

def test_should_create_empty_value_slots():
    assert HashTable(capacity=3)._pairs == [None, None, None]

# ...

def test_should_insert_none_value():
    hash_table = HashTable(100)
    hash_table["key"] = None
    assert ("key", None) in hash_table.pairs


Это не идеально, потому что один из ваших тестов нацелен на внутреннюю реализацию, а не на общедоступные интерфейсы. Тем не менее, такое тестирование известно как тестирование в режиме "белого ящика", которое имеет свое место.
Получить ключи и значения
Помните тестовый пример, который вы изменили, добавив понимание списка для извлечения значений из ваших пар ключ-значение? Ну, вот он снова, если вам нужно освежить память:

# test_hashtable.py

# ...

def test_should_not_contain_none_value_when_created():
    hash_table = HashTable(capacity=100)
    values = [pair.value for pair in hash_table.pairs if pair]
    assert None not in values


Выделенная строка выглядит точно так же, как вам нужно для реализации свойства .values, которое вы ранее заменили на .pairs. Вы можете обновить тестовую функцию, чтобы снова воспользоваться преимуществами .values:

# test_hashtable.py

# ...

def test_should_not_contain_none_value_when_created():
    assert None not in HashTable(capacity=100).values


Может показаться, что это напрасные усилия. Но теперь эти значения вычисляются динамически с помощью свойства getter, тогда как раньше они хранились в списке фиксированного размера. Чтобы выполнить этот тест, вы можете повторно использовать часть его старой реализации, которая использует понимание списка:

# hashtable.py

# ...

class HashTable:
    # ...

    @property
    def values(self):
        return [pair.value for pair in self.pairs]


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

# test_hashtable.py

# ...

def test_should_return_duplicate_values():
    hash_table = HashTable(capacity=100)
    hash_table["Alice"] = 24
    hash_table["Bob"] = 42
    hash_table["Joe"] = 42
    assert [24, 42, 42] == sorted(hash_table.values)


Если у вас есть хэш-таблица с именами и возрастом, например, и у нескольких человек одинаковый возраст, то в .values следует сохранить все повторяющиеся значения возраста. Вы можете отсортировать возрасты, чтобы обеспечить повторяемость тестовых запусков. Хотя этот тестовый пример не требует написания нового кода, он защитит от регрессий .
Стоит проверить ожидаемые значения, их типы и количество. Однако вы не можете сравнивать два списка напрямую, поскольку фактические значения в хэш-таблице могут отображаться в непредсказуемом порядке. Чтобы не нарушать порядок в вашем тесте, вы могли бы преобразовать оба списка в наборы или отсортировать их, как и раньше. К сожалению, наборы удаляют потенциальные дубликаты, в то время как сортировка невозможна, если списки содержат несовместимые типы.
Чтобы надежно проверить, содержат ли два списка абсолютно одинаковые элементы произвольных типов с потенциальными дубликатами, игнорируя их порядок, вы можете использовать следующую идиому Python:

def have_same_elements(list1, list2):
    return all(element in list1 for element in list2)


В нем используется встроенная функция all(), но она довольно подробная. Вероятно, вам лучше использовать плагин pytest-unordered. Не забудьте сначала установить его в свою виртуальную среду:


Окна


Linux + macOS



(venv) C:\> python -m pip install pytest-unordered



(venv) $ python -m pip install pytest-unordered


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

# test_hashtable.py

import pytest
from pytest_unordered import unordered

from hashtable import HashTable

# ...

def test_should_get_values(hash_table):
    assert unordered(hash_table.values) == ["hello", 37, True]


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

# test_hashtable.py

# ...

def test_should_get_values_of_empty_hash_table():
    assert HashTable(capacity=100).values == []

def test_should_return_copy_of_values(hash_table):
    assert hash_table.values is not hash_table.values


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

# test_hashtable.py

# ...

def test_should_get_keys(hash_table):
    assert hash_table.keys == {"hola", 98.6, False}

def test_should_get_keys_of_empty_hash_table():
    assert HashTable(capacity=100).keys == set()

def test_should_return_copy_of_keys(hash_table):
    assert hash_table.keys is not hash_table.keys


В Python нет пустого литерала set, поэтому в этом случае вам придется напрямую вызывать встроенную функцию set(). Реализация соответствующей функции getter будет выглядеть знакомо:

# hashtable.py

# ...

class HashTable:
    # ...

    @property
    def keys(self):
        return {pair.key for pair in self.pairs}


Это похоже на свойство .values. Разница в том, что вы используете фигурные скобки вместо квадратных и ссылаетесь на атрибут .key вместо .value в вашем именованном кортеже. В качестве альтернативы вы могли бы использовать pair[0], если бы захотели, но это было бы менее читабельно.
Это также напоминает вам о необходимости аналогичного тестового примера, который вы пропустили при рассмотрении атрибута .pairs. Имеет смысл вернуть набор пар для обеспечения согласованности:

# test_hashtable.py

# ...

def test_should_return_pairs(hash_table):
    assert hash_table.pairs == {
        ("hola", "hello"),
        (98.6, 37),
        (False, True)
    }

def test_should_get_pairs_of_empty_hash_table():
    assert HashTable(capacity=100).pairs == set()


Таким образом, свойство .pairs отныне также будет использовать заданное значение:

# hashtable.py

# ...

class HashTable:
    # ...

    @property
    def pairs(self):
        return {pair for pair in self._pairs if pair}


Вам не нужно беспокоиться о потере какой-либо информации, потому что каждая пара ключ-значение уникальна. На этом этапе вы снова должны перейти в зеленую фазу.
Обратите внимание, что вы можете воспользоваться свойством .pairs для преобразования вашей хэш-таблицы в обычный старый словарь и использовать .keys и .values для проверки этого:

def test_should_convert_to_dict(hash_table):
    dictionary = dict(hash_table.pairs)
    assert set(dictionary.keys()) == hash_table.keys
    assert set(dictionary.items()) == hash_table.pairs
    assert list(dictionary.values()) == unordered(hash_table.values)


Чтобы не обращать внимания на порядок элементов, не забудьте обернуть ключи словаря и пары ключ-значение наборами перед выполнением сравнения. Напротив, значения вашей хэш-таблицы отображаются в виде списка, поэтому обязательно используйте функцию unordered() для сравнения списков, игнорируя порядок элементов.
Итак, теперь ваша хэш-таблица действительно начинает обретать форму!
Укажите длину хэш-таблицы
Есть одна небольшая деталь, которую вы намеренно оставили неработающей для простоты. Это длина вашей хэш-таблицы, которая в настоящее время показывает максимальную емкость, даже если в ней есть только пустые ячейки. К счастью, для исправления этого не требуется много усилий. Найдите свою функцию с именем test_should_report_capacity(), переименуйте, как показано ниже, и проверьте, равна ли длина пустой хэш-таблицы нулю, а не ста:

# test_hashtable.py

# ...

def test_should_report_length_of_empty_hash_table():
    assert len(HashTable(capacity=100)) == 0


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

# hashtable.py

# ...

class HashTable:
    # ...

    def __len__(self):
        return len(self.pairs)

    # ...


Вы только что убрали начальное подчеркивание из имени переменной. Но это небольшое изменение теперь приводит к внезапному завершению целого ряда тестов с ошибкой, а некоторые из них завершаются неудачей.
 Примечание: Неудачные тесты менее серьезны, поскольку их утверждения оцениваются как False, в то время как ошибки указывают на совершенно неожиданное поведение в вашем коде.
Похоже, что большинство тестовых примеров страдают от одного и того же необработанного исключения из-за деления на ноль при сопоставлении ключа с индексом. Это имеет смысл, потому что ._index() использует длину хэш-таблицы, чтобы найти остаток от деления хэшированного ключа на количество доступных ячеек. Однако теперь длина хэш-таблицы имеет другое значение. Вместо этого вам нужно использовать длину внутреннего списка:

# hashtable.py

class HashTable:
    # ...

    def _index(self, key):
        return hash(key) % len(self._pairs)


Теперь это намного лучше. В трех тестовых примерах, которые по-прежнему не выполняются, используются неверные предположения о длине хэш-таблицы. Измените эти предположения, чтобы тесты прошли успешно:

# test_hashtable.py

# ...

def test_should_insert_key_value_pairs():
    hash_table = HashTable(capacity=100)

    hash_table["hola"] = "hello"
    hash_table[98.6] = 37
    hash_table[False] = True

    assert ("hola", "hello") in hash_table.pairs
    assert (98.6, 37) in hash_table.pairs
    assert (False, True) in hash_table.pairs

    assert len(hash_table) == 3

# ...

def test_should_delete_key_value_pair(hash_table):
    assert "hola" in hash_table
    assert ("hola", "hello") in hash_table.pairs
    assert len(hash_table) == 3

    del hash_table["hola"]

    assert "hola" not in hash_table
    assert ("hola", "hello") not in hash_table.pairs
    assert len(hash_table) == 2

# ...

def test_should_update_value(hash_table):
    assert hash_table["hola"] == "hello"

    hash_table["hola"] = "hallo"

    assert hash_table["hola"] == "hallo"
    assert hash_table[98.6] == 37
    assert hash_table[False] is True
    assert len(hash_table) == 3


Вы вернулись в игру, но ZeroDivisionError был красным флажком, который должен был немедленно вызвать у вас желание добавить дополнительные тестовые примеры:

# test_hashtable.py

# ...

def test_should_not_create_hashtable_with_zero_capacity():
    with pytest.raises(ValueError):
        HashTable(capacity=0)

def test_should_not_create_hashtable_with_negative_capacity():
    with pytest.raises(ValueError):
        HashTable(capacity=-100)


Создание HashTable с неположительной емкостью не имеет особого смысла. Как у вас может быть контейнер с отрицательной длиной? Поэтому вам следует создать исключение, если кто-то попытается это сделать, намеренно или случайно. Стандартный способ указать на такие некорректные входные аргументы в Python - это создать исключение ValueError:

# hashtable.py

# ...

class HashTable:
    def __init__(self, capacity):
        if capacity < 1:
            raise ValueError("Capacity must be a positive number")
        self._pairs = capacity * [None]

    # ...


Если вы прилежны, то вам, вероятно, следует также проверить наличие недопустимых типов аргументов, но это выходит за рамки данного руководства. Вы можете рассматривать это как добровольное упражнение.
Затем добавьте другой сценарий для тестирования длины непустой хэш-таблицы, предоставленной в качестве фиксированного значения pytest:

# test_hashtable.py

# ...

def test_should_report_length(hash_table):
    assert len(hash_table) == 3


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

# test_hashtable.py

# ...

def test_should_report_capacity_of_empty_hash_table():
    assert HashTable(capacity=100).capacity == 100

def test_should_report_capacity(hash_table):
    assert hash_table.capacity == 100


Емкость является постоянной и определяется во время создания хэш-таблицы. Вы можете получить ее из длины базового списка пар:

# hashtable.py

# ...

class HashTable:
    # ...

    @property
    def capacity(self):
        return len(self._pairs)

    def _index(self, key):
        return hash(key) % self.capacity


По мере того, как вы вводите новую лексику в свою проблемную область, это помогает вам открывать новые возможности для более точного и недвусмысленного именования. Например, вы видели, что слово пары используется взаимозаменяемо для обозначения как фактических пар ключ-значение, хранящихся в вашей хэш-таблице, так и внутреннего списка ячеек для пар. Возможно, это хорошая возможность провести рефакторинг вашего кода, изменив везде ._pairs на ._slots.
Затем в одном из ваших предыдущих тестовых примеров будет более четко указано его назначение:

# test_hashtable.py

# ...

def test_should_create_empty_value_slots():
    assert HashTable(capacity=3)._slots == [None, None, None]


Возможно, было бы еще разумнее переименовать этот тест, заменив в нем слово значение на пара:

# test_hashtable.py

# ...

def test_should_create_empty_pair_slots():
    assert HashTable(capacity=3)._slots == [None, None, None]


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

# test_hashtable.py

# ...

def test_should_iterate_over_keys(hash_table):
    for key in hash_table.keys:
        assert key in ("hola", 98.6, False)

def test_should_iterate_over_values(hash_table):
    for value in hash_table.values:
        assert value in ("hello", 37, True)

def test_should_iterate_over_pairs(hash_table):
    for key, value in hash_table.pairs:
        assert key in hash_table.keys
        assert value in hash_table.values


Итерация по ключам, значениям или парам ключ-значение в текущей реализации работает "из коробки", поскольку базовые наборы и списки уже могут с этим справиться. С другой стороны, чтобы сделать экземпляры вашего HashTable класса итерируемыми, вы должны определить другой специальный метод, который позволит вам напрямую взаимодействовать с циклами for:

# test_hashtable.py

# ...

def test_should_iterate_over_instance(hash_table):
    for key in hash_table:
        assert key in ("hola", 98.6, False)


В отличие от предыдущего, здесь вы передаете ссылку на экземпляр HashTable, но поведение такое же, как если бы вы выполняли итерацию по свойству .keys. Такое поведение совместимо со встроенным dict в Python.
Специальный метод, который вам нужен, .__iter__(), должен возвращать  объект-итератор, который цикл использует внутренне:

# hashtable.py

# ...

class HashTable:
    # ...

    def __iter__(self):
        yield from self.keys


Это пример генераторного итератора, который использует ключевое слово yield в Python.
 Примечание: Выражение yield from передает итерацию подгенератору, который может быть другим повторяемым объектом , таким как список или набор.
Ключевое слово yield позволяет вам определить итератор на месте, используя функциональный стиль  без создания   другого класса. Специальный метод с именем .__iter__() вызывается циклом for при его запуске.
Итак, на данный момент в вашей хэш-таблице отсутствуют только несколько несущественных функций.
Представляет хэш-таблицу в текстовом виде
Следующий шаг, который вы собираетесь реализовать в этом разделе, придаст вашей хэш-таблице приятный вид при выводе  на стандартный   вывод. Текстовое представление вашей хэш-таблицы будет выглядеть аналогично литералу Python dict:

# test_hashtable.py

# ...

def test_should_use_dict_literal_for_str(hash_table):
    assert str(hash_table) in {
        "{'hola': 'hello', 98.6: 37, False: True}",
        "{'hola': 'hello', False: True, 98.6: 37}",
        "{98.6: 37, 'hola': 'hello', False: True}",
        "{98.6: 37, False: True, 'hola': 'hello'}",
        "{False: True, 'hola': 'hello', 98.6: 37}",
        "{False: True, 98.6: 37, 'hola': 'hello'}",
    }


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

# hashtable.py

# ...

class HashTable:
    # ...

    def __str__(self):
        pairs = []
        for key, value in self.pairs:
            pairs.append(f"{key!r}: {value!r}")
        return "{" + ", ".join(pairs) + "}"


Вы перебираете ключи и значения с помощью свойства .pairs и используете f-строки для форматирования отдельных пар. Обратите внимание на флаг преобразования !r в строке шаблона, который принудительно вызывает repr() вместо значения по умолчанию str() для ключей и значений. Это обеспечивает более четкое представление, которое варьируется в зависимости от типа данных. Например, он заключает строки в одинарные апострофы.
Разница между str() и repr() более тонкая. В общем, оба они предназначены для преобразования объектов в строки. Однако, хотя вы можете ожидать, что str() вернет понятный пользователю текст, repr() часто возвращает корректный фрагмент кода на Python, который вы можете оценить, чтобы воссоздать исходный объект:

>>> from fractions import Fraction
>>> quarter = Fraction("1/4")

>>> str(quarter)
'1/4'

>>> repr(quarter)
'Fraction(1, 4)'

>>> eval(repr(quarter))
Fraction(1, 4)


В этом примере строковое представление  дроби Python равно '1/4', но каноническое строковое представление того же объекта представляет собой вызов Fraction класс.
Вы можете добиться аналогичного эффекта в своем классе HashTable. К сожалению, в данный момент инициализатор вашего класса не позволяет создавать новые экземпляры из значений. Вы решите эту проблему, введя метод класса, который позволит вам создавать HashTable экземпляра из словарей Python:

# test_hashtable.py

# ...

def test_should_create_hashtable_from_dict():
    dictionary = {"hola": "hello", 98.6: 37, False: True}

    hash_table = HashTable.from_dict(dictionary)

    assert hash_table.capacity == len(dictionary) * 10
    assert hash_table.keys == set(dictionary.keys())
    assert hash_table.pairs == set(dictionary.items())
    assert unordered(hash_table.values) == list(dictionary.values())


Это хорошо согласуется с вашим предыдущим преобразованием, которое было выполнено в противоположном направлении. Однако вам нужно предположить, что хэш-таблица должна быть достаточно большой, чтобы содержать все пары ключ-значение из исходного словаря. Разумная оценка, по-видимому, в десять раз превышает количество пар. На данный момент вы можете жестко запрограммировать это:

# hashtable.py

# ...

class HashTable:

    @classmethod
    def from_dict(cls, dictionary):
        hash_table = cls(len(dictionary) * 10)
        for key, value in dictionary.items():
            hash_table[key] = value
        return hash_table


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

# test_hashtable.py

# ...

def test_should_create_hashtable_from_dict_with_custom_capacity():
    dictionary = {"hola": "hello", 98.6: 37, False: True}

    hash_table = HashTable.from_dict(dictionary, capacity=100)

    assert hash_table.capacity == 100
    assert hash_table.keys == set(dictionary.keys())
    assert hash_table.pairs == set(dictionary.items())
    assert unordered(hash_table.values) == list(dictionary.values())


Чтобы сделать емкость необязательной, вы можете воспользоваться вычислением короткого замыкания логических выражений:

# hashtable.py

# ...

class HashTable:

    @classmethod
    def from_dict(cls, dictionary, capacity=None):
        hash_table = cls(capacity or len(dictionary) * 10)
        for key, value in dictionary.items():
            hash_table[key] = value
        return hash_table


Если значение capacity не указано, то вы возвращаетесь к поведению по умолчанию, при котором длина словаря умножается на десять. Благодаря этому вы, наконец, сможете предоставить каноническое строковое представление для ваших экземпляров HashTable:

# test_hashtable.py

# ...

def test_should_have_canonical_string_representation(hash_table):
    assert repr(hash_table) in {
        "HashTable.from_dict({'hola': 'hello', 98.6: 37, False: True})",
        "HashTable.from_dict({'hola': 'hello', False: True, 98.6: 37})",
        "HashTable.from_dict({98.6: 37, 'hola': 'hello', False: True})",
        "HashTable.from_dict({98.6: 37, False: True, 'hola': 'hello'})",
        "HashTable.from_dict({False: True, 'hola': 'hello', 98.6: 37})",
        "HashTable.from_dict({False: True, 98.6: 37, 'hola': 'hello'})",
    }


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

# hashtable.py

# ...

class HashTable:
    # ...

    def __repr__(self):
        cls = self.__class__.__name__
        return f"{cls}.from_dict({str(self)})"


Обратите внимание, что имя класса не задается жестко, чтобы избежать проблем, если вы когда-нибудь решите переименовать свой класс позже.
Ваш прототип хэш-таблицы почти готов, так как вы реализовали почти все основные и несущественные функции из списка, упомянутого во введении к этому разделу. Вы только что добавили возможность создавать хэш-таблицу с помощью Python dict и предоставили строковые представления для ее экземпляров. Последний и заключительный момент заключается в том, что экземпляры хэш-таблицы можно сравнивать по значению.
Проверьте равенство хэш-таблиц
Хэш-таблицы похожи на наборы в том смысле, что они не устанавливают какой-либо определенный порядок для своего содержимого. На самом деле, у хэш-таблиц и наборов больше общего, чем вы могли бы подумать, поскольку они оба поддерживаются хэш-функцией. Именно хэш-функция делает пары ключ-значение в хэш-таблице неупорядоченными. Однако помните, что, начиная с Python 3.6, dict действительно сохраняет порядок вставки в качестве детали реализации.
Две хэш-таблицы должны сравниваться одинаково тогда и только тогда, когда они имеют одинаковый набор пар ключ-значение. Однако Python по умолчанию сравнивает объекты с идентификаторами, поскольку он не знает, как интерпретировать значения пользовательских типов данных. Таким образом, два экземпляра вашей хэш-таблицы всегда будут сравниваться неравномерно, даже если они используют один и тот же набор пар ключ-значение.
Чтобы исправить это, вы можете реализовать оператор проверки на равенство (==), предоставив специальный метод .__eq__() в вашем классе HashTable. Кроме того, Python вызовет этот метод для вычисления оператора not equal (!=), если вы также не реализуете .__ne__() явно.
Вы хотите, чтобы хэш-таблица была равна самой себе, своей копии или другому экземпляру с одинаковыми парами ключ-значение независимо от их порядка. И наоборот, хэш-таблица должна , а не быть равна экземпляру с другим набором пар ключ-значение или совершенно другим типом данных:

# test_hashtable.py

# ...

def test_should_compare_equal_to_itself(hash_table):
    assert hash_table == hash_table

def test_should_compare_equal_to_copy(hash_table):
    assert hash_table is not hash_table.copy()
    assert hash_table == hash_table.copy()

def test_should_compare_equal_different_key_value_order(hash_table):
    h1 = HashTable.from_dict({"a": 1, "b": 2, "c": 3})
    h2 = HashTable.from_dict({"b": 2, "a": 1, "c": 3})
    assert h1 == h2

def test_should_compare_unequal(hash_table):
    other = HashTable.from_dict({"different": "value"})
    assert hash_table != other

def test_should_compare_unequal_another_data_type(hash_table):
    assert hash_table != 42


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

# hashtable.py

# ...

class HashTable:
    # ...

    def __eq__(self, other):
        if self is other:
            return True
        if type(self) is not type(other):
            return False
        return set(self.pairs) == set(other.pairs)

    # ...

    def copy(self):
        return HashTable.from_dict(dict(self.pairs), self.capacity)


Специальный метод .__eq__() принимает некоторый объект для сравнения в качестве аргумента. Если этот объект является текущим экземпляром HashTable, то вы возвращаете True, поскольку один и тот же идентификатор подразумевает равенство значений. В противном случае вы продолжаете сравнивать типы и наборы пар ключ-значение. Преобразование в наборы помогает сделать порядок неактуальным, даже если вы решите превратить .pairs в другой упорядоченный список в будущем.
Кстати, результирующая копия должна иметь не только те же пары ключ-значение, но и ту же емкость, что и исходная хэш-таблица. В то же время две хэш-таблицы с разной емкостью все равно должны быть сопоставимы:

# test_hashtable.py

# ...

def test_should_copy_keys_values_pairs_capacity(hash_table):
    copy = hash_table.copy()
    assert copy is not hash_table
    assert set(hash_table.keys) == set(copy.keys)
    assert unordered(hash_table.values) == copy.values
    assert set(hash_table.pairs) == set(copy.pairs)
    assert hash_table.capacity == copy.capacity

def test_should_compare_equal_different_capacity():
    data = {"a": 1, "b": 2, "c": 3}
    h1 = HashTable.from_dict(data, capacity=50)
    h2 = HashTable.from_dict(data, capacity=100)
    assert h1 == h2


Эти два теста будут работать с вашей текущей реализацией HashTable, поэтому вам не нужно ничего дополнительно кодировать.
В вашем прототипе пользовательской хэш-таблицы по-прежнему отсутствует пара несущественных функций, которые предоставляет встроенный словарь. Вы можете попробовать добавить их самостоятельно в качестве упражнения. Например, вы могли бы скопировать другие методы из словарей Python, такие как dict.clear() или dict.update(). Кроме этого, вы могли бы реализовать один из побитовых операторов, поддерживаемых dict начиная с версии Python 3.9, которые допускают операцию объединения.
Молодец! Это готовый набор тестов для руководства, и ваша хэш-таблица прошла все модульные тесты. Поздравьте себя с заслуженным успехом, потому что это была чертовски отличная работа. Или так оно и было?
Предположим, вы уменьшили емкость вашей хэш-таблицы, чтобы учитывать только вставленные пары. Следующая хэш-таблица должна содержать все три пары ключ-значение, хранящиеся в исходном словаре:

>>> from hashtable import HashTable
>>> source = {"hola": "hello", 98.6: 37, False: True}
>>> hash_table = HashTable.from_dict(source, capacity=len(source))
>>> str(hash_table)
'{False: True}'


Однако, когда вы просматриваете ключи и значения результирующей хэш-таблицы, вы иногда обнаруживаете, что в ней меньше элементов. Чтобы сделать этот фрагмент кода повторяемым, запустите его с отключенной рандомизацией хэша, установив для переменной окружения PYTHONHASHSEED значение 0.
Чаще всего вы теряете информацию, даже если в хэш-таблице достаточно свободного места. Это связано с тем, что большинство хэш-функций несовершенны, что приводит к коллизиям хэшей, которые вы узнаете, как устранить далее.
Устранение коллизий хэш-кода
В этом разделе вы изучите две наиболее распространенные стратегии борьбы с коллизиями хэш-кода и реализуете их в своем классе HashTable. Если вы хотите следовать приведенным ниже примерам, то не забудьте установить для переменной PYTHONHASHSEED значение 0, чтобы отключить рандомизацию хэша в Python.
К настоящему времени вы уже должны иметь представление о том, что такое коллизия хэшей. Это когда два ключа генерируют идентичный хэш-код, в результате чего разные значения сталкиваются друг с другом по одному и тому же индексу в хэш-таблице. Например, в хэш-таблице с сотней ячеек ключи "easy" и "difficult" имеют один и тот же индекс, когда рандомизация хэша отключена:

>>> hash("easy") % 100
43

>>> hash("difficult") % 100
43


На данный момент ваша хэш-таблица не может обнаружить попыток сохранить разные значения в одном и том же слоте:

>>> from hashtable import HashTable

>>> hash_table = HashTable(capacity=100)
>>> hash_table["easy"] = "Requires little effort"
>>> hash_table["difficult"] = "Needs much skill"

>>> print(hash_table)
{'difficult': 'Needs much skill'}

>>> hash_table["easy"]
'Needs much skill'


В конечном итоге вы не только перезаписываете пару, указанную ключом "easy", но, что еще хуже, при извлечении значения этого несуществующего ключа вы получаете неверный ответ!
Вам доступны три стратегии устранения коллизий хэшей:



Strategy
Description




Perfect Hashing
Choose a perfect hash function to avoid hash collisions in the first place.


Open Addressing
Spread the collided values in a predictable way that lets you retrieve them later.


Closed Addressing
Keep the collided values in a separate data structure to search through.



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

 Перемешивание с кукушкой
 Двойное хеширование
 Хеширование классиков
 Линейное зондирование
 Квадратичное зондирование
 Перемешивание с Робином Гудом

В отличие от этого, закрытая адресация наиболее известна для отдельных цепочек. Кроме того, существует также объединенное хэширование, которое объединяет идеи, лежащие в основе как открытой, так и закрытой адресации, в один алгоритм.
Чтобы приступить к разработке, основанной на тестировании, вам сначала нужно разработать тестовый пример. Но как вы тестируете коллизию хэшей? Встроенная функция Python по умолчанию использует рандомизацию хэша для некоторых своих типов данных, что чрезвычайно затрудняет прогнозирование ее поведения. Выбор начального значения хэша вручную с помощью переменной окружения PYTHONHASHSEED был бы непрактичным и сделал бы ваши тестовые примеры хрупкими.
Лучший способ обойти это - использовать  имитирующую библиотеку, такую как Python unittest.mock:

from unittest.mock import patch

@patch("builtins.hash", return_value=42)
def test_should_detect_hash_collision(hash_mock):
    assert hash("foobar") == 42


 Исправление временно заменяет один объект другим. Например, вы можете заменить встроенную функцию hash() на поддельную, которая всегда возвращает одно и то же ожидаемое значение, что делает ваши тесты повторяемыми. Эта замена действует только во время вызова функции, после чего исходное значение hash() возвращается снова.
Вы можете применить декоратор @patch ко всей вашей тестовой функции или ограничить область видимости макетного объекта с помощью контекстного менеджера:

from unittest.mock import patch

def test_should_detect_hash_collision():
    assert hash("foobar") not in [1, 2, 3]
    with patch("builtins.hash", side_effect=[1, 2, 3]):
        assert hash("foobar") == 1
        assert hash("foobar") == 2
        assert hash("foobar") == 3


С помощью контекстного менеджера вы можете получить доступ к встроенной функции hash(), а также к ее имитируемой версии в рамках одного и того же тестового примера. При желании у вас может быть даже несколько вариантов имитируемой функции. Параметр side_effect позволяет вам указать вызываемое исключение или последовательность значений, которые ваш макетный объект будет возвращать при последовательных вызовах.
В оставшейся части этого руководства вы продолжите добавлять дополнительные функции в свой класс HashTable, не придерживаясь строгого подхода к разработке на основе тестирования. Новые тесты будут опущены для краткости, в то время как изменение класса приведет к сбою некоторых существующих тестов. Однако вы найдете рабочий набор тестов в прилагаемых материалах, доступных для скачивания.
Поиск Столкнувшихся Ключей С Помощью Линейного Зондирования
Остановимся на минутку, чтобы понять теорию коллизий хэш-кода. Когда дело доходит до обращения с ними,,  линейное зондирование является одним из старейших, наиболее простых и в то же время наиболее эффективных методов. Для этого требуется выполнить несколько дополнительных шагов для вставки, поиска, удаления и обновите операций, с которыми вы сейчас познакомитесь.
Рассмотрим пример хэш-таблицы, представляющей  Глоссарий Python с распространенными сокращениями. В общей сложности он вмещает десять слотов, но четыре из них уже заняты следующими парами ключ-значение:



Index
Key
Value




0




1
BDFL
Benevolent Dictator For Life


2




3
REPL
Read–Evaluate–Print Loop


4




5




6




7




8
PEP
Python Enhancement Proposal


9
WSGI
Web Server Gateway Interface



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

>>> hash("MRO")
8199632715222240545

>>> hash("MRO") % 10
5


Вместо использования оператора по модулю вы могли бы альтернативно обрезать хэш-код с помощью соответствующей битовой маски , как это работает внутри dict в Python.
 Примечание: Чтобы получить согласованные хэш-коды, установите для переменной окружения PYTHONHASHSEED значение 0, чтобы отключить рандомизацию хэша.
Отлично! В вашей хэш-таблице с пятым индексом есть свободное место, куда вы можете вставить новую пару ключ-значение:



Index
Key
Value




0




1
BDFL
Benevolent Dictator For Life


2




3
REPL
Read–Evaluate–Print Loop


4




5
MRO
Method Resolution Order


6




7




8
PEP
Python Enhancement Proposal


9
WSGI
Web Server Gateway Interface



Пока все хорошо. В вашей хэш-таблице по-прежнему остается 50% свободного места, поэтому вы продолжаете добавлять новые термины, пока не попробуете вставить аббревиатуру EAFP. Оказывается, хэш-код EAFP сокращается до единицы, которая является индексом ячейки, занятой BDFL термином:

>>> hash("EAFP")
-159847004290706279

>>> hash("BDFL")
-6396413444439073719

>>> hash("EAFP") % 10
1

>>> hash("BDFL") % 10
1


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



Index
Key
Value




0




1
BDFL
Benevolent Dictator For Life


2
EAFP
Easier To Ask For Forgiveness Than Permission


3
REPL
Read–Evaluate–Print Loop


4




5
MRO
Method Resolution Order


6




7




8
PEP
Python Enhancement Proposal


9
WSGI
Web Server Gateway Interface



Несмотря на то, что ключи BDFL и EAFP дают одинаковый индекс, равный единице, в конечном итоге его получает только первая вставленная пара ключ-значение. Какая бы пара ни была второй, она будет помещена рядом с занятым индексом. Таким образом, линейное зондирование делает хэш-таблицу чувствительной к порядку вставки.
 Примечание: Когда вы используете линейное зондирование или другие методы разрешения коллизий хэшей, вы не можете полагаться только на хэш-код для поиска соответствующего слота. Вам также необходимо сравнить ключи.
Рассмотрите возможность добавления другой аббревиатуры, ABC, для абстрактных базовых классов, хэш-код которых сокращается до восьмого индекса. На этот раз вы не можете вставить его в следующую позицию, потому что оно уже занято WSGI. При обычных обстоятельствах вы бы продолжили поиск свободного места ниже, но поскольку вы достигли последнего индекса, вам необходимо перейти к нулевому индексу и вставить новую аббревиатуру:



Index
Key
Value




0
ABC
Abstract Base Class


1
BDFL
Benevolent Dictator For Life


2
EAFP
Easier To Ask For Forgiveness Than Permission


3
REPL
Read–Evaluate–Print Loop


4




5
MRO
Method Resolution Order


6




7




8
PEP
Python Enhancement Proposal


9
WSGI
Web Server Gateway Interface



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

>>> hash("ABC")
-4164790459813301872

>>> hash("ABC") % 10
8


В восьмом индексе хранится пара ключ-значение, но у нее другой ключ, равный PEP, поэтому вы пропускаете его, увеличивая индекс. Опять же, этот интервал занят не связанным с ним термином WSGI, поэтому вы можете отклониться и обойти его, чтобы, наконец, найти свою пару с соответствующим ключом с нулевым индексом. Это ваш ответ.
В общем, существует три возможных условия остановки операции поиска:

Вы нашли подходящий ключ.
Вы исчерпали все слоты, так и не найдя подходящий ключ.
Вы нашли пустой слот, что также указывает на отсутствие ключа.

Последний пункт усложняет  удаление существующей пары ключ-значение. Если бы вы просто удалили запись из хэш-таблицы, то вы бы ввели пустую ячейку, которая остановила бы поиск в ней независимо от любых предыдущих коллизий. Чтобы снова сделать доступными столкнувшиеся пары ключ-значение, вам придется либо перефразировать их, либо использовать стратегию отложенного удаления.
 Последний вариант менее сложен в реализации, но сопряжен с дополнительными затратами, связанными с увеличением количества необходимых шагов поиска. По сути, вместо удаления пары ключ-значение вы заменяете ее контрольным значением, обозначенным красным крестиком (❌) ниже, что делает возможным поиск записей, которые ранее сталкивались друг с другом. Допустим, вы хотите удалить термины BDFL и PEP:



Index
Key
Value




0
ABC
Abstract Base Class


1
❌



2
EAFP
Easier To Ask For Forgiveness Than Permission


3
REPL
Read–Evaluate–Print Loop


4




5
MRO
Method Resolution Order


6




7




8
❌



9
WSGI
Web Server Gateway Interface



Вы заменили соответствующие пары ключ-значение двумя экземплярами контрольного значения. Позже, когда вы, например, будете искать ключ ABC, вы перейдете от sentinel к индексу восемь, затем перейдете к WSGI и, наконец, дойдете до нулевого индекса с соответствующим ключом. Без одного из стражей вы бы прекратили поиск гораздо раньше, ошибочно заключив, что такого ключа нет.
 Примечание: Емкость вашей хэш-таблицы остается неизменной, поскольку вы можете перезаписывать контрольные значения при вставке новых пар ключ-значение. С другой стороны, если бы вы заполнили хэш-таблицу и удалили большинство ее элементов, то практически получили бы алгоритм линейного поиска . Алгоритм линейного поиска. Алгоритм линейного поиска
Итак, вы узнали о вставке, удалении и поиске. Однако есть одна загвоздка в обновлении значения существующей записи в хэш-таблице с помощью линейного зондирования. При поиске пары для обновления вы должны пропустить ячейку только в том случае, если она занята другой парой с другим ключом или содержит контрольное значение. С другой стороны, если ячейка пуста или содержит соответствующий ключ, вам следует установить новое значение.
В следующем подразделе вы собираетесь изменить свой класс HashTable, чтобы использовать линейное зондирование для разрешения коллизий хэшей.
Используйте линейное зондирование в классе HashTable
После краткого экскурса в теорию линейного зондирования вы возвращаетесь к программированию. Поскольку линейное зондирование будет использоваться во всех четырех основных CRUD операциях в хэш-таблице, полезно написать вспомогательный метод в вашем классе, чтобы инкапсулировать логику посещения слотов хэш-таблицы:

# hashtable.py

# ...

class HashTable:
    # ...

    def _probe(self, key):
        index = self._index(key)
        for _ in range(self.capacity):
            yield index, self._slots[index]
            index = (index + 1) % self.capacity


Получив ключ, вы начинаете с использования соответствующего хэш-кода, чтобы найти его ожидаемый индекс в хэш-таблице. Затем вы перебираете все доступные ячейки в хэш-таблице, начиная с вычисленного индекса. На каждом шаге вы возвращаете текущий индекс и связанную с ним пару, которые могут быть пустыми или помеченными как удаленные. Затем вы увеличиваете индекс, при необходимости обводя начало координат.
Затем вы можете переписать свой метод .__setitem__(). Не забывайте о необходимости нового контрольного значения. Это значение позволит вам отличить слоты, которые никогда не были заняты, от тех, которые ранее сталкивались, но теперь удалены:

# hashtable.py

DELETED = object()

# ...

class HashTable:
    # ...

    def __setitem__(self, key, value):
        for index, pair in self._probe(key):
            if pair is DELETED: continue
            if pair is None or pair.key == key:
                self._slots[index] = Pair(key, value)
                break
        else:
            raise MemoryError("Not enough capacity")


Если ячейка пуста или содержит пару с соответствующим ключом, то вы переназначаете новую пару ключ-значение по текущему индексу и останавливаете линейное зондирование. В противном случае, если другая пара занимает этот слот и имеет другой ключ, или слот помечен как удаленный, вы продвигаетесь вперед до тех пор, пока не найдете свободный слот или не исчерпаете все доступные слоты. Если у вас заканчиваются доступные ячейки, вы создаете исключение MemoryError, указывающее на недостаточную емкость хэш-таблицы.
 Примечание: Так совпало, что метод .__setitem__() также предусматривает обновление значения существующей пары. Поскольку пары представлены неизменяемыми кортежами, вы заменяете всю пару соответствующим ключом, а не только его составляющую value.
Получение и удаление пар ключ-значение из хэш-таблицы с помощью линейного зондирования работает почти одинаково:

# hashtable.py

DELETED = object()

# ...

class HashTable:
    # ...

    def __getitem__(self, key):
        for _, pair in self._probe(key):
            if pair is None:
                raise KeyError(key)
            if pair is DELETED:
                continue
            if pair.key == key:
                return pair.value
        raise KeyError(key)

    def __delitem__(self, key):
        for index, pair in self._probe(key):
            if pair is None:
                raise KeyError(key)
            if pair is DELETED:
                continue
            if pair.key == key:
                self._slots[index] = DELETED
                break
        else:
            raise KeyError(key)


Единственное отличие заключается в выделенных строках. Чтобы удалить пару, вы должны знать, где она находится в хэш-таблице, чтобы заменить ее контрольным значением. С другой стороны, при поиске по ключу вас интересует только соответствующее значение. Если вас беспокоит это дублирование кода, вы можете попробовать провести рефакторинг в качестве упражнения. Однако, если это написано явно, это поможет донести суть.
 Примечание: Это хрестоматийная реализация хэш-таблицы, которая проверяет элементы путем сравнения ключей с помощью оператора проверки равенства (==). Однако это потенциально дорогостоящая операция, которой в реальных реализациях можно избежать, сохраняя хэш-код вместе с ключами и значениями в виде триплетов, а не пар. С другой стороны, хэш-коды дешевы для сравнения.
Вы можете использовать контракт с равным хэшем, чтобы ускорить процесс. Если два хэш-кода отличаются, то они гарантированно связаны с разными ключами, поэтому нет необходимости выполнять дорогостоящую проверку на равенство. Этот трюк значительно сокращает количество сравнений ключей.
Следует отметить еще одну важную деталь. Ячейки хэш—таблицы больше не могут находиться только в одном из двух состояний - пустом или занятом. Вставка контрольного значения в хэш-таблицу, чтобы пометить ячейку как удаленную, приводит к искажению свойств хэш-таблицы .pairs, .keys, и .values и неверному отображению длины. Чтобы исправить это, вы должны отфильтровать оба значения None и DELETED при возврате пар ключ-значение:

# hashtable.py

# ...

class HashTable:
    # ...

    @property
    def pairs(self):
        return {
            pair for pair in self._slots
            if pair not in (None, DELETED)
        }


С этим небольшим обновлением ваша хэш-таблица теперь должна уметь справляться с коллизиями хэшей, распределяя столкнувшиеся пары и ища их линейным образом:

>>> from unittest.mock import patch
>>> from hashtable import HashTable

>>> with patch("builtins.hash", return_value=24):
...     hash_table = HashTable(capacity=100)
...     hash_table["easy"] = "Requires little effort"
...     hash_table["difficult"] = "Needs much skill"

>>> hash_table._slots[24]
Pair(key='easy', value='Requires little effort')

>>> hash_table._slots[25]
Pair(key='difficult', value='Needs much skill')


Несмотря на наличие одного и того же хэш-кода, равного двадцати четырем, оба столкнувшихся ключа, "easy" и "difficult", отображаются рядом друг с другом в списке ._slots. Обратите внимание, что они перечислены в том же порядке, в каком вы добавили их в хэш-таблицу. Попробуйте поменять порядок вставки или изменить емкость хэш-таблицы и посмотрите, как это повлияет на ячейки.
На данный момент емкость хэш-таблицы остается неизменной. До внедрения линейного зондирования вы не обращали на это внимания и продолжали перезаписывать совпадающие значения. Теперь вы можете определить, когда в вашей хэш-таблице больше нет места, и создать соответствующее исключение. Однако не лучше ли было бы позволить хэш-таблице динамически масштабировать свою емкость по мере необходимости?
Пусть размер хэш-таблицы изменяется автоматически
Когда дело доходит до изменения размера хэш-таблицы, существуют две разные стратегии. Вы можете подождать до самого последнего момента и изменить размер хэш-таблицы только тогда, когда она заполнится, или же вы можете сделать это сразу после достижения определенного порога. У обоих способов есть свои плюсы и минусы. Стратегия , возможно, более проста в реализации, поэтому сначала вы познакомитесь с ней поближе. Однако это может привести к большему количеству коллизий и снижению производительности.
Единственный раз, когда вам абсолютно необходимо увеличить количество ячеек в вашей хэш-таблице, - это когда при вставке новой пары происходит сбой, что приводит к возникновению исключения MemoryError. Продолжайте и замените инструкцию raise вызовом другого вспомогательного метода, который вы создадите, а затем рекурсивным вызовом .__setitem__() с помощью синтаксиса квадратных скобок:

# hashtable.py

# ...

class HashTable:
    # ...

    def __setitem__(self, key, value):
        for index, pair in self._probe(key):
            if pair is DELETED: continue
            if pair is None or pair.key == key:
                self._slots[index] = Pair(key, value)
                break
        else:
            self._resize_and_rehash()
            self[key] = value


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

# hashtable.py

# ...

class HashTable:
    # ...

    def _resize_and_rehash(self):
        copy = HashTable(capacity=self.capacity * 2)
        for key, value in self.pairs:
            copy[key] = value
        self._slots = copy._slots


Создайте локальную копию хэш-таблицы. Поскольку трудно предсказать, сколько еще ячеек вам может понадобиться, попробуйте угадать и удвоить объем. Затем выполните итерацию по существующему набору пар ключ-значение и вставьте их в копию. Наконец, переназначьте атрибут ._slots в вашем экземпляре так, чтобы он указывал на расширенный список слотов.
Ваша хэш-таблица теперь может динамически увеличивать свой размер, когда это необходимо, так что попробуйте. Создайте пустую хэш-таблицу емкостью в единицу и попробуйте вставить в нее несколько пар ключ-значение:


Окна


Linux + macOS



>>> from hashtable import HashTable
>>> hash_table = HashTable(capacity=1)
>>> for i in range(20):
...     num_pairs = len(hash_table)
...     num_empty = hash_table.capacity - num_pairs
...     print(
...         f"{num_pairs:>2}/{hash_table.capacity:>2}",
...         ("X" * num_pairs) + ("." * num_empty)
...     )
...     hash_table[i] = i
...
 0/ 1 .
 1/ 1 X
 2/ 2 XX
 3/ 4 XXX.
 4/ 4 XXXX
 5/ 8 XXXXX...
 6/ 8 XXXXXX..
 7/ 8 XXXXXXX.
 8/ 8 XXXXXXXX
 9/16 XXXXXXXXX.......
10/16 XXXXXXXXXX......
11/16 XXXXXXXXXXX.....
12/16 XXXXXXXXXXXX....
13/16 XXXXXXXXXXXXX...
14/16 XXXXXXXXXXXXXX..
15/16 XXXXXXXXXXXXXXX.
16/16 XXXXXXXXXXXXXXXX
17/32 XXXXXXXXXXXXXXXXX...............
18/32 XXXXXXXXXXXXXXXXXX..............
19/32 XXXXXXXXXXXXXXXXXXX.............



>>> from hashtable import HashTable
>>> hash_table = HashTable(capacity=1)
>>> for i in range(20):
...     num_pairs = len(hash_table)
...     num_empty = hash_table.capacity - num_pairs
...     print(
...         f"{num_pairs:>2}/{hash_table.capacity:>2}",
...         ("▣" * num_pairs) + ("□" * num_empty)
...     )
...     hash_table[i] = i
...
 0/ 1 □
 1/ 1 ▣
 2/ 2 ▣▣
 3/ 4 ▣▣▣□
 4/ 4 ▣▣▣▣
 5/ 8 ▣▣▣▣▣□□□
 6/ 8 ▣▣▣▣▣▣□□
 7/ 8 ▣▣▣▣▣▣▣□
 8/ 8 ▣▣▣▣▣▣▣▣
 9/16 ▣▣▣▣▣▣▣▣▣□□□□□□□
10/16 ▣▣▣▣▣▣▣▣▣▣□□□□□□
11/16 ▣▣▣▣▣▣▣▣▣▣▣□□□□□
12/16 ▣▣▣▣▣▣▣▣▣▣▣▣□□□□
13/16 ▣▣▣▣▣▣▣▣▣▣▣▣▣□□□
14/16 ▣▣▣▣▣▣▣▣▣▣▣▣▣▣□□
15/16 ▣▣▣▣▣▣▣▣▣▣▣▣▣▣▣□
16/16 ▣▣▣▣▣▣▣▣▣▣▣▣▣▣▣▣
17/32 ▣▣▣▣▣▣▣▣▣▣▣▣▣▣▣▣▣□□□□□□□□□□□□□□□
18/32 ▣▣▣▣▣▣▣▣▣▣▣▣▣▣▣▣▣▣□□□□□□□□□□□□□□
19/32 ▣▣▣▣▣▣▣▣▣▣▣▣▣▣▣▣▣▣▣□□□□□□□□□□□□□


При успешной вставке двадцати пар ключ-значение вы не получили ни одной ошибки. На этом грубом рисунке вы можете четко видеть удвоение ячеек, которое происходит, когда хэш-таблица заполняется и требуется больше ячеек.
Благодаря автоматическому изменению размера, которое вы только что внедрили, вы можете использовать  емкость по умолчанию для новых хэш-таблиц. Таким образом, для создания экземпляра класса HashTable больше не потребуется указывать начальную емкость, хотя это может повысить производительность. Обычно для начальной емкости используется небольшая степень двойки, например, восемь:

# hashtable.py

# ...

class HashTable:
    @classmethod
    def from_dict(cls, dictionary, capacity=None):
        hash_table = cls(capacity or len(dictionary))
        for key, value in dictionary.items():
            hash_table[key] = value
        return hash_table

    def __init__(self, capacity=8):
        if capacity < 1:
            raise ValueError("Capacity must be a positive number")
        self._slots = capacity * [None]

    # ...


Это позволяет создавать хэш-таблицы с вызовом инициализатора без параметров HashTable(). Обратите внимание, что вы также можете обновить метод вашего класса HashTable.from_dict(), чтобы использовать длину словаря в качестве начальной емкости. Ранее вы умножали длину словаря на произвольный коэффициент, который был необходим для того, чтобы ваши тесты прошли успешно, из-за необработанных коллизий хэшей.
Как указывалось ранее, существует одна проблема, связанная со стратегией отложенного изменения размера, а именно повышенная вероятность коллизий. Далее мы рассмотрим этот вопрос.
Рассчитайте коэффициент загрузки
Ожидание, пока ваша хэш-таблица не заполнится, не является оптимальным. Вы можете попробовать  стратегию ожидания, чтобы изменить размер хэш-таблицы до достижения ее общей емкости, что в первую очередь предотвратит возникновение коллизий. Как выбрать оптимальный момент для изменения размера и переформулировки? Используйте коэффициент загрузки!
Коэффициент загрузки  - это отношение количества занятых в данный момент ячеек, включая удаленные, ко всем ячейкам в хэш-таблице. Чем выше коэффициент загрузки, тем больше вероятность коллизии хэшей, что приводит к снижению производительности поиска. Поэтому вы хотите, чтобы коэффициент загрузки всегда оставался относительно небольшим. Увеличение размера хэш-таблицы происходит всякий раз, когда коэффициент загрузки достигает определенного порога.
Выбор определенного порога является классическим примером компромисса между пространством и временем в информатике. Более частое изменение размера хэш-таблицы обходится дешевле и приводит к повышению производительности за счет увеличения потребления памяти. И наоборот, более длительное ожидание может сэкономить немного памяти, но поиск по ключам будет выполняться медленнее. На приведенной ниже диаграмме показана взаимосвязь между объемом выделенной памяти и средним числом коллизий:

Данные, лежащие в основе этой диаграммы, измеряют среднее число коллизий, вызванных вставкой ста элементов в пустую хэш-таблицу с начальной емкостью в один. Измерение повторялось много раз для различных пороговых значений коэффициента загрузки, при достижении которых размер хэш-таблицы изменялся дискретными скачками, удваивая ее емкость.
Пересечение обоих графиков, которое отображается на отметке 0,75, указывает на  оптимальное значение порога  с наименьшим объемом памяти и количеством коллизий. Использование более высокого порогового значения коэффициента загрузки не обеспечивает существенной экономии памяти, но экспоненциально увеличивает количество коллизий. Меньшее пороговое значение повышает производительность, но требует высокой стоимости памяти, которая в основном тратится впустую. Помните, что все, что вам действительно нужно, - это сто слотов!
Вы можете поэкспериментировать с различными пороговыми значениями коэффициента загрузки, но хорошей отправной точкой может быть изменение размера хэш-таблицы, когда занято 60 процентов ее ячеек. Вот как вы можете реализовать расчет коэффициента загрузки в вашем классе HashTable:

# hashtable.py

# ...

class HashTable:
    # ...

    @property
    def load_factor(self):
        occupied_or_deleted = [slot for slot in self._slots if slot]
        return len(occupied_or_deleted) / self.capacity


Вы начинаете с фильтрации достоверных интервалов, которые могут быть любыми, кроме None, а затем берете соотношение в соответствии с определением коэффициента загрузки. Обратите внимание, что если вы решите использовать понятийное выражение, то оно должно быть  понятным списком, чтобы подсчитать все вхождения контрольного значения. В этом случае использование заданного понимания привело бы к отфильтровыванию повторяющихся маркеров удаленных пар, оставляя только один экземпляр и приводя к неправильному коэффициенту загрузки.
Затем измените свой класс, чтобы он принимал необязательный  порог коэффициента загрузки и использовал его для быстрого изменения размера и перепрофилирования слотов:

# hashtable.py

# ...

class HashTable:
    # ...

    def __init__(self, capacity=8, load_factor_threshold=0.6):
        if capacity < 1:
            raise ValueError("Capacity must be a positive number")
        if not (0 < load_factor_threshold <= 1):
            raise ValueError("Load factor must be a number between (0, 1]")
        self._slots = capacity * [None]
        self._load_factor_threshold = load_factor_threshold

    # ...

    def __setitem__(self, key, value):
        if self.load_factor >= self._load_factor_threshold:
            self._resize_and_rehash()

        for index, pair in self._probe(key):
            if pair is DELETED: continue
            if pair is None or pair.key == key:
                self._slots[index] = Pair(key, value)
                break


Пороговое значение коэффициента загрузки по умолчанию равно 0,6, что означает, что занято 60 процентов всех ячеек. Вы используете слабое неравенство (>=) вместо строгого (>), чтобы учесть пороговое значение коэффициента загрузки при его максимальном значении, которое никогда не может быть больше единицы. Если коэффициент загрузки равен единице, то вы также должны изменить размер хэш-таблицы, прежде чем вставлять другую пару ключ-значение.
Блестяще! Ваша хэш-таблица только что стала немного быстрее. На этом мы завершаем пример открытой адресации в этом руководстве. Далее вы будете устранять коллизии хэшей, используя один из самых популярных методов закрытой адресации.
Изолируйте Столкнувшиеся Ключи С Помощью Отдельной Цепочки
 Отдельная цепочка - это еще один чрезвычайно популярный метод разрешения коллизий хэшей, возможно, даже более распространенный, чем линейное зондирование. Идея состоит в том, чтобы сгруппировать похожие предметы по общему признаку в так называемые корзин, чтобы сузить область поиска. Например, вы можете представить, как собираете фрукты в корзины с цветовой маркировкой:

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

Цепочки столкнувшихся пар Ключ-значение
Каждый связанный список содержит пары ключ-значение, ключи которых имеют одинаковый хэш-код из-за коллизии. При поиске значения по ключу вам нужно сначала найти нужную ячейку, затем пройти по ней с помощью линейного поиска, чтобы найти соответствующий ключ, и, наконец, вернуть соответствующее значение. Линейный поиск означает просто просмотр каждого элемента в корзине, одного за другим, пока вы не найдете нужный ключ.
 Примечание: Элементы связанных списков имеют небольшую нагрузку на память, поскольку каждый узел содержит ссылку на следующий элемент. В то же время такое расположение памяти позволяет очень быстро добавлять и удалять элементы по сравнению с обычным массивом.
Чтобы адаптировать ваш класс HashTable для использования отдельной цепочки, начните с удаления метода ._probe() и замены слотов на сегменты. Теперь вместо значения None или пары значений в каждом индексе вы создадите для каждого индекса отдельную ячейку, которая может быть пустой или нет. Каждая ячейка будет представлять собой связанный список:

# hashtable.py

from collections import deque

# ...

class HashTable:
    # ...

    def __init__(self, capacity=8, load_factor_threshold=0.6):
        if capacity < 1:
            raise ValueError("Capacity must be a positive number")
        if not (0 < load_factor_threshold <= 1):
            raise ValueError("Load factor must be a number between (0, 1]")
        self._buckets = [deque() for _ in range(capacity)]
        self._load_factor_threshold = load_factor_threshold

    # ...

    def _resize_and_rehash(self):
        copy = HashTable(capacity=self.capacity * 2)
        for key, value in self.pairs:
            copy[key] = value
        self._buckets = copy._buckets


Вместо того, чтобы создавать связанный список с нуля, вы можете воспользоваться преимуществами двусторонней очереди Python или deque, доступных в collections модуль, который использует двусвязный список под капотом. Это позволяет добавлять и удалять элементы более эффективно, чем в обычном списке.
Не забудьте обновить свойства .pairs, .capacity, и .load_factor, чтобы они ссылались на сегменты, а не на слоты:

# hashtable.py

# ...

class HashTable:
    # ...

    @property
    def pairs(self):
        return {pair for bucket in self._buckets for pair in bucket}

    # ...

    @property
    def capacity(self):
        return len(self._buckets)

    # ...

    @property
    def load_factor(self):
        return len(self) / self.capacity


Вам больше не нужно контрольное значение, чтобы помечать элементы как удаленные, поэтому продолжайте и удалите константу DELETED. Это упрощает определение пар ключ-значение и коэффициента загрузки. Емкость является синонимом количества блоков, поскольку вы хотите сохранить не более одной пары ключ-значение в каждом блоке, чтобы свести к минимуму количество коллизий хэш-кода.
 Примечание: Коэффициент загрузки, определенный таким образом, может превышать единицу, когда количество пар ключ-значение, хранящихся в хэш-таблице, превышает количество сегментов.
Кстати, если разрешить слишком много коллизий, ваша хэш-таблица фактически превратится в плоский список с линейной временной сложностью, что значительно снизит ее производительность. Злоумышленники могут воспользоваться этим фактом, искусственно создавая как можно больше коллизий.
При раздельном объединении все основные операции с хэш-таблицами сводятся к поиску нужной ячейки и поиску по ней, что делает соответствующие методы похожими:

# hashtable.py

# ...

class HashTable:
    # ...

    def __delitem__(self, key):
        bucket = self._buckets[self._index(key)]
        for index, pair in enumerate(bucket):
            if pair.key == key:
                del bucket[index]
                break
        else:
            raise KeyError(key)

    def __setitem__(self, key, value):
        if self.load_factor >= self._load_factor_threshold:
            self._resize_and_rehash()

        bucket = self._buckets[self._index(key)]
        for index, pair in enumerate(bucket):
            if pair.key == key:
                bucket[index] = Pair(key, value)
                break
        else:
            bucket.append(Pair(key, value))

    def __getitem__(self, key):
        bucket = self._buckets[self._index(key)]
        for pair in bucket:
            if pair.key == key:
                return pair.value
        raise KeyError(key)


Экземпляры Deque обновляют свои внутренние ссылки, когда вы удаляете элемент по индексу. Если бы вы использовали пользовательский связанный список, вам пришлось бы вручную перестраивать пары ключ-значение после каждого изменения. Как и прежде, обновление существующей пары ключ-значение требует замены старой на совершенно новую, поскольку пары ключ-значение неизменяемы.
Если вы не хотите повторяться, попробуйте провести рефакторинг трех описанных выше методов, используя структурное сопоставление с образцом, введенное в Python 3.10. Вы найдете одно из возможных решений в сопроводительных материалах. 
Итак, вы знаете, как справляться с коллизиями хэш-кода, и теперь готовы двигаться дальше. Далее вы заставите вашу хэш-таблицу возвращать ключи и значения в порядке их вставки.
Сохранение порядка вставки в хэш-таблицу
Поскольку классическая структура данных хэш-таблицы использует хэширование для равномерного,   а иногда   и псевдослучайного распределения ключей, она не может гарантировать их порядок. Как правило, вы никогда не должны предполагать, что элементы хэш-таблицы будут располагаться в согласованном порядке, когда вы их запросите. Но иногда может оказаться полезным или даже необходимым установить определенный порядок для ваших элементов.
Вплоть до версии Python 3.6 единственным способом упорядочивания элементов словаря было использование OrderedDict оболочки из стандартной библиотеки. Позже встроенный тип данных dict начал сохранять порядок  вставки пар ключ-значение. Как бы то ни было, все же может оказаться разумным предположить отсутствие порядка элементов, чтобы сделать ваш код совместимым со старыми или альтернативными версиями Python.
Как вы можете воспроизвести аналогичное сохранение порядка вставки в своем пользовательском классе HashTable? Одним из способов может быть запоминание последовательности ключей при их вставке и повторение этой последовательности для возврата ключей, значений и пар. Начните с объявления другого внутреннего поля в вашем классе:

# hashtable.py

# ...

class HashTable:
    # ...

    def __init__(self, capacity=8, load_factor_threshold=0.6):
        if capacity < 1:
            raise ValueError("Capacity must be a positive number")
        if not (0 < load_factor_threshold <= 1):
            raise ValueError("Load factor must be a number between (0, 1]")
        self._keys = []
        self._buckets = [deque() for _ in range(capacity)]
        self._load_factor_threshold = load_factor_threshold


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

# hashtable.py

# ...

class HashTable:
    # ...

    def __delitem__(self, key):
        bucket = self._buckets[self._index(key)]
        for index, pair in enumerate(bucket):
            if pair.key == key:
                del bucket[index]
                self._keys.remove(key)
                break
        else:
            raise KeyError(key)

    def __setitem__(self, key, value):
        if self.load_factor >= self._load_factor_threshold:
            self._resize_and_rehash()

        bucket = self._buckets[self._index(key)]
        for index, pair in enumerate(bucket):
            if pair.key == key:
                bucket[index] = Pair(key, value)
                break
        else:
            bucket.append(Pair(key, value))
            self._keys.append(key)


Вы удаляете ключ, когда в хэш-таблице больше нет связанной пары ключ-значение. С другой стороны, вы добавляете ключ только при первой вставке совершенно новой пары ключ-значение в хэш-таблицу. Вы не хотите вставлять ключ при обновлении, потому что это приведет к созданию нескольких копий одного и того же ключа.
Далее вы можете изменить три свойства .keys, .values, и .pairs таким образом, чтобы они следовали тому же порядку вставленных клавиш:

# hashtable.py

# ...

class HashTable:
    # ...

    @property
    def keys(self):
        return self._keys.copy()

    @property
    def values(self):
        return [self[key] for key in self.keys]

    @property
    def pairs(self):
        return [(key, self[key]) for key in self.keys]


Обязательно верните копию ваших ключей, чтобы избежать утечки информации о внутренней реализации. Также обратите внимание, что все эти три свойства теперь возвращают списки вместо наборов, потому что вы хотите, чтобы они сохраняли правильный порядок. В свою очередь, это позволяет вам  объединить ключи и значения в пары:

>>> from hashtable import HashTable
>>> hash_table = HashTable.from_dict({
...     "hola": "hello",
...     98.6: 37,
...     False: True
... })

>>> hash_table.keys
['hola', 98.6, False]

>>> hash_table.values
['hello', 37, True]

>>> hash_table.pairs
[('hola', 'hello'), (98.6, 37), (False, True)]

>>> hash_table.pairs == list(zip(hash_table.keys, hash_table.values))
True


Ключи и значения всегда возвращаются в одном и том же порядке, так что, например, первый ключ и первое значение сопоставляются друг с другом. Это означает, что вы можете архивировать их, как в примере выше.
Теперь вы знаете, как сохранить порядок вставки пар ключ-значение в вашей хэш-таблице. С другой стороны, если вы хотите отсортировать их по более сложным критериям, вы можете использовать те же методы, что и при сортировке по встроенному словарю. На данный момент нет необходимости писать дополнительный код.
Используйте хэшируемые ключи
Теперь ваша хэш-таблица завершена и полностью функциональна. Она может преобразовывать произвольные ключи в значения с помощью встроенной функции hash(). Она может обнаруживать и устранять коллизии хэш-кода и даже сохранять порядок вставки пар ключ-значение. Теоретически вы могли бы использовать его поверх Python dict, если бы захотели, не заметив особой разницы, кроме низкой производительности и иногда более подробного синтаксиса.
 Примечание: Как упоминалось ранее, вам редко приходится самостоятельно реализовывать структуру данных, такую как хэш-таблица. Python поставляется со множеством полезных коллекций, которые обладают непревзойденной производительностью и протестированы в полевых условиях бесчисленным количеством разработчиков. Что касается специализированных структур данных, вам следует проверить PyPI на наличие сторонних библиотек, прежде чем пытаться создать свою собственную. Вы сэкономите много времени и значительно снизите риск возникновения ошибок.
До сих пор вы считали само собой разумеющимся, что большинство встроенных типов в Python могут работать как ключи хэш-таблицы. Однако, чтобы использовать любую реализацию хэш-таблицы на практике, вам придется ограничить ключи только хэшируемыми типами и понимать последствия этого. Это будет особенно полезно, когда вы решите включить в уравнение пользовательские типы данных.
Хэшируемость и неизменяемость
Ранее вы узнали, что некоторые типы данных, включая наиболее примитивные типы данных в Python, являются хэшируемыми, в то время как другие - нет. Основной чертой хэшируемости является способность вычислять хэш-код данного объекта:

>>> hash(frozenset(range(10)))
3895031357313128696

>>> hash(set(range(10)))
Traceback (most recent call last):
  File "<input>", line 1, in <module>
    hash(set(range(10)))
TypeError: unhashable type: 'set'


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

>>> hashable = frozenset(range(10))
>>> {hashable: "set of numbers"}
{frozenset({0, 1, 2, 3, 4, 5, 6, 7, 8, 9}): 'set of numbers'}
>>> {hashable}
{frozenset({0, 1, 2, 3, 4, 5, 6, 7, 8, 9})}

>>> unhashable = set(range(10))
>>> {unhashable: "set of numbers"}
Traceback (most recent call last):
  File "<input>", line 1, in <module>
    {unhashable: "set of numbers"}
TypeError: unhashable type: 'set'
>>> {unhashable}
Traceback (most recent call last):
  File "<input>", line 1, in <module>
    {unhashable}
TypeError: unhashable type: 'set'


В то время как экземпляр frozenset является хэшируемым, соответствующий набор с точно такими же значениями - нет. Имейте в виду, что вы все равно можете использовать не хэшируемый тип данных для значений словаря. Это словарь ключей, который должен уметь вычислять соответствующие им хэш-коды.
 Примечание: Когда вы вставляете объект, который невозможно хэшировать, в контейнер с возможностью хэширования, такой как frozenset, этот контейнер также становится недоступным для хэширования.
Хэшируемость тесно связана с изменчивостью, или способностью изменять внутреннее состояние объекта в течение его жизненного цикла. Взаимосвязь между этими двумя понятиями немного напоминает изменение адреса. Когда вы переезжаете в другое место, вы остаетесь тем же человеком, но вашим старым друзьям может быть трудно вас найти.
Недоступные типы в Python, такие как списки, наборы или словари, являются изменяемыми контейнерами, поскольку вы можете изменять их значения, добавляя или удаляя элементы. С другой стороны, большинство встроенных хэшируемых типов в Python являются неизменяемыми. Означает ли это, что изменяемые типы не могут быть хэшируемыми?
Правильный ответ - они могут быть как изменяемыми, так и хэшируемыми, но они редко должны быть такими! Изменение ключа приведет к изменению его адреса в памяти в хэш-таблице. Рассмотрим этот пользовательский класс в качестве примера:

>>> class Person:
...     def __init__(self, name):
...         self.name = name


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

>>> hash(Person("Joe"))
8766622471691

>>> hash(Person("Joe"))
8766623682281


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

>>> class Person:
...     def __init__(self, name):
...         self.name = name
...
...     def __hash__(self):
...         return hash(self.name)

>>> hash(Person("Joe")) == hash(Person("Joe"))
True


Вы вызываете hash() для атрибута .name, чтобы экземпляры класса Person с одинаковыми именами всегда имели одинаковый хэш-код. Это удобно, например, для поиска их в словаре.
 Примечание: Вы можете явно пометить свой класс как недоступный для хэширования, установив его атрибут .__hash__ равным None:

>>> class Person:
...     __hash__ = None
...
...     def __init__(self, name):
...         self.name = name

>>> hash(Person("Alice"))
Traceback (most recent call last):
  File "<input>", line 1, in <module>
    hash(Person("Alice"))
TypeError: unhashable type: 'Person'


Это предотвратит работу hash() с экземплярами вашего класса.
Еще одной особенностью хэшируемых типов является возможность сравнивать их экземпляры по значению. Напомним, что хэш-таблица сравнивает ключи с помощью оператора проверки на равенство (==), поэтому вы должны реализовать в своем классе другой специальный метод, .__eq__(), чтобы это было возможно:

>>> class Person:
...     def __init__(self, name):
...         self.name = name
...
...     def __eq__(self, other):
...         if self is other:
...             return True
...         if type(self) is not type(other):
...             return False
...         return self.name == other.name
...
...     def __hash__(self):
...         return hash(self.name)


Этот фрагмент кода должен показаться знакомым, если вы ранее проходили проверку хэш-таблиц на равенство. В двух словах, вы проверяете, является ли другой объект точно таким же экземпляром, экземпляром другого типа или другим экземпляром того же типа и имеет значение, равное атрибуту .name.
 Примечание: Специальные методы кодирования, такие как .__eq__() и .__hash__(), могут быть повторяющимися, утомительными и чреватыми ошибками. Если вы используете Python 3.7 или выше, то вы можете добиться того же эффекта более компактно, используя  классов данных:

@dataclass(unsafe_hash=True)
class Person:
    name: str


В то время как класс данных генерирует .__eq__() на основе атрибутов вашего класса, вы должны установить параметр unsafe_hash, чтобы включить генерацию правильного метода .__hash__().
Реализовав .__eq__() и .__hash__(), вы можете использовать экземпляры класса Person в качестве ключей словаря:

>>> alice = Person("Alice")
>>> bob = Person("Bob")

>>> employees = {alice: "project manager", bob: "engineer"}

>>> employees[bob]
'engineer'

>>> employees[Person("Bob")]
'engineer'


Отлично! Не имеет значения, найдете ли вы сотрудника по bob ссылке, которую вы создали ранее, или по совершенно новому Person("Bob") экземпляру. К сожалению, все усложняется, когда Боб внезапно решает сменить свое имя и называть себя Бобби:

>>> bob.name = "Bobby"

>>> employees[bob]
Traceback (most recent call last):
  File "<input>", line 1, in <module>
    employees[bob]
KeyError: <__main__.Person object at 0x7f607e325e40>

>>> employees[Person("Bobby")]
Traceback (most recent call last):
  File "<input>", line 1, in <module>
    employees[Person("Bobby")]
KeyError: <__main__.Person object at 0x7f607e16ed10>

>>> employees[Person("Bob")]
Traceback (most recent call last):
  File "<input>", line 1, in <module>
    employees[Person("Bob")]
KeyError: <__main__.Person object at 0x7f607e1769e0>


У вас больше нет возможности получить соответствующее значение, даже если вы по-прежнему используете исходный ключевой объект, который вы вставили ранее. Что еще более удивительно, так это то, что вы не можете получить доступ к значению через новый ключевой объект с обновленным именем пользователя или со старым именем. Можете ли вы объяснить, почему?
Хэш-код исходного ключа определял, в какой ячейке было сохранено соответствующее значение. Изменение состояния вашего ключа привело к тому, что его хэш-код указывал на совершенно другую ячейку или интервал, который не содержит ожидаемого значения. Но использование ключа со старым именем тоже не помогает. Хотя он указывает на правильную ячейку, сохраненный ключ изменился, в результате чего сравнение на равенство между "Bob" и "Bobby" оценивается как False, а не как совпадение.
Следовательно, хэш-коды должны быть неизменяемыми, чтобы хэширование работало должным образом. Поскольку хэш-коды обычно выводятся из атрибутов объекта, их состояние должно быть фиксированным и никогда не изменяться с течением времени. На практике это также означает, что объекты, предназначенные в качестве ключей хэш-таблицы, сами по себе должны быть неизменяемыми.
Подводя итог, можно сказать, что хэшируемый тип данных обладает следующими характеристиками:

Имеет .__hash__() метод для вычисления хэш-кода экземпляра 
Имеет .__eq__() метод для сравнения экземпляров по значению
Имеет неизменяемые хэш-коды, которые не меняются в течение жизни экземпляров
Соответствует контракту с равным хэшем

Четвертая и последняя особенность хэшируемых типов заключается в том, что они должны соответствовать контракту , равному хэшу, о котором вы узнаете больше в следующем подразделе. Короче говоря, объекты с равными значениями должны иметь одинаковые хэш-коды.
Контракт с равным хэшем
Чтобы избежать проблем при использовании пользовательских классов в качестве ключей хэш-таблицы, они должны соответствовать контракту на равенство хэшей. Если и есть что-то, что следует помнить об этом контракте, так это то, что при реализации .__eq__() вы должны всегда  реализовывать соответствующее .__hash__(). Единственный раз, когда вам не нужно реализовывать оба метода, это когда вы используете оболочку, такую как  класс данных или неизменяемый именованный кортеж, который уже выполняет это для ты.
Кроме того, отказ от реализации обоих методов может быть приемлемым, если вы абсолютно уверены, что никогда не будете использовать объекты вашего типа данных в качестве ключей словаря или элементов набора. Но можете ли вы быть так уверены?
 Примечание: Если вы не можете использовать класс данных или именованный кортеж и хотите вручную сравнить и хэшировать более одного поля в классе, то объедините их в кортеж:

class Person:
    def __init__(self, name, date_of_birth, married):
        self.name = name
        self.date_of_birth = date_of_birth
        self.married = married

    def __hash__(self):
        return hash(self._fields)

    def __eq__(self, other):
        if self is other:
            return True
        if type(self) is not type(other):
            return False
        return self._fields == other._fields

    @property
    def _fields(self):
        return self.name, self.date_of_birth, self.married


Имеет смысл определить частное свойство, возвращающее этот кортеж, если в вашем классе относительно много полей.
 Хотя вы можете реализовать оба метода так, как вам нравится, они должны удовлетворять контракту на равенство хэшей, который гласит, что два одинаковых объекта должны быть преобразованы в одинаковые хэш-коды. Это позволяет найти нужную ячейку  на основе предоставленного ключа. Однако обратное неверно, поскольку коллизии могут иногда приводить к тому, что один и тот же хэш-код будет использоваться разными значениями. Вы можете выразить это более формально, используя следующие два вывода:

a = b ⇒ hash(a) = hash(b)
hash(a) = hash(b) ⇏ a = b

Контракт с равным хэшем является односторонним контрактом . Если   два ключа логически равны, то их хэш-коды также должны быть равны. С другой стороны, если два ключа имеют одинаковый хэш-код, вполне вероятно, что это один и тот же ключ, но также возможно, что это разные ключи. Вам нужно сравнить их, чтобы убедиться, что они действительно совпадают. По закону противопоставления вы можете вывести другое следствие из первого:
hash(a) ≠ hash(b) ⇒ a ≠ b
Если вы знаете, что два ключа имеют разные хэш-коды, то нет смысла их сравнивать. Это может помочь повысить производительность, поскольку проверка на равенство, как правило, является дорогостоящей.
Некоторые IDE предлагают автоматически генерировать методы .__hash__() и .__eq__() для вас, но вам нужно помнить о необходимости их повторного создания при каждом изменении атрибутов вашего класса. Поэтому, по возможности, придерживайтесь классов данных Python или именованных кортежей, чтобы гарантировать правильную реализацию хэшируемых типов.
Заключение
На этом этапе вы можете  реализовать хэш-таблицу с нуля на Python, используя различные стратегии для устранения коллизий хэшей. Вы знаете, как сделать так, чтобы ваша хэш-таблица динамически изменяла размер и перефразировала , чтобы вместить больше данных, и как сохранить  порядок вставки пар ключ-значение. Попутно вы практиковались в разработке на основе тестирования (TDD), шаг за шагом добавляя функции в свою хэш-таблицу.
Кроме того, вы хорошо разбираетесь во встроенной функции Python hash() и можете создать свою собственную. Вы понимаете, что такое контракт с равным хэшем, разницу между хэшируемыми и  не хэшируемыми типами данных, а также их связь с неизменяемыми типами. Вы знаете, как создавать пользовательские классы с возможностью хэширования, используя различные инструменты в Python.
 В этом уроке вы узнали:

Чем хэш-таблица отличается от словаря
Как вы можете реализовать хэш-таблицу с нуля на Python
Как вы можете справиться с коллизиями хэшей и другими проблемами
Каковы желаемые свойства хэш-функции
Как  hash() работает Python за кулисами

Обладая этими знаниями, вы будете готовы ответить на большинство вопросов, которые могут возникнуть у вас на  собеседовании при приеме на работу, связанных с хэш-таблицей данных структура.
Вы можете загрузить полный исходный код и промежуточные шаги, используемые в этом руководстве, перейдя по ссылке ниже:
 Исходный код:  Нажмите здесь, чтобы загрузить исходный код, который вы будете использовать для создания хэш-таблицы на Python.
<статус завершения article-slug="python-хэш-таблица" class="btn-group mb-0" data-api-article-bookmark-url="/api/v1/articles/python-хэш-таблица/bookmark/" data-api-article-завершение-status-url="/api/версия 1/статьи/python-хэш-таблица/завершение_статуса/">



<кнопка поделиться bluesky-text="Интересная статья на #Python от @realpython.com :" email-body="Ознакомьтесь с этой статьей о Python:%0A%0создаем хэш-таблицу на Python с помощью TDD" email-subject="Статья о Python для вас" twitter-text="Интересная статья о #Python от @realpython:" url="https://realpython.com/python-hash-table /" url-title="Создать хэш-таблицу на Python с помощью TDD">


                







                 Back to Top