1 存儲數(shù)據(jù)結(jié)構(gòu)
分析源碼之前饵蒂，先了解兩個數(shù)據(jù)結(jié)構(gòu)声诸，數(shù)組和鏈表。
1.1 數(shù)組
- 內(nèi)存中分配固定的空間
- 刪除或者增加退盯，導(dǎo)致數(shù)組下標(biāo)內(nèi)存位移彼乌，效率低
- 數(shù)組大小固定不利于擴(kuò)增
- 隨機(jī)讀取的效率高，因為數(shù)組是連續(xù)的渊迁，知道內(nèi)存地址慰照，可以直接獲取
Object [] arrays;
1.2 鏈表
- 鏈表的內(nèi)存大小不固定
- 刪除增加數(shù)據(jù)方便，因為每一個鏈表節(jié)點存儲了節(jié)點的數(shù)據(jù)和下一節(jié)點的內(nèi)存地址（單項或者雙向）
- 查找數(shù)據(jù)時效率低宫纬，因為不具有隨機(jī)訪問性焚挠，所以訪問某個位置的數(shù)據(jù)都要從第一個數(shù)據(jù)開始訪問膏萧，然后根據(jù)第一個數(shù)據(jù)保存的下一個數(shù)據(jù)的地址找到第二個數(shù)據(jù)漓骚，以此類推。
- 方便擴(kuò)容榛泛，增刪效率高
Node {
Object data;
Node next;
Node prex;
}
1.3 集合特性
對于集合框架我們的關(guān)注點一般在一下幾點：
- 集合底層實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)是什么 數(shù)組+鏈表+紅黑樹
- 集合中元素是否允許為空 key和value都可以為空
- 是否允許重復(fù)的數(shù)據(jù) key不可以蝌蹂，value可以
- 是否有序(這里的有序是指讀取數(shù)據(jù)和存放數(shù)據(jù)的順序是否一致) 否
- 是否線程安全。 否
2 HashMap
通過上面我們看到數(shù)組查詢效率高曹锨，增刪效率低孤个，而鏈表反之，那么問題來了沛简，有沒有一種結(jié)構(gòu)結(jié)合二者的優(yōu)點齐鲤？我們看下hashMap，直接上碼椒楣！
依賴關(guān)系
HashMap主要是繼承自AbstractMap给郊，實現(xiàn)了Cloneable和Serializable接口使得HashMap具有克隆和序列化的功能、實現(xiàn)了Map接口因此具有Map的性質(zhì)捧灰。
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
簡單寫個main淆九，put etc..
HashMap map=new HashMap();
map.put("c","123");
點擊put方法進(jìn)入源碼世界
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
看english注解，發(fā)現(xiàn)如果你put的key已經(jīng)存在的話，處理完會覆蓋之前的值炭庙，并且返回舊值饲窿，but putVal后面多了兩個參數(shù)，先不管他,這個hash(key)有必要了解下焕蹄，go on
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
h>>>16代表右位移逾雄，低位溢出，符號位不變擦盾，并用符號位補(bǔ)溢出的高位嘲驾，那么看下hashCode()方法，打開Object類迹卢，可以看到
public native int hashCode();//c++寫的貌似我看不到
public int hashCode() {//這個是String類下重寫的
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
public static int hashCode(int value) {//這個是Interger類重寫的
return value;
}
//etc...
原來不同對象都可以重寫此方法辽故，獲取一串不唯一的數(shù)字，然后做右移操作腐碱，然而這個值來干啥呢誊垢？go on！
/**
* 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) {
}
好症见，來到這里終于知道之前的兩個參數(shù)啥意思了喂走，putVal(hash(key), key, value, false, true); onlyIfAbsent if true, don't change existing value，evict if false, the table is in creation mode
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
初始化為空的走擴(kuò)容谋作，下面著重看下resize方法,只考慮初始化芋肠，刪除其他的代碼
final Node<K,V>[] resize() { //通過這個方法也能看出，map的本質(zhì)是Node數(shù)組
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;//這個說明鬼遵蚜，接著往下看
int newCap, newThr = 0;
newCap = DEFAULT_INITIAL_CAPACITY;//點擊看默認(rèn)16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//這個是總大小*負(fù)載因子帖池，默認(rèn)0.75
}
threshold = newThr;
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//開辟數(shù)組
table = newTab;
return newTab;
}
內(nèi)存有了，接著走吭净，根據(jù)hash取存儲下標(biāo)睡汹，如果這個地方?jīng)]有值，那就存數(shù)據(jù)
if ((p = tab[i = (n - 1) & hash]) == null)//經(jīng)過高位運算的hash值和數(shù)組的大小-1取與寂殉，也就是說取值的范圍0-15也就是數(shù)組的下標(biāo)
tab[i] = newNode(hash, key, value, null);
································································································································
//在回顧下node的結(jié)構(gòu)囚巴，單鏈表
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;//hash在這里
this.key = key;
this.value = value;
this.next = next;
}
那么問題來了hash值一樣了怎么辦？ 怎么會一樣友扰，比如String a彤叉，Interger 97
HashMap map=new HashMap();
map.put(new String("a"),"a");
map.put(new Integer(97),97);
//String hashCode 方法
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
//Interger hashCode 方法
public static int hashCode(int value) {
return value;
}
如果存在相同的hash值，那么第二個來的時候必然已經(jīng)存在
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; //如果key是同一個對象村怪，把存在的節(jié)點賦值給e秽浇，那值怎么辦？別著急賦值在后面
else if (p instanceof TreeNode)//1.8新增的一種結(jié)構(gòu)实愚，稍后看
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//這里就是解決hash沖突的地方了
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // 多了個限制兼呵，防止鏈表無限擴(kuò)充吧兔辅，稍后分析
treeifyBin(tab, hash);
break;
}
//鏈表已經(jīng)存在沖突的hash數(shù)據(jù)，如果key對象和再次傳過來的一樣击喂，直接返回當(dāng)前node的節(jié)點维苔，即更改引用。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // 最后復(fù)制操作來了
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)//開關(guān)+以前的數(shù)據(jù)為空懂昂，就覆蓋
e.value = value;
afterNodeAccess(e);
return oldValue;
}
上面代碼可以看到遍歷當(dāng)前的Node節(jié)點介时，看他的下一個是不是存在，如果不存在凌彬，就放在他下一個的位置
那么極端情況沸柔，hash一直沖突，Node就可以無限增長了嗎铲敛，肯定是不可以的褐澎。
TREEIFY_THRESHOLD 看下源碼大小限制為8,超過了走treeifyBin()，然后再看下treeifyBin方法
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();//如果小于64繼續(xù)擴(kuò)容
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
超過64轉(zhuǎn)樹伐蒋，小于64通過擴(kuò)容解決工三，先瞧瞧不到64繼續(xù)擴(kuò)容會怎樣，繼續(xù)看下resize方法的實現(xiàn)
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
進(jìn)行擴(kuò)容oldCap << 1 位運算增加一倍先鱼，擴(kuò)容怎么能解決hash沖突俭正？繼續(xù)往下go
最下面，循環(huán)遍歷舊的數(shù)組焙畔，針對沒有子節(jié)點的鏈表掸读，重新計算index的位置，賦值宏多。
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
接著針對有子節(jié)點的Node
/**
JDK1.7中儿惫，resize時，index取得時绷落，全部采用重新hash的方式進(jìn)行了姥闪。JDK1.8對這個進(jìn)行了改善始苇。
以前要確定index的時候用的是(e.hash&oldCap-1)砌烁，是取模取余，而這里用到的是(e.hash &oldCap)
它有兩種結(jié)果催式，一個是0函喉，一個是oldCap，
比如oldCap=8,hash是3荣月，11管呵，19，27時哺窄，
(e.hash & oldCap)的結(jié)果是0捐下，8账锹，0，8缺谴，這樣3彬碱，19組成新的鏈表鹉梨，index為3
而11，27組成新的鏈表廓奕，新分配的index為3+8；
JDK1.7中重寫hash是(e.hash & newCap-1)档叔，也就是3桌粉，11，19衙四，27對16取余铃肯，也是3，11传蹈，3缘薛，11，
和上面的結(jié)果一樣卡睦，但是index為3的鏈表是19宴胧，3，index為3+8的鏈表是27表锻，11恕齐，
也就是說1.7中經(jīng)過resize后數(shù)據(jù)的順序變成了倒敘，而1.8沒有改變順序瞬逊。
**/
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;
}
也就是說針對e.hash & oldCap=0的保持原來的索引位置不變显歧，為1的原索引位置+原數(shù)組的大小，這也是是1.8針對1.7做的優(yōu)化确镊∈恐瑁回過頭來再分析下如果數(shù)組Node總大小大于64了會怎樣？
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
接下來分析不下去了蕾域，因為要補(bǔ)下紅黑樹的知識點拷肌。。旨巷。先分析下get接口巨缘，關(guān)鍵代碼如下
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;//直接找到返回value值
if ((e = first.next) != null) {//出現(xiàn)沖突，遍歷節(jié)點
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;
}
