«Нормализовать» хэш ключа в HashMap
HashMap хранит свои данные в сегментах как:
transient Node<K,V>[] table;
Чтобы поместить что-то в HashMap, нам нужна функция hash (), которая возвращает хэш Key в диапазоне от 0 до table.length (), верно?
Предположим, у меня есть:
String s = "15315";
// Just pasted internal operation. Is it supposed to calcule hash in table.length range?
int h;
int hmhc = (h = s.hashCode()) ^ (h >>> 16);
System.out.println("String native hashCode: "+s.hashCode() + ", HashMap hash: "+hmhc);
Это возвращает следующее:
String native hashCode: 46882035, HashMap hash: 46882360
У нас должно быть примерно 256 сегментов (так что хеш ключа должен быть в диапазоне от 0 до 256), но внутренний хеш в HashMap дает нам 46882360. Как «нормализовать» этот хеш к нашему диапазону? Я просто не вижу этого в исходном коде.
Я посмотрел на этот jdk (put () начинается со строки 610): http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java
Ответы 1
Обычно возвращаемый хэш-код берется по модулю количества сегментов.
В вашем случае он попадет в корзину 46882360 % 256 = 56.
@GeorgeZorikov Посмотрите, как индексируется таблица - (n - 1) & hash, который выбирает индекс на основе битов в хеш-коде.
Я понял! Они используют (table.length () - 1) & hmhc. Поскольку наша длина всегда является степенью 2, оператор по модулю может быть заменен оператором побитового И. Спасибо!
Да, как я мог об этом забыть ... Но в данном JDK нет оператора по модулю. Можете помочь найти в нем "нормализацию"? put () начинается со строки 610