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

Question

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

Answer 1

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

Вот почему вы не можете использовать что-то «не hashable» в качестве ключа 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 

Вы можете read more about hash tables или check how it has been implemented in python и why it is implemented that way.

Answer 2

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

Answer 3

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

Answer 4

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

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, чем табличного на хэш(). По грубому экспериментированию я нашел это хэш столкновение:

>>> hash(1.1) 
2040142438 
>>> hash(4504.1) 
2040142438 

Но это не нарушает словарь:

>>> d = { 1.1: 'a', 4504.1: 'b' } 
>>> d[1.1] 
'a' 
>>> d[4504.1] 
'b' 

Sanity проверка:

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