Что мы сравниваем в методе put () в Java HashMap? - PullRequest
4 голосов
/ 20 января 2020

Я открыл Исходный код HashMap (Java 8 +) и проверил метод put () . В Java 7 (и менее) исходный код был довольно простым, но я не могу понять версию Java 8+.

Если элемент в корзине не существует, мы просто помещаем его в HashMap:

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

Но если элемент уже существует, мы сталкиваемся со столкновением.

В начале в блоке "else" мы сравниваем элемент (?) С (каким? Первым элементом в этом сегменте?) По их ха sh (?):

else {
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;

Но, подождите, мы повторили это позже:

    ...
    else {
        for (int binCount = 0; ; ++binCount) {
            if ((e = p.next) == null) {
                p.next = newNode(hash, key, value, null);
                if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                    treeifyBin(tab, hash);
                break;
            }
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                break;
            p = e;
        }
    }
    ...
}

Мы просмотрели список до конца и сравнили новый элемент со всеми элементами (для l oop) в корзине. Итак, я не понимаю цель первого сравнения. Означает ли это (в первом случае), что мы сравниваем последний добавленный элемент (уже в hashmap) с новым элементом «готов к добавлению», если они не находятся в одном сегменте?

Ответы [ 2 ]

1 голос
/ 20 января 2020

В местоположении tab[i = (n - 1) & hash] (т. Е. По хешированному индексу) у нас есть либо null (в этом случае карта не содержит записи), либо экземпляр Node, то есть то, что вы Заинтересованы в.

Концептуально этот экземпляр Node выполняет одну из трех ролей, каждая из которых соответствует ветви во внутренней структуре if / else:

  1. Это фактическая запись мы ищем;
  2. Это root дерева (когда корзина хранится в виде дерева)
  3. Это заголовок связанного списка (когда корзина хранится в виде связанного списка)

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

0 голосов
/ 20 января 2020

Строка 629 (if ((p = tab[i = (n - 1) & hash]) == null)) может быть записана в трех отдельных строках:

i = (n - 1) & hash;
p = tab[i];
if (p == null)
    { ... }

Тогда назначения более заметны, и более очевидно, что они выполняются до блока else .

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...