背景
上一篇文章《哈希表、hashCode鲸沮、HashMap的實現(xiàn)》講述了什么是哈希表琳骡、哈希函數(shù)，以及點了一下HashMap讼溺，這篇文章著重講一下HashMap的實現(xiàn)原理楣号。
散列表
Hash table(散列表、哈希表)怒坯，當(dāng)我們需要存儲集合或字典炫狱，使用線性表、樹去存儲時剔猿，元素在存儲結(jié)構(gòu)中的位置與元素的關(guān)鍵碼之間不存在直接的對應(yīng)關(guān)系毕荐，所以在要搜索一個元素時都需要進行一系列的關(guān)鍵碼比較，搜索的效率取決于搜索過程進行的比較次數(shù)艳馒。而散列表（Hash table）是表示集合和字典的另一種有效方法，它提供了一種完全不同的存儲和搜索方式，通過關(guān)鍵碼映射到表中某個位置來存儲元素弄慰，然后根據(jù)關(guān)鍵碼用同樣的方式直接訪問第美。
HashMap實現(xiàn)原理
HashMap的主干是一個Entry數(shù)組。Entry是HashMap的基本組成單元陆爽，每一個Entry包含一個key-value鍵值對什往。
//HashMap的主干數(shù)組，可以看到就是一個Entry數(shù)組慌闭，初始值為空數(shù)組{}别威，主干數(shù)組的長度一定是2的次冪，至于為什么這么做驴剔，后面會有詳細分析省古。
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
Entry是HashMap中的一個靜態(tài)內(nèi)部類。代碼如下
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;//存儲指向下一個Entry的引用丧失，單鏈表結(jié)構(gòu)
int hash;//對key的hashcode值進行hash運算后得到的值豺妓，存儲在Entry，避免重復(fù)計算
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
所以布讹，HashMap的整體結(jié)構(gòu)如下
簡單來說琳拭，HashMap由數(shù)組+鏈表組成的，數(shù)組是HashMap的主體描验，鏈表則是主要為了解決哈希沖突而存在的白嘁，如果定位到的數(shù)組位置不含鏈表（當(dāng)前entry的next指向null）,那么對于查找，添加等操作很快膘流，僅需一次尋址即可絮缅；如果定位到的數(shù)組包含鏈表，對于添加操作睡扬，其時間復(fù)雜度為O(n)盟蚣，首先遍歷鏈表，存在即覆蓋卖怜，否則新增屎开；對于查找操作來講，仍需遍歷鏈表马靠，然后通過key對象的equals方法逐一比對查找奄抽。所以，性能考慮甩鳄，HashMap中的鏈表出現(xiàn)越少逞度，性能才會越好。
關(guān)于hashCode
1. hashCode的存在主要是用于查找的快捷性妙啃，如Hashtable档泽，HashMap等俊戳，hashCode是用來在散列表中確定對象的存儲地址的。
2. 如果兩個對象相同馆匿，就是適用于equals(java.lang.Object) 方法抑胎，那么這兩個對象的hashCode一定要相同
3. 如果對象的equals方法被重寫，那么對象的hashCode也盡量重寫渐北，并且產(chǎn)生hashCode使用的對象阿逃，一定要和equals方法中使用的一致，否則就會違反上面提到的第2點
4. 兩個對象的hashCode相同赃蛛，并不一定表示兩個對象就相同恃锉，也就是不一定適用于equals(java.lang.Object) 方法，只能夠說明這兩個對象在散列存儲結(jié)構(gòu)中呕臂，如Hashtable破托，他們“存放在同一個籃子里“
