Как работает эта хеш-функция? Являются ли эти цифры случайными?

Сейчас я читаю книгу K & R "C Programming Language". В главе "Структуры" под подтемой "Поиск в таблице" (Страница 144) я нашел эту функцию генерации хэша

#define HASHSIZE 101

struct nlist {
    struct nlist *next;
    char *name;
    char *defn;
}

static struct nlist *hashtab[HASHSIZE];

unsigned hash(char *s)
{
    unsigned hashval;

    for (hashval = 0; *s != '\0'; s++)
        hashval = *s + 31 * hashval;
    return hashval % HASHSIZE;
}

Я не понимаю, что на самом деле делает эта функция.

Я думаю, что он генерирует уникальный адрес (как индекс для hashtab) для данной строки (char * s).

Но мне кажется, что двум различным строкам может присваиваться один и тот же индекс, поскольку (hashval% HASHSIZE) - данный адрес (203% 101 = 405% 101 = 1).

И почему HASHSIZE 101 и hashval умножаются на 31? Почему не 100 или 32?

Ответ 1

То, что я не понимаю, это то, что эта функция действительно делает?

Он в основном хэширует строку, на которую указывает указатель char *s, пока не встретит конец строки, которая отмечена нулевым символом '\0'. Другими словами, он вычисляет (или отображает) заданную входную строку в целочисленное значение.

Вы также можете увидеть, что он делает это, просматривая каждый символ в строке (т.е. s++), делая временную сложность этой функции линейно зависимой от длины строки - или O(N) - и что она избегает генерации значения, выходящего за пределы массива с конечной работой модуля.

Я думаю, что он генерирует уникальный адрес (как индекс для hashtab) для данной строки (char * s).

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

Но мне кажется, что двум различным строкам может присваиваться один и тот же индекс, поскольку (hashval% HASHSIZE) - данный адрес (203% 101 = 405% 101 = 1).

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

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

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

На этих страницах написаны главы книг, в основном, когда дело доходит до поиска, поэтому вы можете прочитать их.

И почему HASHSIZE равно 101, а hashval умножается на 31 (почему не 100 или 32)?

Поскольку 101 и 31 являются простыми числами и, следовательно, менее вероятно, что они приводят к возникновению коллизий, умножая/делясь на те же самые ведра, что и предыдущая, и другая строка.

Ответ 2

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

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