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()
Node
TreeNode
LinkedList
TreeMap
HashMap
包含以下欄位:
final int hash
— 目前元素的雜湊值,這是我們透過雜湊鍵所獲得的結果;final K key
— 當前元素的鍵。這是您指定為方法中第一個物件的寫入位置put()
;V value
— 當前元素的值。你在方法中指定的第二個物件寫在這裡put()
;Node < K, V> next
— 連結到同一籃子內的下一個節點。該列表是連接的,因此它需要一個不指向下一個節點的連結(如果有)。
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 個或更多元素,那麼就會發生向樹結構的轉變。
public HashMap()
— 預設建立哈希顯示:按體積(capacity) = 16
和負載因子(load factor) = 0.75
;public HashMap(Map< ? extends K, ? extends V> m)
— 建立一個由另一個給定映射的元素初始化的哈希映射,其初始容量足以容納另一個映射的元素;public HashMap(int initialCapacity)
— 建立具有給定初始容量的哈希圖。為了HashMap能夠正確正確地運作,內部陣列的大小必須是2的冪次方(即16、64、128等);public HashMap(int initialCapacity, float loadFactor)
— 使用指定參數建立哈希映射:初始容量和負載因子。
Map
並擴展類,AbstractMap
而不添加自己的方法。哈希映射不保證其元素的順序。因此,元素進入哈希映射的順序不一定是迭代器檢索它們的順序。 新增物件 新增鍵值對是使用put()
. 讓我們看一下新增物件時涉及的步驟:
-
計算輸入物件的鍵的雜湊值。密鑰哈希是透過
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. -
Вычисляем индекс бакета (ячейки массива), в который будет добавлен наш элемент:
i = (n - 1) & hash
где n – длина массива.
-
Создается an object Node.
-
Теперь, зная индекс в массиве, мы получаем список (цепочку) элементов, привязанных к этой ячейке. Если в бакете пусто, тогда просто размещаем в нем элемент. Иначе хэш и ключ нового element поочередно сравниваются с хешами и ключами элементов из списка и, при совпадении этих параметров, meaning element перезаписывается. Если совпадений не найдено, элемент добавляется в конец списка.
Теперь к очень подробному примеру.
-
Создадим an object класса HashMap:
HashMap < String, Integer> map = new HashMap<>();
-
С помощью метода
put()
добавим в хеш-отображение первую пару «ключ-meaning»:map.put("KING", 100);
В этот момент внутри вызывается метод
putVal()
. -
С помощью хеш-функции, роль которой играет метод hash, вычисляется хеш-code ключа, внутри которого предварительно вычисляется хеш-code с помощью метода hashCode() (в данном случае класса String), в результате чего мы получаем его «предварительное meaning» – 2306967. Может проверить в IDEA с помощью
System.out.println("KING".hashCode());
Полученный хеш-code модифицируется по формуле:
(хеш-code) ^ (хеш-code>>> 16)
, и в результате получаем окончательный хеш-code – 2306996. -
Проверяем таблицу на «пустоту»:
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
, которая в дальнейшем используется для вычисления бакета. -
同時,我們計算將放置物件的桶的索引,並檢查其中是否已經有元素。我們計算:
i = (n - 1) & hash i = (16 - 1) & 2306996 i = 4
查看:
if ((p = tab[i = (n - 1) & hash]) == null)
-
由於檢查結果為 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 類別物件的方法。 -
新增後,將檢查目前元素數量是否超過參數
threshold
:if (++size > threshold) resize();
如果超過,則會呼叫一個方法
resize()
來增加哈希表的大小。此時,該方法
putVal()
(分別為 和put()
)將完成其工作。結果可以用圖形表示如下:
一般來說,如果所需的儲存桶為空,這就是在雜湊表中新增節點(鍵值對)的情況。現在讓我們嘗試添加一個會導致碰撞的元素(當一個桶中有多個元素時)。
-
- 外部連結或連結方法(在 HashMap 中實作) - 即 單元格實際上包含一個列表(鏈)。並且列表可能已經包含多個值(不一定具有相同的雜湊碼)。
- 線性探測或開放尋址方法(在 IdentityHashMap 中實現)- 包括搜尋哈希函數指向的空單元之後的第一個空單元;
-
使用該方法,
put()
我們將另一個鍵值對新增至雜湊映射:map.put("BLAKE", 10);
-
我們計算“初步哈希” - 63281361。我們修改它,結果我們得到最終的哈希碼 - 63281940。
-
由於第一次檢查「空」現在將傳回 false(無需建立表),因此我們立即計算將放置物件的儲存桶的索引:
i = (n - 1) & hash i = (16 - 1) & 63281940 i = 4
-
檢查指定索引處的儲存桶中是否存在元素,並且由於在
if ((p = tab[i = (n - 1) & hash]) == null)
這種情況下不符合條件(儲存桶中已經有一個元素),因此我們轉到區塊else
。 -
首先,我們將新增的元素與桶內鍊錶的第一個元素進行比較:
(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 уже на первом этапе (разные хеши).
-
Игнорируем condition (
p instanceof TreeNode
), так How структура в бакете не является древовидной на данном этапе. -
Далее переходим в цикл
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 в текущем и сохранить оба под нужным индексом; либо осуществить переход к древовидной структуре
- проверяем с помощью методов
-
После каждой итерации (добавления нового 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()
迭代目前儲存的所有元素,重新計算它們的索引(考慮到新的大小)並將元素重新分配到新數組中。簡而言之,在不深入紅黑樹結構細節的情況下,會發生以下情況:
-
列表的第一個元素被寫為整個樹的根(黑色):
if (root == null) { x.parent = null; x.red = false; root = x; }
-
對於其他元素:
根據哈希值將它們分佈到左側或右側:
if ((ph = p.hash) > h) dir = -1; else if (ph < h) dir = 1;
所有左子節點必須小於(或等於)其根節點,而所有右子節點必須大於其根節點。
-
如果兩個元素具有相同的雜湊值並且無法以任何其他方式進行比較(它們沒有實作介面
Comparable
),我們會中斷樹的構造並呼叫該方法tieBreakOrder()
,該方法又使用本機方法System.identityHashCode()
來計算全域唯一的雜湊碼。更多詳細資訊請參閱:文章鏈接
-
我們檢查樹元素(物件
TreeNode
),直到找到子(左或右)零元素。if ((p = (dir <= 0) ? p.left : p.right) == null)
-
新增一個子節點(左或右取決於目錄):
x.parent = xp; if (dir <= 0) xp.left = x; else xp.right = x;
-
由於添加新元素可能會破壞樹的平衡,因此我們將方法稱為重新平衡:
root = balanceInsertion(root, x);
您可以在這裡閱讀有關平衡 CCH 的資訊:habr
-
平衡後,根元素可能會改變。我們透過呼叫一個方法來修復這個問題,該方法保證傳遞給它的根將是第一個節點:
moveRootToFront(tab, root)
在這裡可以清楚地看到紅黑樹是如何建構和自平衡的:視覺化
-
- 計算密鑰的哈希碼。
- 計算桶索引。
- 遍歷索引並將第一個元素的鍵與現有值進行比較。如果它們相等,則傳回該值,否則檢查下一個元素(如果存在)。
- 如果下一個 Node 物件為 null,則傳回 null。
- 如果下一個Node物件不為null,請前往它並重複前三個步驟,直到找到該元素或下一個Node物件為null。
get()
我們取得“KING”鍵的值:
map.get("KING");
在內部,呼叫該方法getNode(int hash, Object key)
,將金鑰本身(“KING”)及其雜湊值(2306996)傳遞給該方法,該值以與操作期間相同的方式預先計算put()
。
-
我們檢查:
-
哈希表是否存在:
(tab = table) != null
讓我提醒您,在創建 HashMap 時,不會在建構函數中創建表的數組;這會在稍後的方法中創建
resize()
,該方法在將第一個元素添加到哈希表時總是被調用。因此,如果HashMap中還沒有添加任何元素,那麼根本就沒有內部陣列來儲存這些元素。 -
如果前面的表達式傳回 true,則需要確保內部數組的長度大於 0:
(n = tab.length) > 0;
-
如果前面的表達式也傳回 true,則轉到先前計算的索引(在我們的範例中為 4)處的儲存桶,並檢查它是否存在元素:
(first = tab[(n - 1) & hash]) != null)
-
我們將要尋找的鍵與儲存桶內列表中第一個元素的鍵進行比較,因為在大多數儲存桶中(並非在所有發生衝突的地方)只有一個元素(我們的情況)。與方法 的情況一樣
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;
-
-
如果桶內有多個元素,則:
-
如果桶子是一個鍊錶,我們會循環遍歷列表中的每個元素,
do – while
直到找到匹配項:do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null);
-
如果桶子是樹狀結構,則另外呼叫該方法
getTreeNode()
,進而使用該方法來尋找所需的鍵find()
。我們進行樹搜尋 - 比較雜湊值並確定要搜尋的左根節點或右根節點。如果鍵相等(透過引用或通過equals
),則傳回此節點。如果左或右子節點為空,我們也使用compareTo比較鍵(如果鍵實作介面Comparable
),否則我們在樹(右子樹或左子樹)中執行遞歸搜索,直到找到匹配項。
-
-
轉到所需的儲存桶(同樣,它是預先計算的);
-
如果桶中只有一個物件(我們檢查其空指標),我們會比較雜湊值、連結和
equals
(如果突然雜湊值不相等)。找到匹配的了嗎?太棒了,這是我們的鍵 - 刪除它(=null)並返回該鍵的值。 -
如果桶中有多個元素,我們會循環檢查每個元素,直到找到該元素或到達清單末端。
-
如果沒有找到該元素,我們傳回 null。
GO TO FULL VERSION