Это простая Java HashMap, как элементы добавляются в соответствующие сегменты

Question

Это просто Java HashMap, как элементы добавляются в соответствующие сегменты. Я знаю о факте изменения размера HashMap и разрешения коллизий, а хорошее распределение помогает повысить производительность.

1. Из начальной емкости от 0 до 15, 6 сегментов заняты для этих 10 элементов, где каждый ключевой хэш-код этих 10 элементов уникален. Как он выбирает контейнер и сталкивается.

2. Что происходит при изменении размера и поиске?

   Map<String, String> hmap = new HashMap();
   
   hmap.put("One", "One");
   hmap.put("Two", "Two");
   hmap.put("Three", "Three");
   hmap.put("Four", "Four");
   hmap.put("Five", "Five");
   
   hmap.put("Six", "Six");
   hmap.put("Seven", "Seven");
   hmap.put("Eight", "Eight");
   hmap.put("Nine", "Nine");
   hmap.put("Ten", "Ten");
   

Answer 1

HashMap использует Object#hashCode() как связанный Javado c notes Возвращает значение кода ha sh для объекта. Этот метод поддерживается для использования таблиц ha sh, таких как таблицы, предоставленные HashMap. Чтобы увидеть значения, просто вызовите hashCode() на своих ключах. Что-то вроде

String[] keyArray = { "One", "Two", "Three", "Four", "Five",
        "Six", "Seven", "Eight", "Nine", "Ten" };
for (String key : keyArray) {
    System.out.printf("%s - %d%n", key, key.hashCode());
}

Какие выходы (здесь)

One - 79430
Two - 84524
Three - 80786814
Four - 2195782
Five - 2190034
Six - 83138
Seven - 79777773
Eight - 66953327
Nine - 2428114
Ten - 83965

Answer 2

Hashmap использует хэш-код и взять и (&) с ним. Это означает, что если ваш хэш-код равен 12345, он принимает & с 15 (т. е. количество сегментов -1). Просто вы можете взять все свои ключи, чтобы сделать что-то подобное, чтобы увидеть, что он делает в backend "System.out.println (" Four ".hashCode () & 15);"

Answer 3

У вас есть HashMap с 16 ведрами. Поскольку это карта Ха sh, вы начинаете с получения hashCode() ключа, который возвращает значение int.

Как назначить полный диапазон int значений до 16 ведер? Одним из способов является использование оператора остатка %.

Однако деление происходит (относительно) медленно, поэтому реализация HashMap гарантирует, что число сегментов всегда равно показателю 2 (16, 32, 64). , 128, ...), поэтому вместо него можно использовать битовую маскировку. Чтобы замаскировать, вы используете побитовый оператор & (AND) с buckets - 1.

Итак, используя ваш hmap (фактически, LinkedHashMap для сохранения порядка), вы можете увидеть расчет корзины здесь:

System.out.println("Key      Hash Code        Bucket");
System.out.println("======= ==========        ======");
for (String key : hmap.keySet())
    System.out.printf("%-7s %10d & 15 = %d%n", '"' + key + '"', key.hashCode(), key.hashCode() & 15);

Вывод

Key      Hash Code        Bucket
======= ==========        ======
"One"        79430 & 15 = 6
"Two"        84524 & 15 = 12
"Three"   80786814 & 15 = 14
"Four"     2195782 & 15 = 6
"Five"     2190034 & 15 = 2
"Six"        83138 & 15 = 2
"Seven"   79777773 & 15 = 13
"Eight"   66953327 & 15 = 15
"Nine"     2428114 & 15 = 2
"Ten"        83965 & 15 = 13

Здесь, в сегментах 2, 6 и 13, имеется достаточное количество коллизий.

Показанные здесь сегменты не соответствуют тому, что вы видите в отладчике, потому что HashMap применяет некоторые дополнительные приемы, чтобы попытаться создать лучший дистрибутив, но это необходимая логика c.

Если размер HashMap изменен до 32 сегментов (следующий показатель равен 2), в результате вы получите:

Key      Hash Code        Bucket
======= ==========        ======
"One"        79430 & 31 = 6
"Two"        84524 & 31 = 12
"Three"   80786814 & 31 = 30
"Four"     2195782 & 31 = 6
"Five"     2190034 & 31 = 18
"Six"        83138 & 31 = 2
"Seven"   79777773 & 31 = 13
"Eight"   66953327 & 31 = 15
"Nine"     2428114 & 31 = 18
"Ten"        83965 & 31 = 29

Как видите, ключи перемещены в другие сегменты, и здесь меньше столкновений, в ведрах 6 и 18.