О реализации Java HashMap

Question

Почему емкость должна быть кратной или 2? Зачем использовать «&» в функции indexFor? Зачем перекомпилировать хеш в хэш-функции вместо прямого использования хеш-кода ключа?

Я думаю, что существуют некоторые важные различия между этой реализацией и описанием «Введение в алгоритм».

Что означает «>>>»?

static int hash(int h) { 
     // This function ensures that hashCodes that differ only by 
     // constant multiples at each bit position have a bounded 
     // number of collisions (approximately 8 at default load factor). 
     h ^= (h >>> 20)^(h >>> 12); 
     return h^(h >>> 7)^(h >>> 4); 
} 

Может ли кто-нибудь дать мне руководство? Я ценю Если кто-то может объяснить хэш-алгоритм. Спасибо большое!

Answer 1

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

table_index = hash_code % table_length; 

Оператор % дорого. Если table_length является степенью 2, то расчет:

table_index = hash_code & (table_length - 1); 

эквивалентно (много) более дорогой операции по модулю.

Answer 2

Не обращайте внимания на человека за занавеской.

Фактический алгоритм, без сомнения, представляет собой комбинацию «то, что чувствует себя хорошо» для разработчика, исправляет некоторые нечетные вырожденные случаи и простую традицию (для которой пользователи часто разрабатывают неясные зависимости).

И заметьте:

* Applies a supplemental hash function to a given hashCode, which 
* defends against poor quality hash functions. This is critical 
* because HashMap uses power-of-two length hash tables, that 
* otherwise encounter collisions for hashCodes that do not differ 
* in lower bits. Note: Null keys always map to hash 0, thus index 0. 

Net: До тех пор, как она работает, и производительность хорошая, вы не заботитесь.