Одной из основных структур данных в Python является словарь, который позволяет записывать «ключи» для поиска «значений» любого типа. Это реализовано внутри как хеш-таблица? Если нет, то что это?
Является ли словарь Python примером хеш-таблицы?
Ответы (4)
Да, это хеш-отображение или хэш-таблица. Вы можете прочитать описание реализации 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 и почему это реализовано таким образом.
.keys()
можно получить список ключей. Настоящая хеш-таблица не будет хранить ключи, а только хэши для экономии места.
- person noɥʇʎԀʎzɐɹƆ; 11.05.2016
В словаре 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)
.)
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 кстати.
- person Will Croxford; 11.06.2019
да. Внутри он реализован как открытое хеширование на основе примитивного полинома над Z/2 (источник).
Чтобы расширить объяснение nosklo:
a = {}
b = ['some', 'list']
a[b] = 'some' # this won't work
a[tuple(b)] = 'some' # this will, same as a['some', 'list']
dict
реализация. - person Torsten Marek   schedule 22.09.2008