Какой хэш-алгоритм использует сопоставление словарей Python?

Я возился с созданием синтаксического анализатора командной строки и задавался вопросом, какой из алгоритмов хеширования использует python dict?

Как я его настроил, у меня есть алгоритм соответствия шаблону, который соответствует токенизированным входным последовательностям со словарным ключом. Некоторые из ключей относительно длинны (длина 5 или 6 кортежей из 6-7 символов). Мне было интересно, есть ли точка, при которой длинные словарные ключи значительно уменьшают эффективность поиска ключей.

Ответы

Ответ 1

Используемый хэш зависит от того, какой объект используется в качестве ключа - каждый класс может определить свой собственный метод __hash __(), а значение, которое оно возвращает для конкретного экземпляра, - это то, что используется для словаря.

Сам Python предоставляет хэш-реализацию для типов str и tuple. Быстрый взгляд на источник должен выявить точный алгоритм для них.

Хэш кортежа основан на хэшах его содержимого. Алгоритм по существу этот (упрощенный):

def hash(tuple):
    mult = 1000003
    x = 0x345678
    for index, item in enumerate(tuple):
        x = ((x ^ hash(item)) * mult) & (1<<32)
        mult += (82520 + (len(tuple)-index)*2)
    return x + 97531

Для строк интерпретатор также выполняет итерацию по каждому символу, комбинируя их с этим (еще немного упрощенным) алгоритмом:

def hash(string):
    x = string[0] << 7
    for chr in string[1:]:
        x = ((1000003 * x) ^ chr) & (1<<32)
    return x

Большая проблема, о которой нужно беспокоиться, - избегать хеш-коллизий. Столкновение хеш-ключей приведет к линейному поиску, поскольку словарь пытается найти место для хранения нового объекта (это теперь распознается как проблема безопасности, и поведение может меняться в будущих версиях python)