HashMap может отличаться индексом ковша для ключа?

Question

Моя забота заключалась в том, чтобы проверить, как Java HashMap получает тот же самый индекс для ключа. Даже когда размер увеличивается от значения по умолчанию 16 до гораздо более высоких значений, мы продолжаем добавлять записи.

Я попытался воспроизвести алгоритм индексирования HashMap.

int length=1<<5; 
int v=6546546; 
int h = new Integer(v).hashCode(); 
h =h^((h >>> 20)^(h >>> 12)); 
h=h^h >>> 7^h >>> 4; 
System.out.println("index :: " + (h & (length-1))); 

Я запустил свой код для разных значений «длина». Так что для одного и того же ключа я получаю разные индексы, так как изменяется длина HashMap. Что мне здесь не хватает?

Мои результаты:

length=1<<5; 
index :: 10 

length=1<<15; 

index :: 7082 

length=1<<30; 
index :: 6626218 

Answer 1

Вы упускаете тот факт, что каждый раз, когда изменения длины, записи перераспределяются - они помещаются в новые ведра надлежащим образом. Вот почему требуется некоторое время (O (N)), когда карта расширяется - все нужно скопировать из старых ковшей в новые.

Если у вас только есть индексы по одной длине за раз (а не смесь), вы в порядке.