Является ли словарь Python примером хеш-таблицы?

187

Одна из основных структур данных в Python - это словарь, который позволяет записывать «ключи» для поиска «значений» любого типа. Это реализовано внутри как хеш-таблица? Если нет, то что это?

Томми Герберт
источник
2
Если вас интересуют технические детали, одна статья в Beautiful Code посвящена внутренним элементам dictреализации Python .
Торстен Марек
Это была одна из моих любимых глав в Beautiful Code.
Джентри
4
Вот выступление Брэндона Крейга Роудса о том, как работает словарь python, youtube.com/watch?v=C4Kc8xzcA68 .
Чандола
Я некоторое время искал диаграмму, представляющую dict, которая расшифровывает реализацию в памяти и CPython. Спасибо за ссылку на книгу!
Чен А.

Ответы:

241

Да, это хэш-отображение или хеш-таблица. Вы можете прочитать описание реализации dict в python, написанное Тимом Питерсом, здесь .

Вот почему вы не можете использовать что-то «не хэшируемое» в качестве ключа, как список:

>>> 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 и почему это реализовано таким образом .

nosklo
источник
1
Швы связи Тима Петерса должны быть нарушены, есть ли чистая связь там?
Мэтт Олкок
1
@MattAlcock: я обновил ссылку. Иногда (обычно из-за того, что кто-то хочет удалить свой адрес электронной почты), архивы списков Python перестраиваются, и идентификаторы писем меняются, тем самым нарушая эти ссылки. Администраторы пидоторг обычно стараются избегать этого в наши дни.
Мартин Питерс
Но используя .keys()можно получить список ключей. Настоящая хеш-таблица не хранит ключи, а просто хэши для экономии места.
noɥʇʎԀʎzɐɹƆ
Более полное описание реализации python dict здесь: laurentluce.com/posts/python-dictionary-implementation
Даниэль Голдфарб,
@ noɥʇʎԀʎzɐɹƆ - сам ключ не сохраняется, только ссылка на него и хеш.
носкло
32

Для словаря 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).)

Боб Стейн
источник
14
Так что столкновения неизбежны. Набор S может содержать бесконечно большое количество элементов, и вы хотите, чтобы он хэшировал число, которое может хранить компьютер. Каждая используемая реализация хеш-таблицы разрешает коллизии, при этом два наиболее распространенных метода: а) открытая адресация и б) цепочка. То, что он не использует идеальный хеш, не означает, что это не хеш-таблица.
Репа Энтропия
1
Коллизии случаются в общем случае, потому что существует бесконечно много возможных значений хеширования и конечных хеш-кодов. Даже хеш-таблица должна была бы как-то обрабатывать столкновения.
Янфэн Лю
3
@YanfengLiu Я полагаю, что это те же самые вещи, которые сделала TurnipEntropy.
Боб Стейн
1
В 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 кстати.
Уилл Кроксфорд
22

Да. Внутренне это реализовано как открытое хеширование на основе примитивного полинома над Z / 2 ( источник ).

Бен Хоффштейн
источник
7

Чтобы расширить объяснение Носкло:

a = {}
b = ['some', 'list']
a[b] = 'some' # this won't work
a[tuple(b)] = 'some' # this will, same as a['some', 'list']
Джереми Кантрелл
источник