Сложность словарей и хэш-таблиц

Question

У меня есть некоторая путаница по словарям и хэш-таблицам, которые я хотел бы уточнить. Предположим, у меня есть текущий словарь и текущий вывод хэшей текущего запуска python.

Dict = dict() 
print(hash('a')) 
print(hash('b')) 
print(hash('c')) 
Dict['a'] = 1 
Dict['b'] = 2 
Dict['c'] = 3 
print(Dict) 

имеет выход

1714333803 
1519074822 
1245896149 
{'a': 1, 'c': 3, 'b': 2} 

Так мне известно, хэш-таблице это просто массив, где хэш индекс Hashtable. Например, «a» имел хэш 1714333803, поэтому мой индекс хэш-таблицы 1714333803 имеет значение «a». Таким образом, я путал, сколько индексов имеет хэш-таблица и как функция хеширования дает ответ? Использует ли он модуль и имеет фиксированный диапазон индексов? Поскольку данная печать словаря выводит {'a': 1, 'c': 3, 'b': 2}, но правильно ли предположить, что событие, хотя оно выводит это, словарь на самом деле представляет собой набор индексов по крайней мере 1714333803, потому что это кажется смехотворно излишним, чтобы содержать 3 элемента и не говоря уже о том, сколько пустой тратой пространства. Также для хэш-таблицы, что есть в индексах, которые не имеют значения, null?

Answer 1

Фактический размер dict зависит от реализации, но в вашем случае это, вероятно, 8. Итак, как это работает?

Принцип работы dict (или хэш-карты в общем случае) заключается в вычислении числового хеша для каждого ключа. Например, в вашем случае это hash("a") == 1714333803. Теперь хэш не используется напрямую как индекс. Вместо этого он отображается на размер словаря.

Простым способом для этого является modulo (%). Скажем, ваш dict имеет 8 размеров. Затем hash("a") % 8 == 1714333803 % 8 == 3. Таким образом, ваш предмет находится на 4-й позиции. Ни один элемент никогда не может иметь индекс за пределами массива.

Здесь есть несколько более сложных вещей, таких как столкновения хэшей. Например, если другой элемент имеет хеш 98499, то также соответствует 3. Существуют стратегии разрешения конфликтов, которые в этом случае выбирают другой показатель.

Итак, почему ваш dict размера 8? Потому что это default size in python. Как только ваш dict получите слишком маленький, его необходимо изменить. В отличие от массивов, это делается до того, как dict действительно заполнен, а именно: two thirds filling. Это делается для уменьшения хеш-коллизий - если ваш dict на 99% заполнен, столкновение практически гарантировано. Для размера 8 dict вам нужно будет ввести 5-6 элементов до его изменения, а именно doubles its capacity - 16.