資訊專欄INFORMATION COLUMN
摘要：的值是在上述方法中處理過的值，通過與當前容量進行，直接獲取到哈希表的位置。策略二，如果已經(jīng)很大了，擴容已經(jīng)不可取，那么就采用紅黑樹結(jié)構(gòu)轉(zhuǎn)化鏈表。紅黑樹的創(chuàng)建不再詳述。紅黑樹的根就是中第一個節(jié)點。
java.util.Map
Map中的自我引用需要小心用易變的對象作為Map的key，這會導致Map的行為無法預測。Map也不可以將自己作為key，可以作為value，但是會導致equals和hashCode方法不是well defined.
Map中有些操作涉及遞歸的遍歷，如果Map自我引用，則有可能出現(xiàn)異常。這些方法包括：clone，equals，hashCode和toString。
Map可以將null作為key和value這是Map接口自己默認實現(xiàn)的一個獲取指定key的value，當沒有該key時可以獲取一個默認值得方法。這就給用戶提供了更靈活的選擇來處理map中沒有存這個key的情況。這里比較有意思的一點是在用v = get(key)判斷一次后，為什么又用containsKey(key)再判斷一次，因為有的map中是允許存null作為value的，所以有key在Map中，但是value為null的情況。
default V getOrDefault(Object key, V defaultValue) {
V v;
return (((v = get(key)) != null) || containsKey(key))
? v
: defaultValue;
}
HashMap
如何求int型數(shù)的最近2次冪
HashMap中，用戶可以初始化容量，但是HashMap中容量皆為2的次冪，所以會把用戶預設的值先轉(zhuǎn)為最近的2的次冪。tableSizeFor方法求出的結(jié)果總是大于或等于cap，且最接近cap的一個2的次冪。當然，對于大于2^30的數(shù)，會返回-2147483648，所以這里會判斷n為負數(shù)的情況，同時，設置了HashMap的最大容量應該為2^30（MAXIMUM_CAPACITY）。
有意思的是經(jīng)過如下幾步就能求得一個2的次冪，下面方法所做的是先求得一個2^n-1，然后+1。獲得一個2^n-1的過程也很巧妙，就是不停的拷貝1。n |= n >>> x;將前x位的1拷貝到了接著的x位。通過幾步位操作就獲得了目標值，不得不贊嘆開發(fā)者的聰明。
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
HashMap的table
HashMap的table就是一個Node的數(shù)組，大小一致保持2的次冪。Node就是HashMap中存儲的元素，它有哈希值、key、value和存儲下一個Node的next屬性。處理沖突的方法是閉哈希方法，也就是有相同的hash值的Node會用鏈表串起來。
HashMap中的hash值如何計算 static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
將key的hashCode的高位和低位部分通過異或合并，使得低位和高位的值都能在hash時發(fā)揮作用。因為哈希表會用一個掩碼來取hashCode的后面一段，如不采用上述方法，前面一部分的hashCode就被忽略了。如果一組key恰巧只在前段的hash值有所差異，而后段都是相同的，則會出現(xiàn)大量的沖突，這種情況在實際中是很可能存在的。
如何將Node哈希到table中公式如：table[node.hash & (capacity - 1)] = node。node的hash值是key在上述hash()方法中處理過的值，通過與當前容量-1進行mask，直接獲取到哈希表的位置。
HashMap的table的擴張如上所述，table大小保持2的次冪，擴張的步驟：
申請一個容量乘以2的新Node數(shù)組。
遍歷table，將原來的元素依次copy到新數(shù)組上，這里原來的鏈表會進行分裂。因為table的擴大，Node的hash值會被多mask一位，所以Node被Hash到的位置也會變化，Node要么保持原位置，要么就是在相對于原位置有一個舊容量大小的偏移。
這里不會將原來的元素重新進行一次hash的過程，重建原來的hash table，這樣代價是比較大的。這里就利用了Node位置變化的規(guī)律，直接將原來的鏈表分裂為兩個。
雖然已經(jīng)進行了優(yōu)化，但是該過程代價還是比較高的，時間復雜度為原table大小+元素數(shù)量，
table中鏈表太長如何處理當Node發(fā)生多次沖突，在一個hash值下建了一個很長的鏈表，這會導致查詢的代價越來越大，這里采用了樹結(jié)構(gòu)來減輕這種問題。
具體過程是，當某個hash值下的鏈表超過了閾值，則會采取策略對其長度進行消解。
如果table還不算大，那么直接對table擴容，鏈表自然會被分裂到兩地。
策略二，如果table已經(jīng)很大了，擴容table已經(jīng)不可取，那么就采用紅黑樹結(jié)構(gòu)轉(zhuǎn)化鏈表。
紅黑樹的創(chuàng)建不再詳述。需要知道，這里采用的是二叉搜索樹，進行比較的是每個hash值，不是key的直接比較。紅黑樹的根就是table中第一個節(jié)點。原始鏈表會先變成雙向鏈表，以保存前后關系，然后再變成樹結(jié)構(gòu)。雖然由鏈表轉(zhuǎn)化成了樹結(jié)構(gòu)，但是每個節(jié)點仍然保存了鏈表的前后關系，所以可以迅速的從樹結(jié)構(gòu)退化為鏈表結(jié)構(gòu)。從TreeNode的屬性中可以看出其既有樹結(jié)構(gòu)的left、right、parent關系，又有prev、next（繼承）的雙向鏈表關系。
