Есть ли лучший способ модулировать значение хэша в этом случае?

Question

я заметил, что строка, которая содержит нечетное количество специфического характера, скажем, «б» имеет значение хеш-функции, которое

kM+r 

где k и r целые и M сила A 2 в. Например, все из следующих строк приводит к тому же значению после модулирования M, если M является 2 по мощности (скажем, 16):

"b"   hashCode("b") = 98,   98%16 = 2 
"bbb"  hashCode("bbb") = 97314,  97314%16 = 2 
"bbbbb"  hashCode("bbbbb") = 293521890, 293521890%16 = 2 
... 

Если я использую использовать следующую формулу (reference) для модуляции значение хеш-функции, все вышеперечисленные строки хеша к тому же ведру, что определенно NOT что мы хотим.

int bucket_id = (hashCode(str) & 0x7fffffff) % M; 

Я делаю что-то неправильно здесь?

Answer 1

Обычно реализация хэш-таблицы выполняет дополнительное преобразование объекта hashCode перед назначением ведра. Например, вот как это реализовано в OpenJDK 8 java.util.HashMap:

static final int hash(Object key) { 
    int h; 
    return (key == null) ? 0 : (h = key.hashCode())^(h >>> 16); 
} 

Это делает более равномерное распределение. Java-7 используется еще более сложные преобразования, что-то вроде этого:

int h = key.hashCode(); 
h ^= (h >>> 20)^(h >>> 12); 
return h^(h >>> 7)^(h >>> 4); 

Кажется, что это было установлено, что излишне сложным, как Java-8 упростил.

Также определено, что ковш имеет hash(key) & (n-1), где n - количество ковшей. Как и в большинстве реализаций хэш-таблицы, количество ведер - это сила двух, такая формула работает хорошо.

И наконец, для защиты от коллизий (случайных или преднамеренных), в Java реализован новый алгоритм, который создает двоичное дерево в кодах, содержащих слишком много элементов (если ключи Comparable). Это делает поиск в переполненном ковше O(log n) вместо O(n).