源碼版本：jdk1.8
接口繼承
源碼注釋概要：
- 允許key和value的值為null
- 與Hashtable不同的地方，HashMap是unsynchronized，線程不安全，Hashtable不允許key和value為null，但是線程安全
- 疊代整個HashMap的時候，時間複雜度是和HashMap執行個體的容量呈正相關的，如果業務需要經常疊代整個HashMap，初始容量不要設定得過高（負載因子也不要設定得太低）
- 容量定義：HashMap的bucket數目
- 負載因子定義：在容量自動擴容之前，裝物品的一個路徑成本，比如現在有10個bucket，現在負載因子定義為0.6，那麼裝滿了6個bucket之後就不能再裝了，就需要擴容之後才能繼續裝。
- 重建規則：鍵值映射數量> 負載因子*容量，HashMap的結構将被重建，容量變為2倍,結構被重建，意味着不同時間疊代同一個HashMap順序可能會不同
- 負載因子預設值為0.75，平衡考慮了時間複雜度和空間複雜度。負載因子高，空間使用率高，但是會增加查詢消耗,負載因子低則會導緻空間浪費。
-
Map m = Collections.synchronizedMap(new HashMap(…)) 這樣使用，可以保證HashMap的原子性
10.疊代器的方法都采用了fail-fast（快速失敗機制），隻要在疊代的時候哈希表被修改，就會及時抛出ConcurrentModificationException異常，而避免以後出現不定期的，難以定位的錯誤。
底層使用數組、連結清單、紅黑樹實作。
HashMap采用鍊位址法來實作，将所有關鍵字為同義詞的結點連結在同一個單連結清單中，也就是同一個bucket中。
- 可以結合三者的優點，數組便于随機存儲，是以計算hash碼所在的bucket最為合适
- 連結清單正好維護處于一個bucket的所有Node節點。連結清單便于修改，删除，時間複雜度為O（1）,但是查詢隻能按鍊查找，時間複雜度為O（N）。
- 但是連結清單查找的時候時間複雜度為O(N),如果連結清單過長，時間消耗太多，是以，對應bucket的Node節點如果過多，就轉為紅黑樹維護，這樣查詢，修改，删除都是O(logN)的時間複雜度
哈希存儲結構
定義了一個Node<K,V> 的内部類，實作了Map.Entry<K,V>的接口，維護<K,V>鍵值對，普通連結清單節點使用Node維護，紅黑樹節點使用TreeNode
TreeNode 繼承了LinkedHashMap.Entry<K,V>
get()
get(Object key)方法根據指定的key值傳回對應的value，該方法調用了getNode(hash(key), key)得到相應的Node，然後傳回對應Node.value。
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
} 算法思想是首先通過hash()函數得到對應bucket的下标，然後查找對應bucket的連結清單或者紅黑樹，通過key.equals(k)方法來判斷是否是要找的那個鍵值對Node。
hash()
hashCode 為native方法，這裡主要好奇的是為啥要這麼異或。hashCode()方法傳回的是int類型的資料，總共4位元組，一共32位。
因為哈希表bucket數組的容量為2的幂次方，是以是僅在目前數組mask上的比特上變化的哈希值将會總是發生碰撞。
hashCode的高16位異或低16位得到哈希值，這樣既減少了哈希碰撞，同時也不是很複雜，沒有增加多少系統的開銷。
為什麼(hashcode ＞＞＞ 16)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
} getNode()
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
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;
} 首先會檢查第一個Node,如果不是，就判斷這個Node上面是不是一棵樹，是樹就在樹上查找，不然就依次的按連結清單順序查找。
大緻示意圖如下所示。
我們還可以看到，源碼中找對應的bucket是通過這個(n - 1) & hash實作的，這就是為什麼哈希表的容量必須為2的幂次方的原因，可以使用位運算快速求出要查詢的hash碼所在的bucket 。如上所示，容量為8的哈希表，n-1=0111 ，與hash碼相與，正好消掉高位，使得隻能映射到0-7區間内，也等價于hash%8。但是一般位運算會比較快
put()
調用putVal()方法，這裡第四個參數對應putVal()的onlyIfAbsent()，寫死了，為false。
為true時，隻有哈希表不存在這個key,才會put
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
} putVal()
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//取所在的bucket,如果為null,則建立一個
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//比較第一個節點
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果為紅黑樹，轉為紅黑樹查詢
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//轉為連結清單查詢
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//這裡設定的是一個門檻值，表明連結清單的長度如果剛好達到TREEIFY_THRESHOLD常量，就調用treeifyBin()方法，将連結清單轉為紅黑樹
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;
}
}
//如果找到了這個key已經存在,覆寫掉以前的鍵值對映射
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//快速失敗機制的modCount
++modCount;
//先插入，再擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
} 這裡有一個有意思的地方就是，連結清單轉為紅黑樹的部分，大家試想，為什麼不插傳入連結表的時候，連結清單維護的資料數超過TREEIFY_THRESHOLD常量就直接轉為紅黑樹呢？
這裡非常類似懶加載，懶惰标記之類的思想。因為并不是每一個連結清單的資料我們都需要将他轉化為紅黑樹，因為轉化是需要時間消耗的，這個工作我們不一定要做。隻有等别人查詢到他的時候，我們才轉化。就好像平時我們做工作，沒必要把所有事都按照最終标準來，說不定我們弄的那個東西别人根本不會來查，這樣我們的工作就沒有意義。是以不要用勤奮要掩蓋你戰術上的懶惰就是這個意思。
當連結清單長度大于TREEIFY_THRESHOLD常量時，并且此時哈希buckets數組容量必須大于MIN_TREEIFY_CAPACITY才能将連結清單轉為紅黑樹
remove(Object key)
其實感覺有時候源碼為啥要封裝成多個函數？
但是看的時候又會發現，你能夠很清晰的明白這個函數是幹嘛用的，是以把業務盡量拆成了單一職責的業務，是為了友善調試和理清業務邏輯吧。
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
} removeNode()
參數
- hash： key的hash值
- key
- value
- matchValue 如果為真，隻在值相等時移除
- movable 如果為false，則在移除時不要移動其他節點
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;
//找對對應的bucket
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;
//比對第一個Node
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
//繼續查找
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
//去紅黑樹裡面查找
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
//去連結清單查找
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
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;
afterNodeRemoval(node);
return node;
}
}
return null;
} 擴容操作resize()
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) { //哈希表平常擴容進入的分支，而下面的else分支對應的HashMap幾個構造函數對應的情況
if (oldCap >= MAXIMUM_CAPACITY) {
//threshold設定到Integer的最大值，但是并不擴容，傳回
threshold = Integer.MAX_VALUE;
return oldTab;
}
//數組大小*2
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 門檻值也乘2
}
else if (oldThr > 0) //對應的HashMap(int initialCapacity, float loadFactor)構造出來的hashMap,第一次put的時候進入
newCap = oldThr;
else { // 其他構造方法，第一次put的時候進入
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
//周遊原數組，将非空元素複制到新數組裡面去
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) { //該bucket不為null
oldTab[j] = null; //原資料置為null，資料已經由e接手
if (e.next == null) //該bucket隻有一個元素
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode) //如果該節點是紅黑樹節點
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//判斷這條元素連結清單是否需要更換bucket
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//不需要移動bucket,在新表的 原bucket位置 也就是j放入這個連結清單
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//需要移動bucket,在新表的 原bucket+原表容量 位置放入這個連結清單
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
} 這裡面連結清單複制那一段代碼維護了兩個連結清單，然後分别放在新表不同的bucket的裡面
- 一類連結清單是需要移動bucket的元素
-
一類連結清單維護的是不需要移動bucket的元素
比如我們原來哈希表的bucket數目為8，那麼編号就是0-7
現在我們老表裡面的2号bucket下存放的有10,18,26等hash碼的元素，那麼分别移動到新表的哪些bucket裡面呢？
10&8=8 需要移動到2+8（原來的容量大小）的bucket裡面
18&8=0 不需要移動bucket
26&8=8 需要移動到2+8（原來的容量大小）的bucket裡面
存放在老表的2号bucket裡面的元素隻可能是哈希碼為8x+2(x為自然數)，是以說具有16x+2(x為自然數)的哈希碼元素就不用移動到其他的bucket裡面。
我們隻需要将元素的hash碼與原來的容量大小相與即可知道是否該移動這個元素到新的bucket裡面去。
自定義對象哈希
在HashMap的put（）函數運作的代碼中，我們會發現hashCode()和equals()方法是做判斷對比Key所要用到的函數。
hashCode()是Native()方法。
HashMap的equals（）是使用Object的equals（）方法，如下面代碼所示是直接用==比對的
public boolean equals(Object obj) {
return (this == obj);
} 是以不适用于對象，但是我們使用的Integer,String等包裝類卻可以，進入他們的源碼可以看到都是重寫了這兩個方法的，是以我們自己定義的類也需要重寫這兩個方法。
public static int hashCode(int value) {
return value;
}
public boolean equals(Object obj) {
if (obj instanceof Integer) {
return value == ((Integer)obj).intValue();
}
return false;
} 如果我們不重寫這兩個方法
使用如下代碼測試
public class A{
static class People {
int age;
int sex;
String name;
public People(int age,int sex,String name){
this.age = age;
this.sex = sex;
this.name = name;
}
@Override
public String toString() {
return "People{" +
"age=" + age +
", sex=" + sex +
", name='" + name + '\'' +
'}';
}
}
public static void main(String[] args){
HashMap<People,Integer> hashMap = new HashMap<>();
hashMap.put(new People(1,0,"tom"),1);
hashMap.put(new People(1,0,"tom"),2);
hashMap.put(new People(2,1,"jim"),3);
for(People people:hashMap.keySet()){
System.out.print(people);
System.out.printf(":%d\n",hashMap.get(people));
}
System.out.println(new People(1,0,"tom").hashCode());
System.out.println(new People(1,0,"tom").hashCode());
System.out.println(new People(2,1,"jim").hashCode());
}
} 運作結果
可以看見HashMap存入多個具有同樣值的Key,不然按照HashMap的規則應該将用新的Value覆寫老的Value,隻會保留一個<Key,Value>映射，但是這裡有兩個。
對于hashCode()，我們可以看見具有相同值的兩個People執行個體的哈希碼是不一樣的，這個hashCode()是Native方法。
對于equals(),調用Object.equals()方法
public boolean equals(Object obj) {
return (this == obj);
} 因為java是函數調用是傳的執行個體的位址，同時因為我們new的多個對象執行個體位址不一樣，這樣就會出錯。
在People類裡面重寫Object類的這兩個方法即可
@Override
public int hashCode() {
final int prime = 13331;
long code = 1;
code = (prime * code + age)%Integer.MAX_VALUE;
code = (prime * code + sex)%Integer.MAX_VALUE;
code = (prime * code + name.hashCode())%Integer.MAX_VALUE;
return (int)code;
}
@Override
public boolean equals(Object obj) {
if (obj == null){
return false;
}
if (this == obj){
return true;
}
if (getClass() != obj.getClass()){
return false;
}
People contrast = (People) obj;
if (age != contrast.age){
return false;
}
if(sex != contrast.sex){
return false;
}
if(!name.equals(contrast.name)){
return false;
}
return true;
}}