一、什么是hash
哈希算法
接受任意長度的二進(jìn)制輸入值哟冬，對輸入值做換算（hash）嫂便，最終給出固定長度的二進(jìn)制輸出值嘱么；
Hash算法不是某個(gè)固定的算法，它代表的是一類算法顽悼，具體換算可能各不相同
哈希表
即散列表曼振，一種數(shù)據(jù)結(jié)構(gòu)，根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問
給定表M蔚龙，存在函數(shù)f(key)冰评，對任意給定的關(guān)鍵字值key，代入函數(shù)后若能得到包含該關(guān)鍵字的記錄在表中的地址木羹，則稱表M為哈希(Hash）表甲雅，函數(shù)f(key)為哈希(Hash) 函數(shù)
哈希碰撞
根據(jù)上面對哈希表的定義，有一種情況是坑填，對不同的關(guān)鍵字可能得到同一散列地址抛人，即k1≠k2，但f(k1)=f(k2)脐瑰，這種情況就是哈希碰撞妖枚。
解決哈希碰撞
拉鏈法（hashmap的解決方式）：
將鍵轉(zhuǎn)換為數(shù)組的索引(0-M-1)，但是對于兩個(gè)或者多個(gè)鍵具有相同索引值的情況苍在，將大小為M 的數(shù)組的每一個(gè)元素指向一個(gè)條鏈表绝页，鏈表中的每一個(gè)節(jié)點(diǎn)都存儲散列值為該索引的鍵值對，這就是拉鏈法
二寂恬、HashMap的實(shí)現(xiàn)
基于哈希表的數(shù)據(jù)結(jié)構(gòu)
線程不安全
下面從代碼上來分析HashMap的實(shí)現(xiàn)原理
1. HashMap的結(jié)構(gòu)
//實(shí)體數(shù)組
transient Node<K,V>[] table;
//實(shí)體構(gòu)造函數(shù)
static class Node<K,V> implements Map.Entry<K,V> {
Node(int hash,K key,V value,Node<K,V> next){
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;//鏈表中下一個(gè)元素的引用
}
}
由上面的代碼可以看出HashMap的基本結(jié)構(gòu)就是:
- 儲存的結(jié)構(gòu)是實(shí)體Node<K,V>[]续誉，即一個(gè)Map.Entry<K,V>。內(nèi)部4個(gè)值初肉，key-value鍵值對酷鸦，hash值，以及指向下一個(gè)元素的引用next牙咏，構(gòu)成鏈表臼隔。
- 實(shí)體Node再構(gòu)成的一個(gè)數(shù)組 Node<K,V>[] table
- 而這個(gè)結(jié)構(gòu)正是我們上面提到的hash表的結(jié)構(gòu)，并很明顯是用拉鏈法來解決hash沖突
2. put
//使用樹而不是列表的bin計(jì)數(shù)閾值
static final int TREEIFY_THRESHOLD = 8;
public V put(K key, V value) {
// 對key的hashCode()做hash
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab;
Node<K,V> p;
int n, i;
//數(shù)組tab為空則創(chuàng)建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果沒有發(fā)生hash碰撞眠寿，則直接添加到數(shù)組tab中
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//發(fā)生了hash碰撞
else {
Node<K,V> e; K k;
//是否hash值相同躬翁，且key值也相同，即節(jié)點(diǎn)已存在
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//hash值相同盯拱，且key值也相同
e = p;
//該鏈?zhǔn)荰reeNode
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//該鏈?zhǔn)菫殒湵砗蟹ⅲ闅v鏈表
for (int binCount = 0; ; ++binCount) {
//遍歷到鏈表的尾部
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//鏈表過長例嘱，轉(zhuǎn)化為紅黑樹，以提高效率
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//遍歷過程中發(fā)現(xiàn)節(jié)點(diǎn)已存在
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//節(jié)點(diǎn)已經(jīng)存在宁舰，則替換為新的值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 超過load factor*current capacity拼卵，resize
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
由上述代碼可以看出put的邏輯
- 對key的hashCode()做hash計(jì)算得到hash值
- 根據(jù)hash值計(jì)算出對應(yīng)在哈希表的數(shù)組中Node<K,V>[] table中的下標(biāo)：index = (size - 1) & hash
- 如果該下標(biāo)上沒有存放Node<K,V>，即沒有發(fā)生hash碰撞蛮艰，則存放到table的該下標(biāo)上
- 如果該下標(biāo)上已經(jīng)有存放Node<K,V>腋腮，即發(fā)生了hash碰撞，則存放到table的該下標(biāo)的鏈表的尾部
- 如果碰撞導(dǎo)致鏈表過長(大于等于TREEIFY_THRESHOLD=8)則會把鏈表轉(zhuǎn)換成紅黑樹
- 如果節(jié)點(diǎn)已經(jīng)存在就替換節(jié)點(diǎn)的值oldValue為新值
- 如果table已經(jīng)滿了壤蚜，則resize增加table的長度
3. get()
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;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//直接找到了節(jié)點(diǎn)對應(yīng)在table中的下標(biāo)
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
//判斷該下標(biāo)下第一個(gè)節(jié)點(diǎn)的key也相同即寡，則直接返回
return first;
if ((e = first.next) != null) {
//開始遍歷鏈表
if (first instanceof TreeNode)
return
//TreeNode ((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;
}
由上述代碼可以看出get的邏輯
- 對key的hashCode()做hash計(jì)算得到hash值
- 根據(jù)hash值計(jì)算出對應(yīng)在哈希表的數(shù)組中Node<K,V>[] table中的下標(biāo)
- 該下標(biāo)上的第一個(gè)元素fristNode和要查找的key值做判斷fristNode.key.equals(key),如果相同，返回
- 如果不相同袜刷，遍歷鏈表直到Node.key.equals(key)聪富，返回
4. 擴(kuò)容resize()
//臨界值（HashMap實(shí)際能存儲的大小）,公式為(threshold = capacity * loadFactor),當(dāng)hashmap中存儲元素大于這個(gè)數(shù)時(shí)著蟹，就需要resize了
int threshold;
/** 負(fù)載因子,默認(rèn)為0.75*/
final float loadFactor;
//默認(rèn)負(fù)載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//數(shù)組默認(rèn)的大小墩蔓，16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//數(shù)組最大的容量，2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//舊表大小不為0
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//把新表的長度設(shè)置為舊表長度的兩倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//把新表的閥值設(shè)為舊表2倍
newThr = oldThr << 1; // double threshold
}
//如果舊表的長度的是0萧豆，則初始化表
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
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;
//構(gòu)造出新表
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;//新表賦值給table
//如果舊表不為空奸披，要把舊表的值轉(zhuǎn)移到新表
if (oldTab != null) {
//遍歷舊表
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//node沒有鏈表則直接放在新表的e.hash & (newCap - 1)位置
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//e是treeNode，則拆樹
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//e有鏈表涮雷，拆鏈表
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;
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);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
由上述代碼可以看出reSize的邏輯
- 先判斷舊表阵面，如果沒有舊表，則初始化一個(gè)默認(rèn)大小的新表或者構(gòu)造函數(shù)中傳入過的initialCapacity大小的新表（默認(rèn)大小16份殿；閥值為12膜钓；16*0.75）嗽交，
- 如果有舊表卿嘲，則初始化一個(gè)新表，大小為舊表的兩倍夫壁，閥值也是舊表的兩倍
- 把舊表的值轉(zhuǎn)移到新表
5. loadFactor和initialCapacity：
loadFactor負(fù)載因子拾枣，代表的是map的裝填程度，構(gòu)造函數(shù)中有
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +loadFactor);
表示loadFactor必須是大于0的數(shù)字盒让。
由前面的知識我們知道HashMap是有數(shù)組table和鏈表的來實(shí)現(xiàn)的
initialCapacity表示HashMap的初始化數(shù)組table的大小
而HashMap的實(shí)際容量 = initailCapacity*loadFactor
當(dāng)HashMap的實(shí)際容量滿的時(shí)候梅肤，才會進(jìn)行resize擴(kuò)充容量
由此可知loadFactor越大，則HashMap中table會填的越滿邑茄，鏈表會越長姨蝴，越容易發(fā)生hash碰撞，造成索引效率低下肺缕；反之則會越稀疏左医，但會造成空間浪費(fèi)授帕。
loadFactor根據(jù)情況進(jìn)行設(shè)置（時(shí)間空間選擇）
注意：initailCapacity的值系統(tǒng)會根據(jù)傳入的值換算成比傳入值大的最接近的2的n次方這是因?yàn)?/p>
table下標(biāo)計(jì)算：index = (size - 1) & hash
如當(dāng)數(shù)組長度為15的時(shí)候，hashcode的值會與size - 1=14（1110）進(jìn)行“與”浮梢，那么最后一位永遠(yuǎn)是0跛十，而0001，0011秕硝，0101芥映，1001，1011远豺，0111奈偏，1101這幾個(gè)位置永遠(yuǎn)都不能存放元素了，空間浪費(fèi)相當(dāng)大
6. 使用注意：
- reSize()比較耗性能的（主要是舊表的值轉(zhuǎn)移到新表）,所以初始化的時(shí)候最好能初始化合適的大小
- HashMap hashMap = new HashMap(1000); 初始化后的表的大小為1024,即總是比傳入值大的最小的2的n次方躯护。這是因?yàn)閿?shù)組長度為2的n次方的時(shí)候霎苗，不同的key算得得index相同的幾率較小，可以減少hash碰撞榛做，從而提高效率
- jdk8中唁盏，HashMap處理碰撞才增加了紅黑樹這種數(shù)據(jù)結(jié)構(gòu)，當(dāng)碰撞結(jié)點(diǎn)較少時(shí)检眯，采用鏈表存儲厘擂，當(dāng)較大時(shí)（>TREEIFY_THRESHOLD=8個(gè)），采用紅黑樹存儲這樣碰撞后的查詢由鏈表變?yōu)榱思t黑樹锰瘸，即時(shí)間復(fù)雜度有O(n)變?yōu)榱薕(logn)
