HashMap 클래스의 상세 분석

수업에 대한 자세한 논의로 넘어가기 전에 해시 테이블과 관련된 기본 개념에 중점을 두겠습니다. 이 문서에서는 해시 매핑 작업 방법에 대해 설명하지 않습니다. 삽입, 검색, 삭제 동작에 대해서만 명확하고 자세하게 설명하겠습니다. 동일한 Schildt에서 HashMap 에서 사용할 수 있는 메소드에 대한 설명을 읽어보는 것은 어렵지 않을 것이라고 생각합니다. 아마도 미래에는 그러한 방법에 관한 또 다른 기사를 쓸 것이지만 지금은 이것이 의심스럽습니다. Java 7과 비교하여 Java 8의 HashMap 클래스는 상당한 변경(코드 1000줄 이상)을 거쳤습니다. 여기에서 Java 7의 구현에 대해 읽을 수 있습니다(더 이상 관련 없음). habr 해시 테이블은 연관 배열 인터페이스(추상 키-값 모델 또는 항목) 를 구현하는 데이터 구조로 , 매우 빠른 삽입 및 검색을 제공합니다. 요소 수 중 삽입과 검색(때때로 삭제)은 상수(O(1))에 가까운 시간에 수행됩니다. 본질적으로 이는 요소의 위치가 요소 자체의 값에 따라 달라지는 일반 배열입니다. 요소 값과 해시 테이블의 위치 사이의 관계는 해시 함수로 지정됩니다. 해시 함수는 키 라고 하는 입력 데이터 조각을 취하고 출력으로 해시 값(또는 해시 코드) 이라는 정수를 생성합니다 . 그런 다음 해시 값은 키를 특정 해시 테이블 인덱스에 바인딩합니다. 기본 작업(삽입, 조회, 삭제)의 경우 동일한 해시 함수를 사용하므로 이러한 작업이 매우 빠르게 수행됩니다. 이러한 이유로 해시 함수가 일관되게 동작하고 동일한 입력 데이터에 대해 동일한 인덱스를 출력하는 것이 중요합니다. 결과 해시 코드는 엄청난 숫자 값이 될 수 있으며 원래 배열은 조건부로 16개 요소에 대해서만 설계되었다는 점은 주목할 가치가 있습니다. 10개만 추가하기 위해 10억 개의 요소로 구성된 배열을 만드는 것은 어떨까요? 따라서 어떻게든 이 해시 코드를 0에서 15 사이의 값으로 변환해야 합니다(배열 크기가 16인 경우). 이를 위해 추가 변환이 사용됩니다. 그래서 우리는 배열의 크기를 최소화하기 위해 인덱스를 생성합니다. 예를 들어 Java 8 이전의 HashMap에서는 다음 추가 메소드를 사용하여 원하는 셀을 찾았습니다.

static int indexFor(int h, int length) {
        return h & (length-1);
}

작업 결과 얻은 해시 코드 hashCode()와 내부 배열의 길이(셀 수)를 입력으로 사용했습니다. 그리고 결과는 "해시 코드" -> 비트 단위 "AND" -> (배열 길이 - 1)로 반환되었습니다. 클래스는 HashMap클래스를 상속 AbstractMap하고 다음 인터페이스를 구현합니다: Map, Cloneable, Serializable. .method는 Java의 해시 함수를 담당합니다 hashCode(). 기본 구현은 ID 해시 코드hashCode() 라는 값을 반환합니다 . 클래스가 를 재정의하더라도 를 호출하여 언제든지 객체의 ID 해시를 얻을 수 있습니다 . OpenJDK의 기본 구현은 때때로 믿어지는 것처럼 메모리 주소와 아무 관련이 없습니다. 자세한 내용은 여기를 참조하세요. habr HashMap에서 해시 테이블은 단일 연결 목록의 배열(또는 테이블이 확장될 수 있으므로 더 정확하게는 동적)을 기반으로 구현됩니다. 본질적으로 우리는 메소드의 결과로 키의 해시 코드를 얻은 후 수정되고(나중에 고려할 것임) 내부적으로 추가 메소드를 사용하여 결과 값이 필요한 셀에 배포됩니다. 배열 요소(셀)는 버킷 이라고도 하며 개별 노드를 저장하는 데 사용됩니다. 각 버킷은 컬렉션(목록 또는 트리)입니다. 노드는 중첩 클래스 (또는 트리 구조) 의 개체입니다 . 실제로 배열 셀 내부에는 단일 연결 리스트 또는 다른 클래스 구현의 기초가 되는 레드-블랙 트리만 있습니다 . hashCode()System.identityHashCode(Object o)hashCode()hashCode()NodeTreeNodeLinkedListTreeMap 레드-블랙 트리 옵션은 자주 발생하지 않으며(아래에서 어떻게, 무엇을, 어디서) 이 구조는 이해하기 매우 어렵기 때문에 노드 유형의 노드에 중점을 둡니다. 노드HashMap 는 다음 필드를 포함하는 중첩 클래스입니다 .

• final int hash— 키를 해싱한 결과로 얻은 현재 요소의 해시
• final K key— 현재 요소의 키입니다. 메소드의 첫 번째 객체로 지정한 내용이 여기에 기록됩니다 put().
• V value— 현재 요소의 값. 그리고 메소드에서 두 번째 객체로 지정하는 내용이 여기에 기록됩니다 put().
• Node < K, V> next— 동일한 바구니 내의 다음 노드에 연결됩니다. 목록은 연결되어 있으므로 다음 노드가 아닌 링크가 필요합니다(있는 경우).

이제 HashMap 클래스 자체의 필드를 살펴보겠습니다.

• transient Node < K, V> [] table– 노드 형태로 키-값 쌍을 저장하기 위해 배열을 기반으로 구현된 해시 테이블 자체입니다. 여기에 노드가 저장됩니다.
• transient int size— 키-값 쌍의 수
• int threshold— 해시 테이블의 크기가 두 배가 되는 최대 요소 수입니다. 공식(capacity * loadFactor)을 사용하여 계산됩니다.
• final float loadFactor— 이 매개변수는 현재 해시 테이블이 새 해시 테이블을 생성하는 데 필요한 로드 정도를 결정합니다. 해시 테이블이 75% 차면 새 해시 테이블이 생성되고 현재 요소가 그 테이블로 이동됩니다(모든 요소를 ​​다시 해시해야 하기 때문에 비용이 많이 드는 작업).
• transient Set< Map.Entry< K,V>> entrySetentrySet()- 반복할 수 있는 캐시가 포함되어 있습니다 HashMap.

그리고 상수:

• static final int DEFAULT_INITIAL_CAPACITY= 1 << 4— 기본 해시 테이블 용량(16)
• static final int MAXIMUM_CAPACITY = 1 << 30— 해시 테이블의 가능한 최대 용량(약 10억)
• static final float DEFAULT_LOAD_FACTOR = 0.75f- 기본 하중 계수;
• static final int TREEIFY_THRESHOLD = 8한 버킷에 있는 요소 수의 "임계값"이며, 이에 도달하면 내부 연결 목록이 트리 구조(레드-블랙 트리)로 변환됩니다.
• static final int UNTREEIFY_THRESHOLD = 6— 한 바구니의 요소 수가 6으로 감소하면 트리에서 연결된 목록으로의 역전이가 발생합니다.
• static final int MIN_TREEIFY_CAPACITY = 64— 트리 구조로의 전환이 가능한 해시 테이블의 최소 용량(버킷 수)입니다. 저것들. 해시 테이블에 최소 64개의 버킷이 있고 하나의 버킷에 8개 이상의 요소가 있는 경우 트리 구조로 전환됩니다.

클래스 생성자:

1. public HashMap()— 기본적으로 해시 디스플레이를 생성합니다: 볼륨 (capacity) = 16및 부하 계수 기준 (load factor) = 0.75;
2. public HashMap(Map< ? extends K, ? extends V> m)— 다른 매핑의 요소를 수용하기에 충분한 초기 용량을 사용하여 다른 매핑의 요소로 초기화된 해시 매핑을 생성합니다.
3. public HashMap(int initialCapacity)— 주어진 초기 용량으로 해시 맵을 생성합니다. HashMap이 올바르게 작동하려면 내부 배열의 크기가 2의 거듭제곱(예: 16, 64, 128 등)이어야 합니다.
4. public HashMap(int initialCapacity, float loadFactor)— 지정된 매개변수(초기 용량 및 부하 계수)를 사용하여 해시 맵을 생성합니다.

클래스는 인터페이스를 구현 하고 자체 메서드를 추가하지 않고 Map클래스를 확장합니다 . 해시 맵은 해당 요소의 순서를 보장하지 않습니다. 따라서 요소가 해시 맵에 입력되는 순서는 반복자가 요소를 검색하는 순서와 반드시 일치하지는 않습니다. 객체 추가 키-값 쌍 추가는 . 객체를 추가할 때 관련된 단계를 살펴보겠습니다. AbstractMapput()

1. 입력된 객체의 키에 대한 해시값을 계산합니다. 키 해시는 우리가 알고 있는 키 메서드 static final int hash(Object key)에 이미 액세스하는 메서드에 의해 계산됩니다 hashCode(). 이를 위해 재정의된 메서드 hashCode()나 해당 기본 구현이 사용됩니다. 메소드의 추가 변환 hash():

   static final int hash(Object key) {
           int h;
           return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
   }

   Почему бы просто не вычислить с помощью hashCode()? Это сделано из-за того, что hashCode() можно реализовать так, что только нижние биты int'a будут заполнены. Например, для Integer, Float – если мы в HashMap кладем маленькие значения, то у них и биты хеш-codeов будут заполнены только нижние. В таком случае ключи в HashMap будут иметь тенденцию скапливаться в нижних ячейках, а верхние будут оставаться пустыми, что не очень эффективно. На то, в Howой бакет попадёт новая запись, влияют только младшие биты хеша. Поэтому и придумали различными манипуляциями подмешивать старшие биты хеша в младшие, чтобы улучшить распределение по бакетам (чтобы старшие биты родного хеша an object начали вносить коррективы в то, в Howой бакет попадёт an object) и, How следствие, производительность. Потому и придумана дополнительная функция hash внутри HashMap.

2. Вычисляем индекс бакета (ячейки массива), в который будет добавлен наш элемент:

   
   i = (n - 1) & hash

   где n – длина массива.

3. Создается an object Node.

4. Теперь, зная индекс в массиве, мы получаем список (цепочку) элементов, привязанных к этой ячейке. Если в бакете пусто, тогда просто размещаем в нем элемент. Иначе хэш и ключ нового element поочередно сравниваются с хешами и ключами элементов из списка и, при совпадении этих параметров, meaning element перезаписывается. Если совпадений не найдено, элемент добавляется в конец списка.

   Теперь к очень подробному примеру.

   1. Создадим an object класса HashMap:

      HashMap < String, Integer> map = new HashMap<>();

   2. С помощью метода put() добавим в хеш-отображение первую пару «ключ-meaning»:

      map.put("KING", 100);

      В этот момент внутри вызывается метод putVal().

   3. С помощью хеш-функции, роль которой играет метод hash, вычисляется хеш-code ключа, внутри которого предварительно вычисляется хеш-code с помощью метода hashCode() (в данном случае класса String), в результате чего мы получаем его «предварительное meaning» – 2306967. Может проверить в IDEA с помощью

      System.out.println("KING".hashCode());

      Полученный хеш-code модифицируется по формуле: (хеш-code) ^ (хеш-code>>> 16), и в результате получаем окончательный хеш-code – 2306996.

   4. Проверяем таблицу на «пустоту»:

      if ((tab = table) == null || (n = tab.length) == 0)

      где [] tab — сама хеш-table: ссылаем tab и table (напомню, что это поле класса HashMap, которое хранит массив для наших элементов) на один и тот же массив, а int n – дополнительная переменная-счетчик.

      Так How проверка вернёт true (потому что массив для таблицы не был создан с помощью оператора new в конструкторе), будет вызван метод resize(), который собственно и создаст таблицу размером на 16 элементов. Да-да, конструкторы класса ниHowой таблицы не создают. Вместо этого всегда происходит вызов метода resize() при первом добавлении element. Длина созданной таблицы (считай длина массива) будет записана в переменную n – n = (tab = resize()).length, которая в дальнейшем используется для вычисления бакета.

   5. 동시에 객체가 배치될 버킷의 인덱스를 계산하고 해당 객체에 이미 요소가 있는지 확인합니다. 우리는 다음을 계산합니다:

      
      i = (n - 1) & hash
      i = (16 - 1) & 2306996
      i = 4

      확인하다:

      
      if ((p = tab[i = (n - 1) & hash]) == null)

   6. 확인 결과 true(버킷에 요소가 없음)가 나오므로 다음 필드가 있는 Node 객체가 생성됩니다.

      
      {
      int hash = 2306996 — сгенерированный хеш-code
      String key = {"KING"} — ключ
      Integer value = 100 — meaning
      Node next = null — link на следующий узел
      }

      생성된 노드 객체는 인덱스 [4] 아래 버킷에 추가됩니다.

      tab[i] = newNode(hash, key, value, null);
      tab[4] = newNode(2306996, “KING”, 100, null);

      newNode()단순히 Node 클래스의 객체를 반환하는 메서드입니다.

   7. 추가한 후에는 현재 요소 수가 매개변수를 초과하는지 확인합니다 threshold.

      if (++size > threshold)
          resize();

      resize()초과하는 경우 해시 테이블의 크기를 늘리는 메서드가 호출됩니다 .

      이 시점에서 메서드 putVal()(및 각각 put())가 작업을 완료합니다.

      결과는 다음과 같이 그래픽으로 표현될 수 있습니다.

      일반적으로 원하는 버킷이 비어 있는 경우 해시 테이블에 노드(키-값 쌍)를 추가하는 모습은 다음과 같습니다 . 이제 충돌을 일으키는 요소를 추가해 보겠습니다(한 버킷에 두 개 이상의 요소가 있는 경우).

충돌에 대해 조금 다른 키가 동일한 버킷에 들어가는 상황(해시가 다르더라도)을 충돌 또는 충돌이라고 합니다. 해시 테이블이 데이터 세트보다 크고 좋은 해시 함수를 선택한 경우에도 충돌이 발생하지 않는다는 보장은 없습니다. 그리고 해시값은 int 값의 범위(약 40억개)로 제한됩니다. 결과적으로 생성된 새 값도 어딘가에 기록되어야 하며, 이를 위해서는 정확히 어디에 기록될 것인지 결정해야 합니다. 이를 갈등 해결이라고 합니다. 두 가지 접근 방식이 있습니다.

• 외부 연결 또는 연결 방법(HashMap에서 구현됨) - 즉 셀에는 실제로 목록(체인)이 포함되어 있습니다. 그리고 목록에는 이미 여러 값이 포함될 수 있습니다(해시 코드가 반드시 동일할 필요는 없음).
• 선형 탐색 또는 개방형 주소 지정 방법(IdentityHashMap에서 구현됨) - 해시 함수가 가리키는 셀 다음의 첫 번째 빈 셀을 검색하는 것으로 구성됩니다.

여기에서 충돌에 대해 읽을 수 있습니다.

1. 이 방법을 사용하여 put()해시 매핑에 또 다른 키-값 쌍을 추가합니다.

   map.put("BLAKE", 10);

2. 우리는 "예비 해시" – 63281361을 계산합니다. 이를 수정하고 결과적으로 최종 해시 코드 – 63281940을 얻습니다.

3. "비어 있음"에 대한 첫 번째 검사는 이제 false를 반환하므로(테이블을 만들 필요가 없음) 객체가 배치될 버킷의 인덱스를 즉시 계산합니다.

   
   i = (n - 1) & hash
   i = (16 - 1) & 63281940
   i = 4

4. 지정된 인덱스의 버킷에 요소가 있는지 확인하고 if ((p = tab[i = (n - 1) & hash]) == null)이 경우 조건이 충족되지 않으므로(버킷에 이미 요소가 있음) 블록으로 이동합니다 else.

5. 먼저 추가되는 요소를 버킷 내부 연결 목록의 첫 번째 요소와 비교합니다.

   (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))

   При проверке сначала сравниваются хеши ключей. Если этот «участок» (p.hash == hash) возвращает false, тогда остальная часть условия игнорируется (&&), так How an objectы гарантированно разные. Иначе затем сравниваются ключи по ссылке (==) и в случае неequalsства, ключи сравниваются уже посредством метода equals(). Сравнение осуществляется в таком порядке во благо производительности. Если все три выражения возвращают true, это означает, что ключи равны и новый элемент будет записан в дополнительную переменную, чтобы в дальнейшем с её помощью перезаписать meaning у ключа:

   if (e != null) { // existing mapping for key
         V oldValue = e.value;
         if (!onlyIfAbsent || oldValue == null)
         e.value = value;
         afterNodeAccess(e);
          return oldValue;
    }

   В результате сравнения ключей мы получаем false уже на первом этапе (разные хеши).

6. Игнорируем condition (p instanceof TreeNode), так How структура в бакете не является древовидной на данном этапе.

7. Далее переходим в цикл for, где в пределах одного бакета проверяем у элементов указатель на следующий элемент next, и если он equals null (значит элемент в списке последний и единственный), добавляем новый элемент Node в конец списка:

   if ((e = p.next) == null){
   	p.next = newNode(hash, key, value, null)
   ... };

   Вы можете спросить, а где же проверка на equalsство ключей? Мы же не можем просто взять и добавить новый элемент. Так вот она уже была заранее осуществлена в пункте (5). Благодаря этому, теперь мы можем просто проверить указатель этого element, и так How он сейчас equals null, можно сделать вывод о том, что в списке только один элемент. И так How мы уже проверяли их ключи, мы можем безболезненно добавлять новый элемент.

   Если же при первой итерации указатель не equals null, это говорит о том, что в списке How минимум два element, поэтому в таком случае мы переходим к следующему условия и сравниваем ключ добавляемого element со всеми ключами элементов в списке (способом, описанным в пятом пункте).

   if (e.hash == hash &&
                           ((k = e.key) == key || (key != null && key.equals(k))))

   Если при сравнении ключей будет найдено совпадение, новый элемент будет записан в дополнительную переменную, чтобы в дальнейшем с её помощью перезаписать meaning у ключа.

   После добавления второго element наш an object HashMap графически выглядит так:

   В итоге, добавление элементов при коллизии (в пределах одного бакета) выглядит следующим образом:

   • проверяем с помощью методов hashCode() и equals(), что оба ключа одинаковы.
   • если ключи одинаковы, заменить текущее meaning новым.
   • иначе связать новый и старый an objectы с помощью структуры данных "связный список", указав ссылку на следующий an object в текущем и сохранить оба под нужным индексом; либо осуществить переход к древовидной структуре

8. После каждой итерации (добавления нового element) в цикле for увеличивается счетчик, который отвечает за количество элементов в бакете:

   for (int binCount = 0; ; ++binCount)

   До тех пор, пока их количество не станет равно or больше 7:

   binCount >= TREEIFY_THRESHOLD – 1

   В таком случае произойдет вызов метода treeifyBin()treeify()для непосредственного построения древовидной структуры. Однако, если количество бакетов в текущей хеш-таблице меньше 64:

   if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)

   resize()트리 구조로 이동하는 대신 해시 테이블의 크기를 늘리고 요소를 재배포하는 메서드가 호출됩니다 . treeify()그러면 연결된 목록이 TreeNode레드-블랙 트리로 변환됩니다. 이 메서드는 resize()현재 저장소의 모든 요소를 ​​반복하고 해당 인덱스를 다시 계산하고(새 크기를 고려하여) 요소를 새 배열로 재배포합니다.

   간단히 말해서, 레드-블랙 트리의 구조를 자세히 설명하지 않고 다음과 같은 일이 발생합니다.

   1. 목록의 첫 번째 요소는 전체 트리의 루트(검은색)로 기록됩니다.

      if (root == null) {
          x.parent = null;
          x.red = false;
          root = x;
      }

   2. 기타 요소의 경우:

      해시 값에 따라 왼쪽이나 오른쪽으로 배포합니다.

      if ((ph = p.hash) > h)
          dir = -1;
      else if (ph < h)
          dir = 1;

      모든 왼쪽 자식은 루트 노드보다 작거나 같아야 하며, 오른쪽 자식은 모두 커야 합니다.

   3. 두 요소의 해시가 동일하고 다른 방법으로 비교할 수 없는 경우(인터페이스를 구현하지 않음 Comparable) 트리 구성을 중단하고 메서드를 호출합니다 tieBreakOrder(). 그러면 기본 메서드를 사용하여 System.identityHashCode()전역적으로 고유한 해시 코드를 계산합니다. .

      자세한 내용은 여기: 기사 링크

   4. TreeNode하위(왼쪽 또는 오른쪽) 0 요소가 발견될 때까지 트리 요소(객체)를 확인합니다 .

      if ((p = (dir <= 0) ? p.left : p.right) == null)

   5. 하위 노드를 추가합니다(dir에 따라 왼쪽 또는 오른쪽).

      x.parent = xp;
      if (dir <= 0)
          xp.left = x;
      else
          xp.right = x;

   6. 새로운 요소를 추가하면 트리의 균형이 깨질 수 있으므로 재조정 방법을 호출합니다.

      root = balanceInsertion(root, x);

      여기에서 CCH 균형 조정에 대해 읽을 수 있습니다: habr

   7. 균형을 맞춘 후에 루트 요소가 변경될 수 있습니다. 전달된 루트가 첫 번째 노드가 되도록 보장하는 메서드를 호출하여 이 문제를 해결합니다.

      moveRootToFront(tab, root)

      여기에서 레드-블랙 트리가 어떻게 구축되고 자체 균형을 맞추는지 명확하게 볼 수 있습니다. 시각화

원칙적으로 그게 전부입니다. 예를 사용하여 KING, MARY, JOSE, ANNA, FRED, TONY, ALEX, PEPE와 같은 이름을 키로 추가한다고 가정해 보겠습니다. 그리고 해시 테이블에 최소 64개의 버킷이 있고 이 모든 요소가 하나의 버킷에 축적되어 있다고 가정해 보겠습니다. 구조적으로 이 버킷은 다음과 같습니다(요소는 해시 코드별로 정렬됨). CCHD 유형: 버킷 내부 보기: 요소 검색(키로 값 검색) 추가 작업은 매우 간단합니다. 알고리즘(버킷에 연결된 목록이 있는 경우)은 다음과 같이 작성할 수 있습니다.

1. 키의 해시 코드를 계산합니다.
2. 버킷 인덱스를 계산합니다.
3. 인덱스를 살펴보고 첫 번째 요소의 키를 기존 값과 비교합니다. 동일하면 값을 반환하고, 그렇지 않으면 다음 요소가 있는지 확인합니다.
4. 다음 Node 객체가 null이면 null을 반환합니다.
5. 다음 Node 개체가 null이 아니면 해당 개체로 이동하여 요소를 찾거나 다음 Node 개체가 null이 될 때까지 처음 세 단계를 반복합니다.

이 메서드를 사용하여 get()"KING" 키의 값을 얻습니다.

map.get("KING");

내부에서는 키 자체("KING")와 해당 해시(2306996)가 전달되는 메소드가 호출되며 getNode(int hash, Object key), 이는 작업 중과 동일한 방식으로 사전 계산됩니다 put().

1. 우리는 다음을 확인합니다:

   1. 해시 테이블이 존재합니까?(tab = table) != null

      HashMap을 생성할 때 테이블의 배열은 생성자에서 생성되지 않으며, 이는 resize()해시 테이블에 첫 번째 요소를 추가할 때 항상 호출되는 메서드에서 나중에 발생합니다. 따라서 HashMap에 요소가 추가되지 않은 경우 요소를 저장할 내부 배열이 없습니다.

   2. 이전 표현식이 true를 반환하는 경우 내부 배열의 길이가 0보다 큰지 확인해야 합니다.(n = tab.length) > 0;

   3. 이전 표현식도 true를 반환하는 경우 이전에 계산된 인덱스(이 경우 4)의 버킷으로 이동하여 요소가 있는지 확인합니다.

      (first = tab[(n - 1) & hash]) != null)

   4. 우리가 찾고 있는 키를 버킷 내부 목록의 첫 번째 요소의 키와 비교합니다. 왜냐하면 대부분의 버킷에는 (충돌이 있는 모든 곳은 아니지만) 단 하나의 요소(우리의 경우)만 있기 때문입니다. 메소드의 경우와 마찬가지로 put()해시를 비교하고 일치하면 키를 참조로 비교한 다음 으로만 비교합니다 equals().

      if (first.hash == hash && // always check first node
          ((k = first.key) == key || (key != null && key.equals(k))))

      우리의 경우 "KING" 키가 "BLAKE" 키보다 앞에 있으므로(연결된 목록 내에서는 새 요소가 끝에 추가되고 KING이 먼저 추가됨) 이 지점에서 멈추고 첫 번째 개체를 반환합니다. get() 메서드에 Node를 입력하면 값이 (100)인 필드를 "낚아챌" 수 있습니다.

      return (e = getNode(hash(key), key)) == null ? null : e.value;

2. 버킷 내부에 두 개 이상의 요소가 있는 경우 다음을 수행합니다.

   1. do – while버킷이 연결된 목록인 경우 일치하는 항목을 찾을 때까지 루프의 각 요소를 통해 목록을 살펴봅니다 .

      do {
          if (e.hash == hash &&
              ((k = e.key) == key || (key != null && key.equals(k))))
              return e;
      } while ((e = e.next) != null);

   2. 버킷이 트리 구조인 경우 메소드가 추가로 호출되고 getTreeNode(), 이 메소드는 필요한 키를 찾기 위해 해당 메소드를 사용합니다 find(). 우리는 트리 검색을 수행합니다. 해시를 비교하고 검색할 왼쪽 또는 오른쪽 루트 노드를 결정합니다. 키가 동일하면(참조 또는 equals) 이 노드를 반환합니다. 왼쪽 또는 오른쪽 하위 노드가 null인 경우 CompareTo를 사용하여 추가로 키를 비교합니다(키가 인터페이스를 구현하는 경우 Comparable). 그렇지 않으면 일치 항목을 찾을 때까지 트리(오른쪽 또는 왼쪽 하위 트리)를 통해 재귀 검색을 수행합니다.

HashMap에서 객체 제거하기 글의 공간이 부족하므로 키별로 삭제가 어떻게 이루어지는지 간략하게 설명하겠습니다. 알고리즘은 매우 유사합니다.

• 원하는 버킷으로 이동합니다(다시 말하지만 사전 계산됨).

• 버킷에 개체가 하나만 있는 경우(널 포인터 확인) 해시, 링크를 비교하고 equals(갑자기 해시가 동일하지 않은 경우) 일치하는 항목을 찾았나요? 좋습니다. 이것이 우리의 키입니다. 이를 삭제하고(=null) 이 키의 값을 반환합니다.

• 버킷에 요소가 두 개 이상 있으면 해당 요소를 찾거나 목록 끝에 도달할 때까지 루프의 각 요소를 확인합니다.

• 요소를 찾을 수 없으면 null을 반환합니다.

트리가 있는 상황에서는 다소 까다로운 구현이 있는데, 이를 모르고 잠에 드는 것이 좋습니다(방법 설명에 따르면 레드-블랙의 일반 삭제 작업보다 구현이 더 복잡하다고 나와 있습니다). 나무). 또한, 삭제되면 한 버킷의 노드 수가 6으로 돌아갈 수 있으며, 그런 다음 트리는 다시 연결 목록으로 재구성됩니다. 다년간의 경험을 가진 개발자가 아니라면 이것을 알고 이해할 필요가 전혀 없습니다 (단순히 필요하지도 않습니다).