Почему хэш-функция возвращает size_t и как она используется?

Question

Я понимаю математическую основу для хеш-таблиц.У меня есть хеш-функция (которую я где-то нашел) ниже:

/* Fowler / Noll / Vo (FNV) Hash */
static const size_t InitialFNV = 2166136261U;
static const size_t FNVMultiple = 16777619;
size_t myhash(const string &s, int length)
{
    size_t hash = InitialFNV;
    for(size_t i = 0; i < length; i++)
    {
        //XOR the lower 8 bits
        hash = hash ^ (s[i]);

        //Multiply by the multiple
        hash = hash * FNVMultiple;
    }
    return hash;
}

1. Почему это возвращает size_t?
2. Как можно использовать это, чтобы написать store() функция, которая помещает строку в хеш-таблицу?
3. Как это можно адаптировать для массива символов?
4. Что касается # 3, было бы целесообразно заменить forцикл с while цикл, который заканчивается на '\0' символ?

К вашему сведению, я готовлюсь ко второму собеседованию, и поэтому я спрашиваю.

Answer 1

1. Возвращает size_t, потому что это родное целое число (также самое быстрое). Зачем выбирать что-то еще?

2. "Стол"? Какой стол? Если вы имеете в виду хеш-таблицу, то вы можете использовать возвращаемое значение, чтобы выбрать случайное ведро для помещения объекта. (Подсказка: подумайте «остаток».)

3. Разве он уже не адаптирован для массива?

4. Если это строка с нулевым символом в конце, почему бы и нет?

Answer 2

string содержит свою собственную длину, вам не нужно передавать ее. Это C ++, а не C- нет ссылок в C. Нет необходимости в strlen или чем-то подобном, или NULL терминаторахили любой другой.Это означает, что заменить его циклом while, ищущим \0, было бы Bad ™, поскольку нет гарантии, что у std::string даже есть такой, не говоря уже о том, что он имеет терминатор.

Answer 3

1. Это не обязательно должно быть size_t, но, вероятно, это должен быть целочисленный тип без знака, чтобы мод был хорошо определен.

2. Обычным способом является использование хеш-функции для преобразования данных «ключа» в индекс массива. Таким образом, вы изменяете размер массива, чтобы получить целое число от 0 до SIZE-1, которое вы можете использовать в качестве индекса. Вам также понадобится «стратегия разрешения коллизий», потому что, если хеш не дает идеальных результатов, некоторые пары ключей, которые отличаются, будут хэшировать до одного и того же значения.

3. Кажется, он уже адаптирован.

4. Если строка заканчивается на NUL, вы можете искать ноль. Но функции, как написано, передается длина в качестве аргумента. Проще всего оставить рабочую функцию в покое и вызвать ее с результатом strlen ().

Ps. const string &s означает C ++, , а не C. Это может быть важно при компиляции.