В прошлом сообщении упомянул, что самый очевидный способ написать свою хэш-функцию - “для каждого ключа-строки считаем сумму числовых значений символов в строке” - является неправильным. Резонный вопрос - что с ним не так?

Если подумать, можно сформулировать два критерия хорошей хэш функции - она должна быстро вычисляться и она должна давать минимальное количество коллизий. Т.е. если мы размещаем в хэш-таблице на m элементов n ключей, то в каждой ячейке должно оказаться примерно по n / m элементов.

Наш вариант хэш-функции явно быстро вычисляется, но что с распределением ключей по хэш-таблице? Рассчитаем такую хэш-функцию для 1000 случайных строк (длиной по 10 символов) и посмотрим сколько слов попадёт в каждую из ячеек хэш-таблицы на 100 элементов (хотелось бы чтобы везде по 10)

import random
import string


def generate_random_string(length):
    letters = string.ascii_lowercase
    rand_string = ''.join(random.choice(letters) for i in range(length))
    return rand_string


def hash_function(string):
    hash = 0
    for ch in string:
        hash += ord(ch)
    return hash % 100


hash_table = list((0 for i in range(100)))

for _ in range(1000):
    hash_table[hash_function(generate_random_string(10))] += 1
    
print(hash_table)

Строки случайные, поэтому раз на раз не приходится, но скорее всего получится что-то такое: [24, 17, 17, 13, 17, 18, 15, 10, 20, 14, 17, 14, 18, 11, 15, 15, 10, 15, 12, 8, 15, 9, 8, 7, 3, 4, 9, 7, 6, 8, 9, 10, 13, 6, 5, 6, 2, 4, 3, 2, 3, 1, 8, 4, 2, 5, 2, 2, 3, 2, 3, 2, 6, 5, 2, 1, 2, 4, 6, 10, 5, 7, 13, 5, 10, 11, 9, 8, 5, 6, 10, 4, 10, 9, 10, 12, 14, 7, 10, 19, 14, 15, 14, 17, 11, 23, 12, 10, 11, 12, 22, 9, 22, 11, 17, 13, 13, 26, 16, 19]

Не идеально, но более менее равномерно получилось. Ок, это были случайные строки, посмотрим что с реальными данными.

Возьмём 1000 самых частых английских слов https://github.com/powerlanguage/word-lists/blob/master/1000-most-common-words.txt и посмотрим распределение для них: [175, 638, 88, 118, 181, 279, 8, 51, 270, 126, 1298, 353, 143, 11, 369, 290, 384, 149, 52, 99, 14, 81, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 370, 87, 197]

На равномерное распределение совсем не похоже. Заметная часть ячеек пустая, большинство ключей группируются в небольшом количестве ячеек - соответственно, после того как хэш-функция даст ссылку на одну из таких ячеек, надо будет последовательно перебрать все значения там, чтобы убедиться есть там нужный ключ или нет.

Хорошая хэш-функция даёт равномерное распределение по хэш-таблице даже для незначительно различающихся строк. Собственно, один из показателей “правильности” хэш-функции это то, что незначительная разница на входе даёт огромную разницу на выходе (лавинный эффект).

Хэш-функций существует довольно много, под разные задачи. Одна из популярных - murmur2 (https://ru.wikipedia.org/wiki/MurmurHash2). Переписывать алгоритм на python сейчас не буду - воспользуюсь готовым модулем

from murmurhash2 import murmurhash2


SEED = 3242157231

hash_table = list((0 for i in range(100)))

for word in words:
    key = bytes(word, 'utf8')
    hash_table[murmurhash2(key, SEED) % 100] += 1
    
print(hash_table)

[405, 0, 0, 0, 0, 0, 0, 0, 14, 0, 998, 126, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 138, 82, 0, 0, 99, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0, 384, 0, 290, 0, 0, 143, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 279, 1, 638, 370, 570, 369, 0, 0, 0, 0, 0, 0, 0, 175, 11, 0, 0, 0, 0, 197, 0, 118, 0, 0, 0, 0, 0, 149, 88, 0, 0, 0, 181, 2] - неожиданно :)

Вообще я ожидал увидеть практически равномерное распределение. Надо разбираться