Основная проблема с использованием % capacity
заключается в том, что он может возвращать отрицательные и положительные значения.
HashMap позволяет избежать этой проблемы, используя степень 2, и использует следующий подход
public int getIndex(K key) { return hash(key.hashCode()) & (capacity-1); }
Если емкость не является степенью 2, вы можете игнорировать старший бит (который часто не так уж случайен)
public int getIndex(K key) { return (hash(key.hashCode()) & 0x7FFFFFFF) % capacity; }
Фактически используемая хеш-функция может иметь значение. HashMap использует следующее
/**
* 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.
*/
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);
}
Я бы использовал это, если у вас нет веских причин не делать этого. Например. по соображениям безопасности, если у вас есть служба, которая может быть объектом атаки типа «отказ в обслуживании», вы захотите использовать другой хеш, чтобы избежать того, что злоумышленник превратит вашу HashMap в LinkedList. К сожалению, вам по-прежнему нужно использовать другой hashCode (), а также вы можете создать длинный список строк с базовым хеш-кодом, поэтому изменять его позже будет позже.
Вот список строк, у всех из которых hashCode () равен 0, функция hash () ничего не может с этим поделать.
Почему String hashCode () не кеширует 0?