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()。預設實作會傳回一個稱為身分雜湊碼的hashCode()值。即使類別重寫了，您也始終可以透過呼叫 來取得物件的 ID 雜湊值。有時人們認為，OpenJDK 中的預設實作與記憶體位址無關。更多詳細資訊請參閱：habr 在 HashMap 中，哈希表是基於單鍊錶數組（或更準確地說，動態的，因為表可以擴展）實現的。本質上，我們透過方法獲得鍵的雜湊碼，然後對其進行修改（我們稍後將考慮），並在內部使用附加方法將結果值分發到所需的單元格。數組元素（單元）也稱為儲存桶，用於儲存各個節點。每個桶子都是一個集合（列表或樹）。節點是巢狀類別（或樹結構中）的物件。事實上，數組單元內部只有一個單鍊錶或紅黑樹，它是另一個類 - 的實現的基礎。 hashCode()System.identityHashCode(Object o)hashCode()hashCode()NodeTreeNodeLinkedListTreeMap 紅黑樹的選項並不經常出現（如何、什麼和在哪裡 - 下面），而且這種結構很難理解，因此重點將放在 Node 類型的節點上。 Node是一個巢狀類，其中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— 元素的最大數量，達到該數量後的雜湊表大小將加倍。使用公式計算（容量*負載係數）；
• final float loadFactor— 此參數決定目前雜湊表需要多大程度的負載才能建立新的雜湊表，即 一旦雜湊表已滿 75%，就會建立一個新的雜湊表，並將當前元素移入其中（這是一個成本高昂的操作，因為所有元素都必須重新雜湊）；
• transient Set< Map.Entry< K,V>> entrySet- 包含一個緩存entrySet()，我們可以用它來迭代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並擴展類，AbstractMap而不添加自己的方法。哈希映射不保證其元素的順序。因此，元素進入哈希映射的順序不一定是迭代器檢索它們的順序。 新增物件 新增鍵值對是使用put(). 讓我們看一下新增物件時涉及的步驟：

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 на следующий узел
      }

      我們產生的 Node 物件將會被加入到索引 [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），直到找到子（左或右）零元素。

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

   5. 新增一個子節點（左或右取決於目錄）：

      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");

在內部，呼叫該方法getNode(int hash, Object key)，將金鑰本身（“KING”）及其雜湊值（2306996）傳遞給該方法，該值以與操作期間相同的方式預先計算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），則傳回此節點。如果左或右子節點為空，我們也使用compareTo比較鍵（如果鍵實作介面Comparable），否則我們在樹（右子樹或左子樹）中執行遞歸搜索，直到找到匹配項。

從 HashMap 中刪除物件 由於本文篇幅有限，我將簡要描述如何透過鍵進行刪除。該演算法非常相似：

• 轉到所需的儲存桶（同樣，它是預先計算的）；

• 如果桶中只有一個物件（我們檢查其空指標），我們會比較雜湊值、連結和equals（如果突然雜湊值不相等）。找到匹配的了嗎？太棒了，這是我們的鍵 - 刪除它（=null）並返回該鍵的值。

• 如果桶中有多個元素，我們會循環檢查每個元素，直到找到該元素或到達清單末端。

• 如果沒有找到該元素，我們傳回 null。

在樹的情況下，有一個相當棘手的實現，最好不要知道它並睡個好覺（該方法的描述甚至說該實現比紅黑中的常規刪除操作更複雜）樹）。而且，當刪除時，一個桶中的節點數可以恢復到6個，然後樹將被重建回鍊錶。如果您不是具有多年經驗的開發人員，則完全沒有必要了解和理解這一點（而且根本沒有必要）。