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

Question

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

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

Answer 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)