Ответ 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 являются простыми числами и, следовательно, менее вероятно, что они приводят к возникновению коллизий, умножая/делясь на те же самые ведра, что и предыдущая, и другая строка.