目錄
一. 實作的介面
二. 默認初始值
1. 默認初始容量
2. 默認最大容量
3. 默認負載因子
三. 鏈表與紅黑樹的相互轉換
四. 哈希桶中鏈表的結構
五. 哈希函式
六. 擴容
七. HashMap中常用的方法
1. 構造方法
2. 查找，根據key獲取value
3. 檢測key是否存在
4. 插入
5. 洗掉
八. HashMap常考問題
一. 實作的介面
底層實作了Map，克隆，序列化介面
二. 默認初始值
1. 默認初始容量
2^4 = 16，當不給初始容量時，容量默認為16
2. 默認最大容量
默認最大容量為 2^30
3. 默認負載因子
默認的負載因子為0.75，有效元素個數 / 表容量 = 負載因子
三. 鏈表與紅黑樹的相互轉換
哈希桶中存放的是鏈表節點，但是在一定條件下，鏈表會和紅黑樹相互轉化
每個桶的鏈表節點個數超過8，鏈表會轉化為紅黑樹
當紅黑樹中的節點個數小于6時，紅黑樹會退化為鏈表
如果哈希桶中某條鏈表中節點超過8，并且桶的個數超過64，鏈表才會轉化為紅黑樹，否則直接擴容
四. 哈希桶中鏈表的結構
//HashMap將其底層鏈表中的節點封裝為靜態內部類
//節點中帶有key，value鍵值對以及key所對應的哈希值
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //節點的哈希值
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
//重寫Object類中hashcode()方法
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
//重寫Object類中equals方法
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
五. 哈希函式
將key轉化為一個整型數字，再用這個數字進行除留余數法計算桶的位置
決議：
1. 如果key為null，回傳0號桶，
2. 如果key不為null，回傳key所對應的哈希碼，如果key為自定義型別，必須重寫Object類中的hashcode()方法，
3. ( h = key . hashCode() ) ^ ( h >>> 16 ),是為了讓高16bit不變，低16bit與高16bit進行異或，主要用于當hashmap陣列比較小的時候所有bit都參與運算，目的是減小碰撞，
4. 獲取到哈希地址后，計算桶號的方式為：index = (table.length - 1) & hash，
5. 通過除留余數法方式獲得桶號，因為hash表的大小始終為2的n次冪，因此可以將取模轉為位運算，提高效率，這也是為什么要按照2倍方式擴容的一個原因，
這里畫圖來說明一下原因：
總結：通過上述方式可知，實際上hashcode的很多位是用不上的，因此在hashMap的hash函式中，才使用了移位運算，只取了前16位來做映射，另一方面&運算比取模效率更高，
六. 擴容
每次都是將cap擴大到與cap最近的2的n次冪，int n = cap - 1;是為了防止cap已經是2的冪次方，如果cap已經是2的冪次方，則執行完后面的幾條無符號右移操作之后，回傳的capacity將是這個cap的2倍，
假設現在cap的初始值為10，具體方式如下：
七. HashMap中常用的方法
1. 構造方法
// 構造方法一：帶有初始容量的構造，負載因子使用默認值0.75
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 構造方法二：
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// 構造方法一：帶有初始容量和初始負載因子的構造
public HashMap(int initialCapacity, float loadFactor) {
// 如果容量小于0，拋出非法引數例外
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// 如果初始容量大于最大值，用2^30代替
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 檢測負載因子是否非法，如果負載因子小于0，或者負載因子不是浮點數，拋出非法引數例外
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// 給負載因子和容量賦值，并將容量提升到2的整數次冪
// 注意：建構式中并沒有給
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
/*
注意：
不同于Java7中的構造方法，Java8對于陣列table的初始化，并沒有直接放在構造器中完成，而是將table陣列的構
造延遲到了resize中完成
*/2. 查找，根據key獲取value
/*
1. 通過key計算出其哈希地址，然后借助哈希地址在哈希桶中找到與key對應的節點
2. 如果節點為null，回傳null，說明HashMap中節點是可以為空的
3. 如果節點不為空，回傳該節點中的value
*/
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 1. 先檢測哈希桶是否為空
// 2. 檢測哈希桶的個數是否大于零，如果桶不空，桶的個數肯定不為0
// 3. n-1&hash-->計算桶號
// 4. 當前桶是否為空桶
// 如果1 2 3 4均不成立，說明當前桶中有節點，拿到當前桶中第一個節點
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 如果節點的哈希值與key的哈希值相等，然后再檢測key是否相等
// 如果相等，則回傳該節點
// 此處也進一步證明了：HashMap必須要重寫hashCode和equals方法
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 如果第一個節點后還有節點，檢測first是否為treeNode型別的
// 因為如果哈希桶中某條鏈節點大于8個，為了提高性能，HashMap會將鏈表替換為紅黑樹
// 此時再紅黑樹中找與key對應的節點
if ((e = first.next) != null) {
if (first instanceof TreeNode) // 通過檢測節點的型別知道是鏈表還是紅黑樹
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 當前桶中掛接的是一個鏈表
// 順著鏈表的節點一個一個往下找，找到之后回傳
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
3. 檢測key是否存在
/*
1. 先通過getNode()獲取與key對應的節點
2. 如果節點不為空，說明存在回傳true，否則回傳false
3. 時間復雜度：平均為O(1)，如果當天key所對應的桶中掛接的鏈表則順序查找，掛接的是紅黑樹按照紅黑樹性質找
*/
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}4. 插入
/*
1. 先使用key借助hash函式計算key的哈希地址
2. 將key-value鍵值對，結合計算出的hash地址插入到哈希桶中
3. 從以下代碼中可以看到，HashMap在插入時，并沒有處理執行緒安全問題，因此HashMap不是執行緒安全的
4. 紅黑樹優化鏈表過長是java8新引進，是基于性能的考慮，在沖突大時，紅黑樹演算法會比鏈表綜合表現更好
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 1. 桶如果是空的，則進行擴容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 2. (n-1)&hash-->計算桶號，如果當前桶中沒有節點，直接插入
// p來記錄桶中的第一個節點
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 3. 如果key已經是和桶中第一個節點相等，不進行插入
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode) // 4. 如果該桶中掛接的是紅黑樹，向紅黑樹中插入
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 5. key不同，也不是紅黑樹，說明當前桶中掛的是一個鏈表
// a. 在當前鏈表中找key
// b. 如果找到，則不插入
// c. 如果沒有找到，先構建新節點，然后將該節點尾插到鏈表中
// d. 檢測bitCount的計數，binCount記錄的是在未插入新節點前原鏈表的節點個數
// e. 新節點插入后，鏈表長度是否超過TREEIFY_THRESHOLD，如果超過將鏈表轉換為紅黑樹
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// p已經是最后一個節點，說明在鏈表中未找到key對應的節點
// 進行尾插
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash); // 將鏈表轉化為紅黑樹
break;
}
// 如果key已經存在，跳出回圈
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 如果key已經存在，將key所對節點中的value替換為引數指定value，回傳舊value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
/*
注意：afterNodeAccess和afterNodeInsertion主要是LinkedHashMap實作的，HashMap中給出了該方法，但是
并沒有實作
*/
// Callbacks to allow LinkedHashMap post-actions
// 訪問、插入、洗掉節點之后進行一些處理，
// LinkedHashMap正是通過重寫這三個方法來保證鏈表的插入、洗掉的有序性
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
/*
LinkedHashMap: 繼承了HashMap，在LinkedHashMap中會對以上方法進行重寫，以保證存入到LinkedHashMap中
的key是有序的，注意這里的有序是不自然序列，指的是插入元素的先后次序
LinkedHashMap底層的哈希桶使用的是雙向鏈表
*/5. 洗掉
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
// 1. 檢測哈希表是否存在
// 2. index = (n - 1) & hash: 獲取桶號
// 3. p記錄當前桶中第一個節點，如果桶中沒有節點，直接回傳null
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
// 如果第一個節點就是key，用node記錄
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
// 如果當前桶下是紅黑樹，在紅黑樹中查找，結果用node記錄
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
// 當前桶下是鏈表，遍歷鏈表，在鏈表中檢測是否存在為key的節點
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// node不為空，在HashMap中找到了
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// 如果節點在紅黑樹中，將其洗掉
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
// 如果節點是鏈表中第一個節點，將當前鏈表中下一個節點地址放在桶中
else if (node == p)
tab[index] = node.next;
else
p.next = node.next; // 非第一個節點
++modCount;
--size;
// LinkedHashMap使用
afterNodeRemoval(node);
// 洗掉成功，回傳原節點
return node;
}
}
// 洗掉失敗回傳空
return null;
}八. HashMap常考問題
1. 如果new HashMap(19)，bucket陣列多大？
在Java1.8中，new的時候并沒有給陣列開辟空間，而是在第一次插入的時候才開辟空間，開辟的空間為比19大且最接近19的冪次方，2^4=16,2^5=32,故bucket陣列的大小為32
2. HashMap什么時候開辟bucket陣列占用記憶體？
這個問題上面答案中已經回答過了，在第一次插入的時候才開辟空間記憶體
3. hashMap何時擴容？
當表中有效元素的個數 >= 負載因子 * 表格容量的時候需要擴容，擴容也是按照2的冪次方來進行擴容的
4. 當兩個物件的hashcode相同會發生什么？
在get()時：如果hashcode相同，先通過equal方法比較key是否一樣，如果key也相同將value直接回傳，否則回傳空
在插入時：如果hashcode相同，再判斷key是否存在，如果key已經存在，將key對應的value進行替換，如果key不存在則插入
在洗掉時：如果hashcode相同，則key可能是我們要洗掉的，通過equals對比，如果是則洗掉，如果不是則回傳
5. 如果兩個鍵的hashcode相同，你如何獲取值物件？
遍歷與hashCode值相等時相連的鏈表，直到相等或者 null
6. 你了解重新調整HashMap大小存在什么問題嗎？
如果將HashMap的容量進行改變，就必須將原來表中的節點重新哈希，擴容的目的就是將節點重新哈希，將鏈表變短
7. 為什么要重寫hashcode()與equals()方法？
重寫hashcode：底層原理是通過key來計算hashcode，通過hashcode來計算hash，hash回傳的是一個整型數字，再通過這個數來進行除留余數，計算的結果為桶的位置，但是對于自定義型別，key不能轉化為整型數字，必須重寫hashcode方法來使自定義型別的key轉化為整型數字以此來得到桶的位置，
重寫equals：當發生哈希沖突時，得比較key是否相同，而比較需要用到equals方法，對于自定義型別比較key的時候得重寫equals方法來比較key的內容是否相同，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/393922.html
標籤：其他
上一篇：嵌入式實時作業系統8——等待表
下一篇：Manacher(馬拉車演算法）