Как работает поиск хеша в словаре 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: Рассмотрите словарь как массив (смежные области памяти), но в массиве могут быть блоки, которые не используются. Следовательно, словари имеют тенденцию тратить много места в памяти по сравнению с деревьями. Но для лучшей производительности во время выполнения словари могут быть лучше, чем деревья. Ключевые столкновения могут иногда ухудшать производительность. Вы должны прочитать о последовательном хешировании.

Источник
Другие вопросы по тегам