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

Ответ 1

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

Ответ 2

Если вас интересуют технические подробности, одна статья в Beautiful Code посвящена внутренним реализациям Python dict.

Ответ 3

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

Ответ 4

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

Ответ 5

Развернуть объяснение nosklo:

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