Я возился с созданием синтаксического анализатора командной строки и задавался вопросом, какой из алгоритмов хеширования использует python dict?
Как я его настроил, у меня есть алгоритм соответствия шаблону, который соответствует токенизированным входным последовательностям со словарным ключом. Некоторые из ключей относительно длинны (длина 5 или 6 кортежей из 6-7 символов). Мне было интересно, есть ли точка, при которой длинные словарные ключи значительно уменьшают эффективность поиска ключей.
Используемый хэш зависит от того, какой объект используется в качестве ключа - каждый класс может определить свой собственный метод __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)