Как работает поиск хэшей в словарях Python?
Как алгоритмы поиска по словарю Python работают внутри?
mydi['foo']
Если в словаре 1 000 000 терминов, выполняется ли поиск по дереву? Могу ли я ожидать производительности с точки зрения длины ключевой строки или размера словаря? Может быть, вставить все в словарь так же хорошо, как написать индекс поиска по дереву для строк размером 5 миллионов?
5 ответов
Вот некоторый псевдокод, ближе к тому, что на самом деле происходит. Представьте, что в словаре есть атрибут data, содержащий ключ, пары значений и size, который представляет собой количество выделенных ячеек.
def lookup(d, key):
perturb = j = hash(key)
while True:
cell = d.data[j % d.size]
if cell.key is EMPTY:
raise IndexError
if cell.key is not DELETED and (cell.key is key or cell.key == key):
return cell.value
j = (5 * j) + 1 + perturb
perturb >>= PERTURB
Значение perturb гарантирует, что все биты хеш-кода в конечном итоге используются при разрешении хеш-столкновений, но как только он уменьшится до 0, (5*j)+1 в конечном итоге коснется всех ячеек в таблице.
size всегда намного больше, чем количество фактически используемых ячеек, поэтому хеш гарантированно попадет в пустую ячейку, когда ключ не существует (и обычно должен ударить одну довольно быстро). Также есть удаленное значение для ключа, чтобы указать ячейку, которая не должна завершать поиск, но которая в данный момент не используется.
Что касается вашего вопроса о длине ключевой строки, то при хешировании строки будут просматриваться все символы в строке, но в строке также есть поле, используемое для хранения вычисленного хэша. Таким образом, если вы каждый раз используете разные строки для поиска, длина строки может иметь значение, но если у вас есть фиксированный набор ключей и вы повторно используете те же строки, хэш не будет пересчитан после первого использования , Python получает выгоду от этого, так как большинство поисков имен включает словари, и одна копия каждой переменной или имени атрибута хранится внутри, поэтому каждый раз, когда вы обращаетесь к атрибуту x.y, происходит поиск в словаре, но не вызов хеш-функции.
Как вы упомянули в заголовке, dicts - это хеш-таблицы. Поиск по дереву не используется. Поиск ключа - это операция с почти постоянным временем, независимо от размера диктовки.
Вам могут пригодиться ответы на этот вопрос: Как реализованы встроенные словари Python
Вот хорошее объяснение: http://wiki.python.org/moin/DictionaryKeys
Псевдокод сверху по ссылке:
def lookup(d, key):
'''dictionary lookup is done in three steps:
1. A hash value of the key is computed using a hash function.
2. The hash value addresses a location in d.data which is
supposed to be an array of "buckets" or "collision lists"
which contain the (key,value) pairs.
3. The collision list addressed by the hash value is searched
sequentially until a pair is found with pair[0] == key. The
return value of the lookup is then pair[1].
'''
h = hash(key) # step 1
cl = d.data[h] # step 2
for pair in cl: # step 3
if key == pair[0]:
return pair[1]
else:
raise KeyError, "Key %s not found." % key
В хэш-поисках не используются деревья. Они используют хеш-таблицу, и они берут постоянный поиск времени. Они будут занимать больше места (в среднем, я полагаю, вдвое больше), чем дерево, но время поиска и вставки выигрывает.
Чтобы упростить задачу, возьмите md5 своего ключа и измените его, указав количество адресов, которое у вас есть, и там, где вы сохраняете или ищите ключ. Неважно, насколько большой набор, он всегда будет занимать одинаковое количество времени, пока у вас нет значительного столкновения, которого избежит хороший хеш.
Ответ 1: Внутренняя работа объясняется в этом видео
Ответ 2: Нет, поиск по дереву не выполняется, если в словаре имеется миллион записей.
Ответ 3: Поскольку могут быть конфликты клавиш, вы ожидаете производительность в терминах размера словаря, а не в терминах длины строки ключа.
Ответ 4: Рассматривайте словарь как массив (смежные области памяти), но в массиве могут быть блоки, которые не используются. Следовательно, словари имеют тенденцию тратить много места в памяти по сравнению с деревьями. Но для лучшей производительности во время выполнения словари могут быть лучше, чем деревья. Ключевые столкновения могут иногда ухудшать производительность. Вы должны прочитать о последовательном хешировании.