1. Map实现类结构
2. HashMap底层数据结构
2.1HashMap数据结构
JDK1.8之前Map.Entry[]数组+链表结构，链表插入使用头插法。
JDK1.8之后Node[]数组+链表+红黑树，链表插入采用尾插法。
2.2 HashMap存储过程
put方法执行流程：
- 调用put方法，put方法调用putVal方法。
- 如果为第一次调用put方法，就会首先创建一个长度为16的Node数组。
- 获取key的hash值，根据hash值和数组长度进行某种算法求出应该存储在数组的那个下标。
- 定位到数组的索引位置，如果索引位置为空，直接创建Node节点插入
- 如果索引位置不为空，遍历链表，根据hash值进行判断。如果hash值一样就进行value的更新
- 如果hash值都不一样，如果此链表的长度小于8，就直接在链表尾部插入
- 如果链表长度大于等于8，但是Node数组的长度小于64，就进行数组的扩容
- 如果链表长度大于等于8，并且Node数组的长度大于等于64，就会把链表存储结构变为红黑树的存储结构。
3. 源码分析
3.1 HashMap参数分析
3.1.1 DEFAULT_INITIAL_CAPACITY
默认的Node数组的初始化长度为16。1 << 4 = 2^4 = 16
可以通过new HashMap(int initialCapacity);的方式新建map对象。注意initialCapacity必须为2的次方。如果参数不是2的次方，后续tableSizeFor方法会强制转换为2的次方。 /**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /**
* Returns a power of two size for the given target capacity.
*/
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;
}tableSizeFor执行过程：
假设设置的初始容量为 11
- int n = cap - 1;
此时 n = 10
n |= n >>> 1;
n = 10(十进制)=00000000 00000000 00000000 00001010(二进制)
n >>> 1 无符号右移一位变为 00000000 00000000 00000000 00000101
进行和n或操作
00000000 00000000 00000000 00000101
00000000 00000000 00000000 00001010
---------------------------------------------------------------------------------------------
00000000 00000000 00000000 00001111 => 15
- n |= n >>> 2;
此时 n = 15(十进制) = 00000000 00000000 00000000 00001111(二进制)
n >>> 2 无符号右移2位变为 00000000 00000000 00000000 00000011
进行和n或操作
00000000 00000000 00000000 00001111
00000000 00000000 00000000 00000011
-----------------------------------------------------------------------------------
00000000 00000000 00000000 00001111 => 15
- n |= n >>> 4;
此时 n = 15(十进制) = 00000000 00000000 00000000 00001111(二进制)
n >>> 4 无符号右移2位变为 00000000 00000000 00000000 00000000
进行和n或操作
00000000 00000000 00000000 00001111
00000000 00000000 00000000 00000000
------------------------------------------------------------------------------------
00000000 00000000 00000000 00001111 => 15
- n |= n >>> 8;
- n |= n >>> 16;
上面两次操作结果一样，此时 n = 15(十进制) = 00000000 00000000 00000000 00001111(二进制)
- return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
经过判断，n+1 = 16 = 2^4 此时设置的初始容量11就会变成16.
tableSizeFor方法会把设置的初始容量改成距离参数值最近的2的次方。比如1会变为2，3会变为4，11变为16，19变为32等等
思考1：tableSizeFor方法为什么首先进行 cap - 1操作？
答： cap - 1操作为了防止初始容量刚好为2的次方时，会继续进行高位赋值1。例如cap设置为16时，如果不进行 cap - 1，执行完会返回cap为32，就不符合要求了。
思考2：为什么初始化容量必须设置为2的次幂？
答：通过设置为2的次幂，可以时Hash值能够均匀的分布在数组中。具体如图所示：
3.1.2 DEFAULT_LOAD_FACTOR
加载因子：表示数据存储的稀疏程度。默认值为0.75 在创建HashMap时可以设置，但是一般不建议修改。
加载因子一般作为数组扩容的标准之一，一般数组存储数量达到数组容量*加载因子时就会进行数组扩容，扩大为2倍。比如默认初始容量为16，加载因子为0.75，所以桶用到了12个时，会进行数组的扩容。
加载因子过大就会导致每个数组的链表或者红黑树节点较多，查询效率变低，
加载因为过小就会导致数组的利用率比较低，浪费空间。
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;3.1.3 MAXIMUM_CAPACITY
数组容量最大值，最大值为2^30
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;3.1.4 TREEIFY_THRESHOLD
链表节点数量达到多少时进行链表转换为红黑树。默认值为8，但是当链表节点数量达到8时，并不是立即进行转换，首先进行判断数组的长度是否达到64，如果长度没有达到64，会首先进行数组扩容。如果达到64，就会进行转化红黑树。
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;思考：为什么达到8才进行红黑树的转换？
源码作者注释：
* Because TreeNodes are about twice the size of regular nodes, we
* use them only when bins contain enough nodes to warrant use
* (see TREEIFY_THRESHOLD). And when they become too small (due to
* removal or resizing) they are converted back to plain bins. In
* usages with well-distributed user hashCodes, tree bins are
* rarely used. Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million因为红黑树节点的大小大约是常规节点的两倍，所以我们只在bin包含足够的节点以保证使用时才使用它们（请参见TREEIFY THRESHOLD）。当它们变得太小时（由于移除或调整大小），它们会被转换回普通的垃圾箱。在使用分布良好的用户hashcode时，很少使用树bin。理想情况下，在随机哈希码下，箱中节点的频率服从泊松分布(http://en.wikipedia.org/wiki/Poisson\u分布)参数平均约为0.5，默认的调整阈值为0.75，但由于调整粒度的原因差异较大。忽略方差，列表大小k的预期出现次数为（exp（-0.5）*pow（0.5，k）/阶乘（k））。第一个值是：
3.1.4 UNTREEIFY_THRESHOLD
当红黑树的节点少于此值时，进行转换为链表。默认值为6，当红黑树节点少于6时，会把红黑树转变为链表。
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;3.1.5 MIN_TREEIFY_CAPACITY
链表转换为红黑树的最小数组容量。默认值为64，当数组容量小于64时，链表节点过多会进行扩容，不进行结构变化。
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;3.2 构造方法
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}3.3 put方法源码解析
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}- 首先利用hash方法获取key的Hash值，首先判断是否为空，如果为空，哈希值就为0，就是为什么HashMap允许key为空，但是只能存在一个null。如果不为空，就会把key的哈希值（32bit）无符号右移16bit，然后和key的哈希值进行异或运算，结果作为key的返回值。运算过程如图
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}思考：为什么不直接返回哈希值，而是使用(h = key.hashCode()) ^ (h >>> 16)的方式获取哈希值？
答：在putVal方法中，会通过i = (n - 1) & hash (n：数组的容量，hash表示返回的hash值)的方式获取key需要放入数组的下标。如果当数组的容量很小时，使用直接返回的哈希值进行与容量进行与操作时，只利用了哈希值的低位。如果哈希值的高位变化很大，低位一样，就会导致很多的hash分布不均匀。经过上述16bit右移，可以充分利用哈希值的高位和低位部分，hash分布更加均匀。图解：
- 调用 putVal(hash(key), key, value, false, true);
- 如果第一次调用put方法会调用resize()方法进行创建HashMap数组。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;- resize（）方法主要为了创建Node数组，并且把threshold从数组容量改为（数组容量*加载因子）
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; //oldTab = table = null
int oldCap = (oldTab == null) ? 0 : oldTab.length; //oldCap = 0
int oldThr = threshold; //oldThr = threshold = 16
int newCap, newThr = 0; //newCap = newThr = 0
if (oldCap > 0) {
......
}
else if (oldThr > 0)
newCap = oldThr; //newCap = oldThr = 16
else {
..........
}
if (newThr == 0) { //true
float ft = (float)newCap * loadFactor; //默认值为 ft = 16*0.75 = 12
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE); //newThr = 12
}
threshold = newThr; //threshold = 12 即当数组的使用达到12时开始进行扩容
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //此时开始创建一个容量为16的Node数组
table = newTab; //赋值给table
if (oldTab != null) {
.........
}
return newTab; //返回Node数组
}- 根据hash值进行获取Node数组的下标索引值，然后根据下标索引上是否存在节点，如果不存在节点则直接创建节点，插入节点。
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
......
++modCount; // 记录map插入操作计数，更新不会计数
if (++size > threshold) //size 记录map中键值对的个数。
resize();newNode内进行的操作：链表尾插法
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}- 如果索引位置上存在节点，遍历节点，根据哈希值进行判断key是否存在map中，如果哈希值相同，并且key相同，就进行数值的更新操作。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}- 判断节点的类型，是否是treeNode节点，如果时treeNode节点，就放入红黑树中
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);- 如果不是红黑树结构，和链表头节点的哈希值也不相同，就会从头节点遍历链表，如果遍历完链表没有找到相同的哈希值，就会创建节点，插入链表尾部。如果遍历中存在相同哈希值，如果key相同，中止遍历，更新数值。
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}3.4 扩容机制
扩容会把容量变为原来的2倍。然后对原来的节点进行重新的分布。扩容后的节点分布不会和一开始put那么复杂，节点中都保存了key处理后的hash值。通过hash&(n-1) n为新扩容的容量大小，就能求出新的索引，一般为原索引位置或者原索引位置+原来数组的容量。
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
............
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;
}