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

Question

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

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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

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

Answer 5

Хочу отметить, что словарь - это хеш-таблица, но НЕ наоборот.

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

Однако с Python это не имеет большого значения, потому что вы явно не объявляете типы данных.