Как изменяется внутренняя структура данных Java HashMap во время перефразирования? - PullRequest
Новая
       84

Как изменяется внутренняя структура данных Java HashMap во время перефразирования?

4 голосов
/ 22 апреля 2019

Я пытаюсь написать демонстрационный код, чтобы показать, что перефразирование происходит в Hashmap, когда размер карты превышает пороговое значение коэффициента загрузки.Как я могу доказать, что перефразировка происходит внутри.Также я хочу доказать, что даже если старые записи перемещаются в новые сегменты во время перефразирования, я могу получить старые элементы, используя старый ключ (дайте мне знать, что мое предположение верно).Ниже приведен пример кода.

import java.util.*;

    class RehashDemo{

        public static void main(String[] args){
            Map<Integer,String> numbers = new HashMap<>(10);
            for(int i = 0; i<10;i++){
                numbers.put(i,i+"");
            }
            System.out.println(numbers);

            for(int j = 15; j<=20;j++){
                numbers.put(j,j+"");
            }
            System.out.println(numbers);

        }


    }

1 Ответ

5 голосов
/ 23 апреля 2019

Нетрудно написать программу для демонстрации повторного хэширования, но вы должны много понять о внутренней организации HashMap, о том, как генерируются хеш-коды объектов, как хэш-коды связаны с внутренними структурами HashMap и как это влияет на порядок итераций.

Вкратце, HashMap состоит из массива сегментов («таблица»).Каждый сегмент представляет собой связанный список пар ключ-значение.Добавление пары, чьи ключи хешируются в группу, которая уже занята, добавляется в конец связанного списка для этой корзины.Контейнер определяется путем вызова метода ключа hashCode(), XOR его с 16 старшими битами старшего разряда, смещенными вправо на 16 (см. source ), и затем с учетом модуля размера таблицы.Поскольку размер таблицы всегда является степенью двойки, это по существу AND с маской (tablesize-1).Хеш-код объекта Integer является просто его целочисленным значением.( источник ).Наконец, порядок итераций HashMap последовательно проходит через каждый сегмент, а также последовательно через связанный список пар в каждом сегменте.

После всего этого вы можете видеть, что небольшие целочисленные значения будут заканчиваться в соответствующих сегментах,Например, Integer.valueOf(0).hashCode() равно 0. Он останется 0 после shift-and-XOR, а модуль любого размера таблицы останется 0. Таким образом, Integer 0 заканчивается в сегменте 0, Integer 1 заканчивается в сегменте 1 и т. Д.,Но не забывайте, что ведро по модулю размера стола.Таким образом, если размер таблицы равен 8, целое число 8 окажется в сегменте 0.

С помощью этой информации мы можем заполнить HashMap ключами Integer, которые окажутся в предсказуемых сегментах.Давайте создадим HashMap с размером таблицы 8 и коэффициентом загрузки по умолчанию 0,75, что означает, что мы можем добавить шесть сопоставлений до перефразирования. 

Map<Integer, Integer> map = new HashMap<>(8);
map.put(0, 0);
map.put(8, 8);
map.put(1, 1);
map.put(9, 9);
map.put(2, 2);
map.put(10, 10);

{0=0, 8=8, 1=1, 9=9, 2=2, 10=10}

Распечатка карты (по сути, используя ее toString()метод) повторяет карту последовательно, как описано выше.Мы видим, что 0 и 8 заканчиваются в первом сегменте, 1 и 9 - во втором, а 2 и 10 - в третьем.Теперь давайте добавим еще одну запись: 

map.put(3, 3);

{0=0, 1=1, 2=2, 3=3, 8=8, 9=9, 10=10}

Порядок итераций изменился!Добавление нового отображения превысило пороговое значение для перефразирования, поэтому размер таблицы был удвоен до 16. Перефразирование было выполнено, на этот раз с модулем 16 вместо 8. В то время как 0 и 8 были оба в корзине 0 раньше, теперь они находятся вотдельные ведра, так как доступно в два раза больше ведер.То же самое с 1/9 и 2/10.Вторая запись в каждом сегменте со старым размером таблицы 8 теперь хэшируется в свой собственный сегмент, когда размер таблицы равен 16. Вы можете видеть это, поскольку итерация последовательно проходит через сегменты, и теперь в каждом сегменте имеется одна запись.

Конечно, я тщательно выбрал целочисленные значения, чтобы коллизии возникали с размером таблицы 8, а не с размером таблицы 16. Это позволяет нам очень четко увидеть перефразирование.Для более типичных объектов хеш-коды (и, следовательно, сегменты) сложнее предсказать, поэтому сложнее увидеть коллизии и то, что происходит, когда происходит перефразировка.

...