前面分析了List的兩個(gè)實(shí)例類(lèi)吧趣，現(xiàn)在我們開(kāi)始分析Map和悦。至于為什么跳過(guò)Set先分析Map。嘿嘿榜揖，Set中的HashSet是基于HashMap實(shí)現(xiàn)的勾哩、TreeSet是基于TreeMap實(shí)現(xiàn)的這種事情，我會(huì)先劇透举哟？
HashMap定義及說(shuō)明
按照慣例思劳，先看定義：
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {}
先分析一下定義：
1、繼承了AbstractMap妨猩，實(shí)現(xiàn)了Map接口潜叛。即可以有Map基本的操作。還通過(guò)AbstractMap默認(rèn)實(shí)現(xiàn)了部分方法壶硅。
2威兜、實(shí)現(xiàn)了Cloneable，即支持clone庐椒。
3牡属、實(shí)現(xiàn)了Serializable，即支持序列化和反序列化扼睬。
接下來(lái)逮栅，再看看構(gòu)造方法：
//數(shù)組的最大長(zhǎng)度
static final int MAXIMUM_CAPACITY = 1 << 30;
//默認(rèn)加載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//使用指定的初始容量和加載因子構(gòu)造一個(gè)空的HashMap
public HashMap(int initialCapacity, float loadFactor) {
//指定的初始容量不能小于0
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//使用的初始容量不能大于1*2^30
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//加載因子不能小于等于0或者是非數(shù)字的值(無(wú)窮大或無(wú)窮小等)
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
//給初始容量和加載因子賦初值
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
//使用指定的初始容量和默認(rèn)加載因子（0.75）構(gòu)造一個(gè)空的HashMap
public HashMap(int initialCapacity){
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//使用默認(rèn)初始容量（16）和默認(rèn)加載因子（0.75）構(gòu)造一個(gè)空的HashMap
public HashMap(){
//初始化默認(rèn)加載因子
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
//使用與指定Map相同的映射構(gòu)造一個(gè)新的HashMap悴势。 使用默認(rèn)加載因子（0.75）和足以在指定的Map 中保存映射的初始容量創(chuàng)建HashMap。
public HashMap(Map<? extends K, ? extends V> m) {
}
從第一個(gè)構(gòu)造函數(shù)中我們可以看到對(duì)初始容量和加載因子的限定措伐。初始容量不能大于2^30且必須是2的冪特纤。加載因子必須大于0且小余無(wú)窮大。了解了這些后侥加，我們?nèi)タ纯碒ashMap是怎么工作的捧存。
HashMap的源碼簡(jiǎn)析
初始化了一個(gè)Map之后，我們一般會(huì)往Map中添加元素担败，那么昔穴，就去put()方法中看一下。不過(guò)提前，在看源碼之前吗货，我們先了解一些概念，以便理解源碼
準(zhǔn)備工作(哈希表)
hashCode
假如我們需要一個(gè)存儲(chǔ)鍵值對(duì)的容器狈网，我們會(huì)這怎樣去構(gòu)建它宙搬？比如創(chuàng)建一個(gè)數(shù)組，用數(shù)組來(lái)存儲(chǔ)拓哺？但是如果我們想從中取出某個(gè)對(duì)象呢勇垛？那我們就的去遍歷這個(gè)數(shù)組，看看是否有對(duì)應(yīng)的鍵士鸥。這么做的效率是很低的闲孤，那么，有沒(méi)有一種方式可以把所有類(lèi)型的值都轉(zhuǎn)化為整數(shù)烤礁，這樣讼积，我們就可以根據(jù)索引來(lái)存取值了。
我們知道鸽凶，object是所有類(lèi)的基類(lèi)币砂，而Object中提供了hashCode方法來(lái)獲取一個(gè)對(duì)象的hashCode值建峭。通過(guò)這個(gè)方法玻侥，可以返回一個(gè)32位的整數(shù)。這樣亿蒸，我們就有了一個(gè)整數(shù)值來(lái)做索引了凑兰。但是，用這么大的值來(lái)做索引明顯不可行边锁。那么怎么辦呢姑食？我們有沒(méi)有什么辦法可以縮小這個(gè)值嗎？
除留余數(shù)法
除留余數(shù)法為最常用的構(gòu)造散列函數(shù)方法茅坛，假如有一個(gè)初始長(zhǎng)度為m的數(shù)組音半，我們要根據(jù)某個(gè)對(duì)象的hashcode計(jì)算出一個(gè)0～m-1的整數(shù)则拷，用來(lái)將它放入數(shù)組中，則計(jì)算公式為：
f(key) = key mod p (p ≤ m)
其中曹鸠，mod為取模(求余數(shù))的意思(即取hashcode%m)煌茬。這樣，我們就將一個(gè)大的整數(shù)轉(zhuǎn)化為一個(gè)數(shù)組可以接受的數(shù)字彻桃。但是坛善，這么算的話，會(huì)出現(xiàn)很多hashcode值不同邻眷，但是結(jié)果相同的情況眠屎，即哈希碰撞。處理碰撞有兩種常用的方式：開(kāi)放地址法和鏈地址法肆饶。
開(kāi)放地址法(線性探測(cè)法)
開(kāi)放地址法改衩，就是如果發(fā)生了沖突，就去尋找下一個(gè)空的散列地址抖拴。只要表足夠大燎字，總是能找到的。
公式為：
fi(key)=(f(key)+di) MOD m (di=1,2,…,k(k<=m-1))
這種做法具體是指當(dāng)沖突發(fā)生的時(shí)候阿宅，使用某種探測(cè)技術(shù)在散列表上形成一個(gè)探測(cè)序列候衍。然后沿著這個(gè)序列查找指定的鍵值對(duì)代表的地址。如果找到了指定的鍵值對(duì)代表的地址洒放，且當(dāng)前地址單元為空蛉鹿，則將此鍵值對(duì)存進(jìn)去。如果當(dāng)前地址內(nèi)有值往湿，則去找一個(gè)地址單元為空的地址妖异，將鍵值對(duì)存進(jìn)去。如果之后的所有地址單元都不為空领追，則再?gòu)念^開(kāi)始找他膳，直到找到一個(gè)空的地址單元，并存入鍵值對(duì)绒窑。
由此可見(jiàn)棕孙，我們的數(shù)組長(zhǎng)度的要大于元素個(gè)數(shù)。這樣才能減少碰撞些膨。
鏈地址法(拉鏈法)
上面的方法是蟀俊，如果有沖突，即發(fā)生了碰撞订雾，就去找其他的地址單元為空的地址肢预。可是洼哎，為什么發(fā)生了碰撞就要離開(kāi)烫映，大家都是那個(gè)值沼本，一起待著不行么？
可以呀锭沟，用鏈地址法擅威。就是用一個(gè)數(shù)組，數(shù)組中的每個(gè)元素都指向一個(gè)鏈表冈钦。每當(dāng)有散列值為該元素的索引的鍵值對(duì)進(jìn)來(lái)郊丛，就將其存入鏈表中。這種方法的思想就是數(shù)組要選的足夠大瞧筛，以保證所有的鏈表要盡可能的短厉熟，以保證高效的查找。HashMap就是用的這個(gè)方法
開(kāi)始分析源碼
好了较幌，了解了那些知識(shí)點(diǎn)后揍瑟，我們從put()方法及其相關(guān)方法下手，源碼如下：
//將指定的值與此映射中的指定鍵相關(guān)聯(lián)乍炉。 如果映射先前包含鍵的映射绢片，則替換舊值。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//計(jì)算key的哈希值
static final int hash(Object key) {
int h;
//混淆hashCode岛琼，減少插入hashMap時(shí)的hash沖突(用高16位于低16位做異或運(yùn)算)
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//該表在首次使用時(shí)初始化底循，并根據(jù)需要調(diào)整大小。 分配時(shí)槐瑞，長(zhǎng)度始終是2的冪熙涤。某些操作中，允許為0
transient Node<K,V>[] table;
//將鏈表轉(zhuǎn)為紅黑樹(shù)的閾值困檩，當(dāng)鏈表節(jié)點(diǎn)個(gè)大于等于TREEIFY_THRESHOLD - 1時(shí)祠挫，會(huì)將該鏈表?yè)Q成紅黑樹(shù)
static final int TREEIFY_THRESHOLD = 8;
//數(shù)組的閾值
int threshold;
//將數(shù)據(jù)填入HashMap中
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//tab：內(nèi)部數(shù)組；p：hash對(duì)應(yīng)的索引位中的第一個(gè)節(jié)點(diǎn)悼沿；n：內(nèi)部數(shù)組的長(zhǎng)度等舔；i：hash對(duì)應(yīng)的索引位
Node<K,V>[] tab; Node<K,V> p; int n, I;
//判斷是否初始化
if ((tab = table) == null || (n = tab.length) == 0)
//tab為初始值，則初始化數(shù)組大小
n = (tab = resize()).length;
//計(jì)算數(shù)組索引糟趾，并判斷該索引下第一個(gè)節(jié)點(diǎn)的元素是否為null
if ((p = tab[i = (n - 1) & hash]) == null)
//如果該索引下第一個(gè)節(jié)點(diǎn)為null慌植，則添加一個(gè)新的節(jié)點(diǎn)
tab[i] = newNode(hash, key, value, null);
else {
//該索引下第一個(gè)節(jié)點(diǎn)不為null
Node<K,V> e; K k;
//判斷該索引下第一個(gè)元素的key值是否與要添加的元素相同
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//相同則將p賦值給e
e = p;
//如果該索引下第一個(gè)元素的key值與要添加的元素不相同，判斷p是不是一個(gè)紅黑樹(shù)結(jié)構(gòu)
else if (p instanceof TreeNode)
//如果p是紅黑樹(shù)結(jié)構(gòu)拉讯，則將要插入的元素添加到數(shù)組里面涤浇，并賦值給e
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//如果p不是紅黑樹(shù)結(jié)構(gòu)鳖藕，則遍歷此索引下的節(jié)點(diǎn)
for (int binCount = 0; ; ++binCount) {
//如果某個(gè)節(jié)點(diǎn)的下個(gè)節(jié)點(diǎn)為null
if ((e = p.next) == null) {
//將新的元素賦予下個(gè)節(jié)點(diǎn)
p.next = newNode(hash, key, value, null);
//如果以遍歷的節(jié)點(diǎn)的個(gè)數(shù)大于等于8-1=7
if (binCount >= TREEIFY_THRESHOLD - 1)
//嘗試將次鏈表轉(zhuǎn)為紅黑樹(shù)
treeifyBin(tab, hash);
//結(jié)束循環(huán)
break;
}
//如果某個(gè)位置的元素跟新元素的key相同
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
//結(jié)束循環(huán)
break;
//將當(dāng)前循環(huán)位置的節(jié)點(diǎn)值賦予p魔慷，并開(kāi)始下次循環(huán)
p = e;
}
}
//如果循環(huán)結(jié)束，且e被賦值
if (e != null) {
//獲取e的value
V oldValue = e.value;
//如果e節(jié)點(diǎn)的value為null或者可以用新值覆蓋舊值
if (!onlyIfAbsent || oldValue == null)
//用新的value覆蓋e節(jié)點(diǎn)的value
e.value = value;
afterNodeAccess(e);
//返回value值
return oldValue;
}
}
//修改次數(shù)加一
++modCount;
//判斷當(dāng)前的數(shù)組長(zhǎng)度是否大于閾值
if (++size > threshold)
//加倍數(shù)組大小
resize();
afterNodeInsertion(evict);
return null;
}
//數(shù)組的最大長(zhǎng)度
static final int MAXIMUM_CAPACITY = 1 << 30;
//最大閾值
public static final int MAX_VALUE = 0x7fffffff;
//默認(rèn)初始容量著恩，必須是2的冪
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4（16）
//初始化或加倍數(shù)組大小
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) {
//如果數(shù)組長(zhǎng)度到達(dá)最大值院尔，則直接返回
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果舊的數(shù)組長(zhǎng)度*2小于最大數(shù)組長(zhǎng)度蜻展，且舊的數(shù)組長(zhǎng)度大于等于默認(rèn)數(shù)組長(zhǎng)度
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//將容量擴(kuò)充一倍
newThr = oldThr << 1;
}
//如果數(shù)組長(zhǎng)度等于0，但是threshold大于0(帶參構(gòu)造設(shè)置)邀摆，則將threshold置為數(shù)組長(zhǎng)度
else if (oldThr > 0)
newCap = oldThr;
else {
//否則纵顾，使用默認(rèn)的數(shù)組長(zhǎng)度及加載因子，并計(jì)算數(shù)組容量
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果數(shù)組容量為0栋盹，可能上面oldThr << 1移除了最高位
if (newThr == 0) {
//重新計(jì)算數(shù)組容量
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//將計(jì)算好的數(shù)組容量賦值給threshold
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//用計(jì)算好數(shù)組長(zhǎng)度新建一個(gè)Node
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//將新建好的Node賦于table
table = newTab;
//如果table之前已被使用
if (oldTab != null) {
//遍歷數(shù)組
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//取出索引下的第一個(gè)節(jié)點(diǎn)施逾，并判斷是否為null
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//如果此鏈表只有一個(gè)節(jié)點(diǎn)，則將此元素存入(要重新計(jì)算索引)
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//如果是紅黑樹(shù)的結(jié)構(gòu)
else if (e instanceof TreeNode)
//調(diào)整大小
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
//loHead例获，loTail為原鏈表的節(jié)點(diǎn)
Node<K,V> loHead = null, loTail = null;
// hiHeadm, hiTail為新鏈表節(jié)點(diǎn)
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//如果此鏈表有多個(gè)節(jié)點(diǎn)汉额，則遍歷節(jié)點(diǎn)
do {
//獲取下個(gè)節(jié)點(diǎn)的元素
next = e.next;
//新增bit為0的節(jié)點(diǎn)，存入原鏈表
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 新增bit為1的節(jié)點(diǎn)榨汤，存入新鏈表
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;
}
//新鏈表存入：原鏈表+索引長(zhǎng)度
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
//單向鏈表結(jié)構(gòu)蠕搜，屬性包括當(dāng)前位置的元素的key和value，及其后面元素位置的指針收壕。還有此位置元素的hash值妓灌。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
// key的hashCode異或value的hashCode
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
//其他的方法
.........
}
//紅黑樹(shù)結(jié)構(gòu)
static final class TreeNode<K,V> extends LinkedHashMap.LinkedHashMapEntry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
//其他方法
.....................
//最小樹(shù)形化的容量，即：當(dāng)內(nèi)部數(shù)組長(zhǎng)度小于64時(shí)蜜宪，不會(huì)將鏈表轉(zhuǎn)化成紅黑樹(shù)虫埂，而是優(yōu)先擴(kuò)充數(shù)組
static final int MIN_TREEIFY_CAPACITY = 64;
//對(duì)于給定的散列unles表，在索引處替換bin中的所有鏈接節(jié)點(diǎn)太小圃验，在這種情況下調(diào)整大小告丢。
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//如果數(shù)組為null或者數(shù)組長(zhǎng)度小于64
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
//擴(kuò)充數(shù)組
resize();
//否則，將鏈表轉(zhuǎn)為紅黑樹(shù)
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);
}
}
然后损谦，再看一下它的remove方法：
public V remove(Object key) {
Node<K,V> e;
//判斷是否有key及其相關(guān)的映射岖免，如果有，則移除并返回
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
// 實(shí)現(xiàn)Map.remove和相關(guān)方法
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
//tab：內(nèi)部數(shù)組 p：某個(gè)節(jié)點(diǎn)值 n：數(shù)組長(zhǎng)度 index：索引位置
Node<K,V>[] tab; Node<K,V> p; int n, index;
//將table的值賦予tab并判斷是否為空照捡，將與key對(duì)應(yīng)的索引位置的第一個(gè)節(jié)點(diǎn)的值賦予p并判斷是否為空颅湘，只要有一個(gè)為空，則放回null
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;
//判斷p的hash值及key與傳入的參數(shù)的hash值和key是否相同
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//相同則將p的值賦予node
node = p;
//不相同栗精，判斷是否有下一個(gè)元素
else if ((e = p.next) != null) {
//有下一個(gè)元素闯参，判斷p是否為紅黑樹(shù)結(jié)構(gòu)
if (p instanceof TreeNode)
//是紅黑樹(shù)結(jié)構(gòu)，則獲取指定節(jié)點(diǎn)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
//鏈表結(jié)構(gòu)悲立，則遍歷鏈表鹿寨，找傳入的key所對(duì)應(yīng)的節(jié)點(diǎn)，找到后將其賦值給node
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
//如果在此處返回薪夕，則noed為p的下一個(gè)節(jié)點(diǎn)(下面做判斷要用)
break;
}
//將e賦值給p
p = e;
} while ((e = e.next) != null);
}
}
//判斷node脚草、value及是否刪除元素
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
//判斷要?jiǎng)h除的節(jié)點(diǎn)是否為紅黑樹(shù)結(jié)構(gòu)
if (node instanceof TreeNode)
//刪除紅黑樹(shù)的node節(jié)點(diǎn)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
//如果node等于p，則node為首節(jié)點(diǎn)原献，那么馏慨，將node的下個(gè)元素置為首節(jié)點(diǎn)埂淮，刪除node
else if (node == p)
tab[index] = node.next;
else
//否則，p和node經(jīng)歷過(guò)循環(huán)写隶，則將p的下個(gè)元素置為node的下個(gè)元素倔撞，刪除node
p.next = node.next;
++modCount;
--size;
//刪除后處理其對(duì)應(yīng)鏈表前后關(guān)系，為L(zhǎng)inkedHashMap留的
afterNodeRemoval(node);
return node;
}
}
return null;
}
上面代碼中的解釋已經(jīng)很清楚了慕趴，就不做其他分析了痪蝇。
好了，現(xiàn)在把上面分析的總結(jié)一下：
1冕房、HashMap是一個(gè)基于拉鏈法實(shí)現(xiàn)的散列表霹俺，內(nèi)部由數(shù)組(用索引確定鍵值對(duì)的位置)、鏈表(存儲(chǔ)hash值毒费、key丙唧、value和下個(gè)節(jié)點(diǎn)的地址)和紅黑樹(shù)實(shí)現(xiàn)。
2觅玻、HashMap中的數(shù)組默認(rèn)的初始容量為16想际，容量的增長(zhǎng)必須以2的次方的方式擴(kuò)容。且要小于1 << 30溪厘。
3胡本、加載因子的默認(rèn)中是0.75。即當(dāng)當(dāng)前數(shù)組內(nèi)的元素的個(gè)數(shù)為數(shù)組容量的0.75畸悬，則數(shù)組就會(huì)被擴(kuò)充侧甫。
4、HashMap中的Node是一個(gè)單鏈表模式的類(lèi)蹋宦。HashMap內(nèi)部數(shù)組中的元素是單鏈表類(lèi)型的披粟。當(dāng)鏈表長(zhǎng)度大于等于7的時(shí)候，單鏈表會(huì)判斷是擴(kuò)容還是轉(zhuǎn)為紅黑樹(shù)冷冗。判斷的依據(jù)是數(shù)組的長(zhǎng)度是否大于64守屉。而當(dāng)鏈表的長(zhǎng)度小于6的時(shí)候，又會(huì)將紅黑樹(shù)轉(zhuǎn)為鏈表(在split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit)蒿辙；方法中體現(xiàn))拇泛。
源碼中的其他細(xì)節(jié)
1、tableSizeFor()方法做了些什么思灌？
我們?cè)倏匆幌逻@個(gè)方法：
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;
}
直接看好像看不出什么俺叭，那我們就給cap賦一個(gè)值，看看在這個(gè)方法中經(jīng)歷了什么泰偿。比如熄守，我們給cap賦值為10,那么10-1=9，9的二進(jìn)制為"0000 0000 0000 1001"。
首先柠横，將它右移一位，在做或運(yùn)算
0000 0000 0000 1001
| 0000 0000 0000 0100
-----------------------
0000 0000 0000 1101
可以看到课兄，我們最高的有效位的右邊被復(fù)制出了一個(gè)1牍氛。接下來(lái)，我們?cè)倮^續(xù)烟阐，將它右移兩位搬俊，再做或運(yùn)算：
0000 0000 0000 1101
| 0000 0000 0000 0011
---------------------
0000 0000 0000 1111
可以看到，現(xiàn)在我們最高位的右邊都變?yōu)?蜒茄。后面還有的右移4唉擂、8和16位，由于我們的數(shù)字比較小檀葛，所以就沒(méi)用了玩祟，也就不分析了。
現(xiàn)在屿聋，我們將這個(gè)數(shù)字加1空扎，那么它就會(huì)進(jìn)位，且后面的低位全部為0润讥。這個(gè)數(shù)就成為2的次方了转锈。所以，經(jīng)過(guò)這樣的運(yùn)算楚殿，我們自己傳進(jìn)來(lái)的數(shù)都會(huì)變?yōu)?的次方撮慨。
2、hashcode是怎么轉(zhuǎn)換為數(shù)組的索引的脆粥？
在我們調(diào)用put方法后砌溺，我們傳進(jìn)來(lái)的key會(huì)進(jìn)入hash方法，我們看一下在hash方法中作了什么操作：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
主要看"(h = key.hashCode()) ^ (h >>> 16)"這一部分变隔。這部分表示key的hashCode即h抚吠，會(huì)右移16位，然后與h做異或運(yùn)算弟胀，得到一個(gè)值楷力。這么做是為了將hashCode進(jìn)一步混淆，以減少hash碰撞孵户。而這個(gè)值就是就是索引值了么萧朝？怎么可能。在putVal()方法中夏哭，還有一步操作：
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
我們主要看判斷語(yǔ)句中的"tab[i = (n - 1) & hash]"检柬。在這里，我們生成的hash值，會(huì)和數(shù)組長(zhǎng)度-1得到的值做一次與運(yùn)算何址。這就是hashcode轉(zhuǎn)索引的過(guò)程里逆。我們具體看一下過(guò)程：
比如我們隨便定義一個(gè)hashcode，看看"(h = key.hashCode()) ^ (h >>> 16)"發(fā)生了什么:
h = hashcode： 1111 1111 1111 1111 1111 0011 1100 1101
k = hashcode>>> 16:
0000 0000 0000 0000 1111 1111 1111 1111
h ^ k:
1111 1111 1111 1111 1111 0011 1100 1101
^ 0000 0000 0000 0000 1111 1111 1111 1111
-------------------------------------------
1111 1111 1111 1111 0000 1100 0011 0010
然后用爪，假如我們有一個(gè)初始容量為16的數(shù)組原押，則根據(jù)"(n - 1) & hash"的到的索引為：
(n - 1) & hash:
0000 0000 0000 0000 0000 0000 0000 1111
1111 1111 1111 1111 0000 1100 0011 0010
---------------------------------------
0000 0000 0000 0000 0000 0000 0000 0010
這個(gè)結(jié)果就是元素的索引。
3偎血、數(shù)組容量為什么一定要是2的次方式增長(zhǎng)诸衔？
通過(guò)上面分析我們發(fā)現(xiàn)，我們?cè)O(shè)置數(shù)組長(zhǎng)度的初始值不管是多少颇玷，最后都會(huì)被轉(zhuǎn)換為2的次方笨农。為什么這么做呢？我們看一下設(shè)置數(shù)組角標(biāo)的代碼"(n - 1) & hash"，n代表數(shù)組長(zhǎng)度，我們只有將數(shù)組長(zhǎng)度設(shè)置為2的次方逃片，n-1的低位才能都是1。這樣诊霹，在與計(jì)算的時(shí)候，才能保證值所生成的hashCode的低位每一位都能被使用渣淳，提高空間的利用率脾还。到這里不理解沒(méi)關(guān)系(其實(shí)是我嘴笨，上面說(shuō)的我自己也覺(jué)得繞)入愧，舉個(gè)反例就明白了(我們只考慮最低的四位)：
假如鄙漏，數(shù)組長(zhǎng)度不是2的次方，比如10棺蛛。那么10-1=9怔蚌。9的二進(jìn)制位1001。那么旁赊，與任何值做與運(yùn)算桦踊，中間的兩位都是0。也就是說(shuō)终畅，他們所代表的值永遠(yuǎn)不會(huì)被使用籍胯。是不是很浪費(fèi)？這就是原因了离福。
好杖狼，到這，這篇文章就結(jié)束了妖爷。休息了蝶涩，要出去浪一會(huì)。
