Есть ли имя для этой хэш-функции?

Question

Я довольно долго использовал интерпретатор Elk Scheme и иногда просматривал его исходный код.

Я заметил, что он содержит следующую хеш-функцию в symbol.c:

int Hash (char const *str, unsigned int len) {
    register int h;
    register char const *p, *ep;

    h = 5 * len;
    if (len > 5)
        len = 5;
    for (p = str, ep = p+len; p < ep; ++p)
        h = (h << 2) ^ *p;
    return h & 017777777777;
}

В исходном коде нет ничего, что описывает функцию.

Есть ли имя для этой хэш-функции?
Задокументирована ли где-нибудь схема хеширования?

Answer 1

Таким образом, это по сути тот же алгоритм, что и в классическом Fowler-Noll-Vo хэше, но вместо использования специально выбранного простого числа для множителя хеша, он использует 4 (смещение числа влево на 2 - это то же самое, что умножение на 4). Начальное начальное значение хэша также отличается; 5 * len вместо постоянного значения.

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

Последняя строка return h & 017777777777; тоже интересна. Эта восьмеричная константа при условии типичного 32-битного комплимента 2 int, INT_MAX. Это то, что вы увидите, если вычислить 64-битный хеш, но вернуть только младшие 32 бита, но для 32-битного типа это не работает. Может быть, автор был параноидален в отношении переносимости систем с большим типом int? Но если он используется только в том месте, где возвращаемое значение хеша берется по модулю длины массива, зачем беспокоиться? Или, может быть, h был задуман как unsigned int, но они не хотели использовать полный диапазон этого типа (или убедитесь, что он никогда не был отрицательным, когда превращается в значение со знаком)?