Вопрос по python, hash, hashtable, hashmap, dictionary – Является ли словарь Python примером хеш-таблицы?

148

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

Вот выступление Брэндона Крейга Роудса о том, как работает словарь Python,youtube.com/watch?v=C4Kc8xzcA68. chandola
Если вы заинтересованы в технических деталях, одна статья вBeautiful Code имеет дело с внутренностями Pythondict реализация. Torsten Marek
Это была одна из моих любимых глав в Beautiful Code. DGentry
Я некоторое время искал диаграмму, представляющую dict, которая расшифровывает реализацию в памяти и CPython. Спасибо за ссылку на книгу! Chen A.

Ваш Ответ

4   ответа
6

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

a = {}
b = ['some', 'list']
a[b] = 'some' # this won't work
a[tuple(b)] = 'some' # this will, same as a['some', 'list']
201

Да, это хеш-таблица или хеш-таблица. Вы можете прочитать описание реализации 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 а такжепочему так реализовано.

Но используя.keys() можно получить список ключей. Настоящая хеш-таблица не хранит ключи, а просто хэши для экономии места.
Швы связи Тима Петерса должны быть нарушены, есть ли чистая связь там?
Более полное описание реализации python dict здесь:laurentluce.com/posts/python-dictionary-implementation
@MattAlcock: я обновил ссылку. Иногда (обычно из-за того, что кто-то хочет удалить свой адрес электронной почты), архивы списков Python перестраиваются, и идентификаторы писем меняются, тем самым нарушая эти ссылки. Администраторы пидоторг обычно стараются избегать этого в наши дни.
19

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

20

Для словаря Python должно быть нечто большее, чем поиск по таблице в hash (). Путем грубых экспериментов я нашел этоhash collision:

>>> 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).)

@YanfengLiu Я полагаю, что это те же самые вещи, которые сделала TurnipEntropy.
Коллизии случаются в общем случае, потому что существует бесконечно много возможных значений хеширования и конечных хеш-кодов. Даже хэш-таблица должна была бы как-то обрабатывать столкновения.
Так что столкновения неизбежны. Набор S может содержать бесконечно большое количество элементов, и вы хотите, чтобы он хэшировал число, которое может хранить компьютер. Каждая используемая реализация хеш-таблицы разрешает коллизии, при этом два наиболее частых метода: а) открытая адресация и б) цепочка. То, что он не использует идеальный хэш, не означает, что он не является хэш-таблицей.
Есть обходные пути для столкновений.
Оно использует__eq__ разрешать коллизии.

Похожие вопросы