Словарь Python является примером хеш-таблицы?
Одной из основных структур данных в Python является словарь, который позволяет записывать «ключи» для поиска «значений» любого типа. Это реализовано внутри как хеш-таблица? Если нет, то что это?
Если вас интересуют технические детали, одна статья в Красивый код посвящена внутреннему устройству реализации Python dict.
Это была одна из моих любимых глав в Beautiful Code.
Некоторое время я искал диаграмму, представляющую dict, которая расшифровывает реализацию в памяти и CPython. Спасибо, что сослались на книгу!
Ответы 4
Да, это хеш-отображение или хеш-таблица. Вы можете прочитать описание реализации Python dict, написанное Тимом Петерсом, здесь.
Вот почему вы не можете использовать что-то `` не хешируемое '' в качестве ключа dict, например список:
>>> a = {}
>>> b = ['some', 'list']
>>> hash(b)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: list objects are unhashable
>>> a[b] = 'some'
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: list objects are unhashable
Вы можете узнать больше о хеш-таблицах или проверьте, как это реализовано в Python и почему это реализовано именно так.
Соединительные швы Тима Петерса должны быть разорваны, есть ли чистая ссылка?
@MattAlcock: Я обновил ссылку. Иногда (обычно из-за того, что кто-то хочет, чтобы их адрес электронной почты был где-то удален), архивы списков python перестраиваются, а идентификаторы электронных писем меняются, тем самым нарушая эти ссылки. В наши дни админы pydotorg обычно стараются избегать этого.
Но с помощью .keys() можно получить список ключей. Настоящая хеш-таблица не хранит ключи, а только хеши для экономии места.
Более полное описание реализации python dict здесь: laurentluce.com/posts/python-dictionary-implementation
@ noɥʇʎԀʎzɐɹƆ - сам ключ не сохраняется, только ссылка на него и хеш.
Да. Внутренне это реализовано как открытое хеширование на основе примитивного полинома по Z / 2 (источник).
Чтобы расширить объяснение Носкло:
a = {}
b = ['some', 'list']
a[b] = 'some' # this won't work
a[tuple(b)] = 'some' # this will, same as a['some', 'list']
В словаре Python должно быть что-то большее, чем поиск в таблице с помощью hash (). Путем грубого экспериментирования я нашел это хеш-коллизия:
>>> hash(1.1)
2040142438
>>> hash(4504.1)
2040142438
Но это не ломает словарь:
>>> d = { 1.1: 'a', 4504.1: 'b' }
>>> d[1.1]
'a'
>>> d[4504.1]
'b'
Санитарная проверка:
>>> for k,v in d.items(): print(hash(k))
2040142438
2040142438
Возможно, есть еще один уровень поиска помимо hash (), который позволяет избежать конфликтов между ключами словаря. Или, может быть, dict () использует другой хеш.
(Кстати, это в Python 2.7.10. Та же история в Python 3.4.3 и 3.5.0 с столкновением на hash(1.1) == hash(214748749.8).)
Так что столкновения неизбежны. Набор S может содержать бесконечно большое количество элементов, и вы хотите, чтобы он хешировал число, которое компьютер может сохранить. Каждая используемая реализация хеш-таблицы разрешает коллизии, причем двумя наиболее частыми методами являются: а) открытая адресация и б) цепочка. То, что он не использует идеальный хеш, не означает, что это не хеш-таблица.
Конфликты будут происходить в общем случае, потому что существует бесконечное количество возможных хешируемых значений и конечных хэш-кодов. Даже хеш-таблица должна как-то справляться с коллизиями.
@YanfengLiu Я считаю, что это в точности те же самые пункты, что и TurnipEntropy.
В Python 3.7 похоже, что на самом деле существует 2E20 минус 1 возможное значение хэша. От -1E20 минус 1 до (+) 1E20 минус 1. Попробуйте hash('I wandered lonely as a cloud, that drifts on high o\'er vales and hills, when all at once, I saw a crowd, a host of golden daffodils.'). Это дает 19-значное десятичное число - -4037225020714749784, если вы достаточно фанатичны, чтобы заботиться о нем. Продолжайте своими словами, дети, и хеш по-прежнему будет 19-значным числом. Я предполагаю, что существует ограничение на длину строки, которую вы можете хэшировать в Python, но с уверенностью можно сказать, что возможных строк намного больше, чем возможных значений. А hash(False) = 0 кстати.
Причина, по которой он не нарушает словарь, заключается в том, что под капотом повторяющиеся значения реализуются с использованием связанного списка и хранятся вместе с указателем на ключ, из которого они были сгенерированы.
Вот выступление Брэндона Крейга Роудса, в котором обсуждается принцип работы словаря Python youtube.com/watch?v=C4Kc8xzcA68.