У меня есть некоторые проблемы с HashMap из JDK1.8 - PullRequest
Новая
       11

У меня есть некоторые проблемы с HashMap из JDK1.8

0 голосов
/ 19 декабря 2018

Вот часть кода.когда длина узла превышает 7, он превращает узел в TreeNode, но в функции treeifyBin (), если длина вкладки меньше 64, он просто выполняет resize (). 

// binCount is length of Node,  TREEIFY_THRESHOLD is default 8
if (binCount >= TREEIFY_THRESHOLD - 1)
    treeifyBin(tab, hash);

// tab is Node[],  MIN_TREEIFY_CAPACITY is default 64
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    resize();

Я не могу понять, почему длина узлаотносится к resize ().

Ответы [ 2 ]

0 голосов
/ 19 декабря 2018

Основная цель создания HashMap заключается в том, что вы хотите получить значение за постоянное время O (1).Тем не менее, он не остается O (1), когда у вас есть столкновение.В случае коллизии вам придется искать ключ либо в связанном списке, либо в дереве.

Здесь вы находитесь внутри функции treeifyBin().Это означает, что вы уже столкнулись со столкновением.Но мы ненавидим столкновения.Мы хотим избежать столкновения во что бы то ни стало.Но создание дерева - это много работы.Итак, перед созданием дерева мы проверяем, достаточно ли мал массив (или вкладка) (< MIN_TREEIFY_CAPACITY).Если это так, вместо создания дерева мы увеличиваем размер массива, чтобы избежать столкновения.

Теперь давайте посмотрим, как увеличение размера массива позволяет избежать коллизий.Допустим, начальный размер массива равен 16. Теперь, чтобы отобразить хэш-код на индекс массива, нужно выполнить побитовое И (hashCode & (sizeOfArray - 1)).Здесь двоичный файл (16-1) равен 1111.Если хэш-код равен 17 (двоичный = 10001), то после побитового И все, что вы получите, будет 0001, т. Е. 1. Теперь, если вы измените размер, ваш размер массива будет 32. Следовательно, (sizeOfArray - 1) = 11111.Теперь, если вы сделаете побитовое И с тем же хеш-кодом 17, вы получите 10001, т. Е. 17. Таким образом, элемент будет перемещен с tab [1] на tab[17].Если другой ключ, который ранее сталкивался, имел хеш-код 1 или 33 ранее, он все равно был бы введен в tab[1].

0 голосов
/ 19 декабря 2018

Как вы знаете, из внутренних рабочих изменений в java-8, когда внутренний связанный список достигает порогового значения, он преобразуется в дерево (в частности, в RB Tree). Логика преобразования дерева зависит от длины узлов в корзине, поэтому ее ценностьпроверка перед преобразованием списка в дерево, можно ли вставить узел, просто изменив размер связанного списка вместо преобразования списка в дерево, что является дорогостоящей операцией.Здесь нужно учесть еще одну вещь, поскольку при частом удалении из карты дерево может быть снова преобразовано в список, поэтому в вашем методе treeifybin () есть проверка на изменение размера, а затем ваша текущая структура изменяется на дерево.

Для получения дополнительной информации просто проверьте следующее: http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java

Приветствия:)

...