Запрос о внутренней реализации HashMap

Question

Я рассматриваю реализацию HashMap и обращаюсь к этой ссылке: Как Java реализует хеш-таблицы? Я обнаружил, что «HashMap содержит массив сегментов, чтобы содержать его записи».Итак, у меня есть несколько вопросов -

1. Каков тип массива сегментов.
2. Поскольку у массива есть недостатки (например, фиксированный размер и допускаются только однородные данные). Затем мынесмотря на эти недостатки, используют массивы.

3.В случае одинакового хеш-кода для ключа или коллизии он использует связанный список. Как он получает (ищет) ссылку на второй, третий узел и т. д.

Спасибо в adv.

Answer 1

1. Это внутренний объект, который содержит ключ, значение и ссылку на следующий узел в корзине (для реализации единого связанного списка)
2. Требуется фиксированный размер степени 2для массива.Индекс массива для данного ключа основан на логическом И (&) хеш-кода ключа и размере массива, который является фактической «магией» хеш-таблицы.
3. Связанный список в сегменте необходим для устранения коллизий хеш-кода.Это является причиной наихудшего случая сложности O (n) в HashMap.get () - происходит, если все ключи имеют одинаковый хеш-код и искомый ключ является последним в корзине.

Если хэш-карты растут, существует очень дорогая функция перефразировки, потому что массив должен расти до следующей степени 2, а также.В этом случае каждое ведро должно пересчитать свой индекс.В этом случае создается новый массив.Это означает, что динамическая структура данных не требуется.

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

Answer 2

Из источника кода OpenJDK8 :

1. Ячейки являются либо списками, либо деревьями, в зависимости от количества элементов, которые они содержат
2. Однородность массивовне является проблемой в этом контексте, и скорость доступа вычитается из стоимости изменения размера массива
3. HashMap всегда перебирает все значения с одинаковым хешем, проверяя, имеют ли они правильный ключ:

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;

}

Answer 3

1. Каков тип массива блоков.

Это зависит от карты, которую вы делаете, если вы сделаете HashMap<Integer, String>, то корзины будут тех типов, которые могутсодержать эти типы объектов

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

Поскольку недостатки того стоят по сравнению с повышением производительности.Поскольку массивы имеют фиксированный размер, многие проверки могут быть пропущены (т.е. существует ли этот индекс?).Вы можете прочитать больше об этом здесь;https://en.wikiversity.org/wiki/Java_Collections_Overview и Почему бы не всегда использовать ArrayLists в Java вместо простых старых массивов?

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

Это объясняется здесь лучше, чем яМожно; Что происходит, когда дублирующий ключ помещается в HashMap?