提起Map想必大家都不陌生，用的最多的比如：HashMap、TreeMap、ConconrentHashMap等等，本文主要介绍HashMap底层的一点东西，说的不全，后续会继续补充。。。
你懂得越多，你不懂的越多
简介
HashMap在java.util包下，是AbstractMap的字类，属于非线程安全的集合，HashMap的源码相信很多人都看过，我再稍微总结下，做个笔记，以便后续复习，
先介绍下HashMap类的几个变量：
-
DEFAULT_LOAD_FACTOR = 0.75f：默认装载因子（0.75） -
EFAULT_INITIAL_CAPACITY = 1 << 4：默认初始容量（16） -
MAXIMUM_CAPACITY = 1 << 30：最大容量（2^30）
接下来通过一个例子一步步介绍它底层的一些逻辑，首先是构造方法，HashMap提供了4中构造方法：
//四种构造方法
public HashMap(int initialCapacity, float loadFactor)
public HashMap(int initialCapacity)
public HashMap()
public HashMap(Map<? extends K, ? extends V> m)
具体的实现这里不多说了，重点是前三种构造方法，虽然有初始容量和负载因子，但是方法内部都没有去初始化一个table。具体什么时候回初始化，下边会介绍到。
扰动函数
介绍扰动函数之前，我们先看下HashMap的put()方法，可以看到在put方法里边还有一个putVal()方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
然后在这个方法里有个hash(key)，这个函数即被称为扰动函数（到底是什么的扰动，下边再说），源码如下：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
方法的实现非常简单，首先获取key的hashCode（就是最底层的hashCode()），然后将hashCode右移16位，之后两者异或。先说下这样做的好处是可以让hashCode的高低位都参与到index（数据在map中的位置）的计算中，具体原因下边再说。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0) //1
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) //2
tab[i] = newNode(hash, key, value, null);
else {
......
进到putVal()方法的内部，我们只看前半部分，后边的扩容逻辑暂时不看，注意注释位置
-
1、首先判断
table是不是空，如果是空则resize()初始化，上边说的构造函数未初始化的table，就是在这初始化的，这块有点像懒加载，用到的时候才创建 -
2、计算一个位置（index），看这个位置是否为空，如果为空则新建一个节点，可以看到计算方式为
(n - 1) & hash，这里的n指的是table的长度，hash其实就是上边扰动函数算出的hash值（高低16位异或那个），这个地方还牵扯到另一个点就是为什么table的容量必须是2的n次幂，即便初始化的时候构造参数不是2的n次幂，hashmap内部也会转成2的n次幂大小（就是下边这个方法）。
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;
}
这里就是通过一系列的右移+位或操作，因为或操作只要有一个1结果就是1，这样就可以将位都变成1，比如10二进制为1010，右移1位为0101，位或结果为1111，之后再右移、或操作结果都是1111，对应十进制为15，最后得到n+1=16。为什么一定要转为2的n次幂，往下看。
2的n次幂
这里之所以把2的n次幂作为一个模块，是因为之前一直没搞懂这块（异或、与操作啥的，乱七八糟），所以打算着重记录下，这里主要介绍两个方面：一是为什么集合容量一定是2的n次幂；其次是这块和扰动函数之间的关系。
我们知道，hash函数主要关注的无非两点（分布均匀和较低的碰撞率），其实只需要关注碰撞率就好。碰撞率低数据分布自然均匀，这里的2的n次幂和扰动函数就是实现低碰撞率的，具体怎么实现呢，往下看：
我们假设容量n=2^4=16，那么n-1=15用二进制标识就是01111，下面列举4个随机数与01111与操作。
alt
可以发现结果都不同，很好的避免了hash碰撞。
如果容量不是2的n次幂，假如容量n=10,那么n-1=9，用二进制表示为01001，同样对4个数进行与操作，很明显有3个结果是重复的，说明碰撞率很高。
alt
到这里我们知道了为什么容量一定是2的n次幂，那扰动函数起什么作用呢？上边说到扰动函数是将hashCode 的高低16位进行异或操作，为的是让高低位都可以参与到index的计算中，我们还是举个例子说明：
假设容量n=16，n-1=15二进制是01111，hash=....1010 0000 0110 0110，我们知道0与任何数都是0，那么hash&(n-1)=(....1010 0000 0110 0110) & (01111)=.......0110，这里的结果省略了前边的一堆0，可以看到结果就是hash的后四位（0110）。
那么如果不使用扰动函数，直接hashCode & (n-1)，这样的话如果两个数的hashCode的后四位一样，比如.....0101 0110
和......0110 0110，计算出的结果都是0110，碰撞率很高，所以相比于直接使用hashCode，扰动函数计算出的hash值，hash结果就没那么碰巧。
讲到这里，我们应该知道为什么容量取2的n次幂和引入扰动函数，其实两者是结合使用的，都是为了减小碰撞率。
至此，我们大致了解了HashMap的为避免hash碰撞的做法和逻辑，下边我们分析下发生hash碰撞后HashMap做了什么？
putVal(）后半段（hash碰撞解决过程）
我们接着看putVal()方法，看下半部分的逻辑
else { //发生了碰撞
Node<K,V> e; K k;
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k)))) //1、相同key，直接覆盖
e = p;
else if (p instanceof TreeNode) //2、是否是红黑树的节点
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) { //3、尾插法插入元素
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) //3-1 、判断链表长度是否大于默认值8
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) //3-2、链表中是否有相同的key
break;
p = e;
}
}
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
这段主要是发生hash碰撞后的处理流程，根据注释位置，大致介绍下：
-
1、这里的p指的是上边根据
(n-1) & hash算出的位置所对应的值，如果key和hash值相同，说明是同一个key，直接覆盖 -
2、判断是否是
红黑树的节点，如果是则直接put，红黑树相关操作后续再说。 -
3、不是相同的key，且不是红黑树节点，走正常的添加逻辑，也就是尾插法将元素放到最后一个位置，在这中间有两个判断，
- 3-1、判断链表的长度是否大于临界值
8，如果大于则进入一个叫treeifyBin(tab, hash)的方法，这个方法在这就不细说了，主要做了两件事：如果整个table的长度小于64只进行resize()扩容，否则如果长度大于64则将当前链表结构转为红黑树。 - 3-2、 在尾插法遍历过程中，如果发现有相同的Key，直接break跳出循环。
- 3-1、判断链表的长度是否大于临界值
至此，我们已经了解了HashMap的put大致流程，接下来看下HashMap的扩容机制。
扩容机制 resize()
我们知道，当table的长度大于64并且某一链表的长度大于8的时候，会触发扩容，也就是resize()，先看源码
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) {
if (oldCap >= MAXIMUM_CAPACITY) { //1、如果原始table的长度大于最大值（2^30），将临界值设为int的最大值
threshold = Integer.MAX_VALUE;
return oldTab;
}
//2、如果老数组长度的2倍<最大容量 && 老数组的长度>默认容量，将新的临界值设为原始临界值的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; //3、到此为止，计算出了新的capcity（容量）和threshold（临界值）
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) { //4、遍历老数组，复制元素到新数组
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null) //5、如果链表只有一个节点，直接放到 hash & (newCap - 1) 位置
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode) //6、如果是红黑树节点，走红黑树扩容逻辑
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { //7、链表扩容逻辑（重点，下边细说）
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) { //7-1、判断元素在新数组中的位置是否需要改变
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else { // 8、需要改变位置的链表尾插逻辑
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; //9、需要改变位置的链表放到table中的新位置
}
}
}
}
}
return newTab;
}
以上就是rezise()扩容机制的详细流程，下边重点说下普通链表的扩容逻辑（注释7），首先判断的是元素在新数组的位置是否需要改变，判断公式为e.hash & oldCap，注意不是hash & (oldCap-1)，下边举几个个例子说明下，假设初始容量是oldCap=16（0001 0000)，扩容后容量为newCap=32（0010 0000）。
1、 假设e.hash=10（0000 1010），那么e.hash & oldCap = 10(0000 1010) & 32(0010 0000)=0(0000 0000)，结论是扩容后不需要变更位置,，我们验证下：
-
扩容之前的index=e.hash & (oldCap-1)=10(0000 1010) & 15(0000 1111) = 10(0000 1010)
-
扩容后index=e.hash & (newCap)=10(0000 1010) & 31(0001 1111) = 10(0000 1010)，扩容后位置不变
2、假设e.hash=17（0001 0001），则e.hash & oldCap = 17(0001 0001) & 16(0001 0000)=16(0001 0000)，结论是扩容后需要变动位置，解释如下：
-
扩容之前的index=e.hash & (oldCap-1)=17(0001 0001) & 15(0000 1111) = 1(0000 0001)
-
扩容后index=e.hash & (newCap)=17(0001 0001) & 31(0001 1111) = 17(0001 0001)，扩容后的位置变了
注释8意思是：如果改变链表头结点在table中的位置，则新建一个链表，再把新链表的头结点放到table中的新位置，对应注释9位置代码。可以发现新链表的头结点在table中的位置是newTab[j+oldCap]，其实就是原始位置索引加上原始长度，这也对应了上边说的hash=17在原始table中的位置是1，rehash后在新table中的位置是17（1+16）。
拓展
说到扩容就不得不提一下jdk1.7中在多线程下扩容形成死链的问题，在jdk1.7中扩容使用的是头插法，核心代码如下：
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
//这个while循环是我们问题的关键
while(null != e) {
Entry<K,V> next = e.next; //t1、线程1执行到此处
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity); //重新计算位置
e.next = newTable[i]; //头插法插入当前元素
newTable[i] = e;
e = next;
}
}
}
首先我们了解下头插法：
假设有3个元素，
1、插入元素a，此时e指向a，next指向b
2、插入b，此时e指向b，next指向c:
3、插入c:
1
2
3
死链的产生：当两个线程都执行扩容方法时，假设线程1执行到代码注释t1处（此时e指向的是a），此时线程2来了，重新执行了扩容并将table更新为newTab，这时线程1来了，对于线程1来说，由于e指向的是a，然后执行代码e.next = newTable[i]，e.next指向了链表的头结点（也就是c）,然后又执行newTable[i] = e后将头结点赋为a，此时的结构就像下图这样
alt
在jdk1.8中采用尾插法避免了死链的问题，但是这并不意味着在jdk1.8中可以在并发场景下使用HashMap，因为它内部并没有集成锁机制，多线程下仍然存在数据不一致的情况。至此，我们大致了解了HashMap的扩容机制以及jdk1.7中的死链相关问题。
小结
此篇文章大概介绍了HashMap中的几个关注点：扰动函数、table长度为什么是2的n次幂、hash碰撞解决、扩容机制（resize）以及jdk1.7死链问题。至于扩容引入的关于红黑树相关知识，后期打算单独拉一个模块来详细介绍下，这里就不多说了。
网友评论