Слишком много коллизий хеш-функции

Question

Я пытаюсь создать функцию хеширования с использованием метода полиномиального накопления (который должен дать вам 5 столкновений на 55 000 слов или что-то в этом роде), но когда я запускаю его с 1000 словами, я получаю ~ 190 столкновений.Я что-то не так делаю?

public int hashCode(String str) {
        double hash_value = 0; // used for float
        for (int i = 0; i < str.length(); i++){
            hash_value = 33*hash_value + str.charAt(i);
        }
        return (int) (hash_value % array_size);
    }

Answer 1

Как правило, простые числа предпочтительнее для генерации хеш-кода.Я предлагаю попробовать 109 или 251. 33 кратно 3, что означает, что у вас, скорее всего, будут проблемы, основанные на ваших входных данных.

Также вы должны использовать int для расчетов и вызывать Math.abs для результата.

Answer 2

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

"bA" = 98+(33x65)=2243
"AB" = 65+(33x66)=2243

Если вы выберете большое число больше 57, вероятность столкновения будет меньше.109 или 251 будет хорошим выбором.

Answer 3

Либо ваш набор данных чрезвычайно "неудачлив", либо (что более вероятно) array_size слишком мало (параметры хеш-функции обычно заключаются в кавычки без учета конечного размера массива сегмента).