Пара вопросов о хеш-таблицах

Question

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

В качестве справки я читал это: http://eternallyconfuzzled.com/jsw_home.aspx

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

Каков оптимальный размер хеш-таблицы? На чем я должен основывать свое решение?

2) Кроме того, на этом сайте есть пара функций хеширования, которые я еще не прочитал. В нем также говорится, что всегда лучше использовать хорошо известный алгоритм и использовать мой собственный. И я мог бы сделать это, я выберу один с этого сайта и протестирую его в своем коде и посмотрю, минимизирует ли он коллизии на основе моих входных данных.

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

Answer 1

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

С хорошей хэш-функцией, среднее стоимость поиска почти постоянна, так как коэффициент загрузки увеличивается от 0 до 0,7 или так. Помимо этого, вероятность столкновений и стоимость обработки их увеличивается.

Я считаю, что реализация Java (и, возможно, другие) периодически изменяет размер, чтобы сохранить коэффициент загрузки в допустимом диапазоне.

2) Просто используйте оператор по модулю (%), чтобы индекс корзины был легальным. Второй оператор должен быть размером вашего массива сегментов.

Answer 2

Выберите маленький размер для вашей хеш-таблицы. Когда вы добавляете что-то к своей таблице, проверьте, какой процент этой таблицы используется; когда он заполнен более чем на 70%, увеличьте таблицу. Это также относится и к удалению элементов - например, уменьшите таблицу, если она заполнена менее чем на 60%. В Википедии есть хорошее описание некоторых стратегий динамического изменения размера, но это общая идея.

Я говорю это только потому, что вам, похоже, известны входные данные:

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

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