前言
对于初级和中级程序员来说，Java的Api是必须迈过的一个“坎”，许多程序员在对业务代码麻木后就会对代码的实现原理进行理解，而Java的Api中HashMap、ConcurrentHashMap可能是大家使用最为频繁且面试最容易问到数据结构，本文不会对HashMap、ConcurrentHashMap源码进行逐行的解析，只是会对其中我感觉比较重要的点进行总结（建议对HashMap、ConcurrentHashMap数据结构有基本了解后再读下面章节的内容），通过对比JDK7 、JDK8中的HashMap和ConcurrentHashMap，让大家对其原理有一个深入的理解。
一、JDK7中的HashMap
1.HashMap中槽的默认大小（数组长度）为什么要始终保持2的N次方?
-
性能：HashMap在进行元素的put操作时，要通过key的hash值定位对应的槽位，正常的操作一般都是hash%length，但“与”操作与“模”操作相比性能要高，所以Api采用了hash&（length-1）的方式，这么做的一个前提就是length为2的N次方。
hash=11 length=5： hash%length=11%5=1 hash&（length-1）=11&4=0
hash=11 length=4： hash%length=11%4=3 hash&（length-1）=11&3=3 -
目标： 为了保持分布均匀而较少碰撞，如果length为2的N次方，那么length-1在二进制上后面的位都为1，这样与hash进行运算会尽量多产生出结果，减少碰撞。
length=9：hash&（length-1）=11&8=8 hash%length=15%8=8 ->产生碰撞
length=8：hash&（length-1）=11&7=3 hash%length=15%7=7 ->避免碰撞
2.为什么计算完hashcode要再进行一次hash计算？
- hashcode：计算规则为s[0]*31^(n-1)+s[1]*31^(n-2)+...+s[n-1]，其中的31为奇数数，能够保证31*i=（i<<5）-i
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;
}
- hash：好多人给这一次哈希操作叫做“扰动函数”，hashCode返回的是Int的散列值，如果我们槽的数量比较少且是2的N次方，那反应到二进制上前几位都为0，后几位都为1（或高位值不同低位值相同），碰撞也会很严重，该算法将二进制的高半区与低半区进行了异或操作，来加大二进制低位取值的随机性，将高低位的值反应到哈希值上，从而来减少碰撞。
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
3.什么是HashMap中的Fail-Fast机制？
在HashMap中有一个变量为modCount，它的类型为volatile，每次对HashMap进行修改都要修改该值，我们都知道HashMap线程不安全，该变量的作用就是确定在该线程感知其他线程是否对HashMap进行了修改，如果发现了则抛出异常，这个过程简称Fail-Fast，如我再遍历HashMap所有的key与value，其他线程对HashMap进行了修改，当我判断该值与之前取值不同时，则抛出异常。
4.HashMap在插入和扩容时有什么特点？
- 在插入时，若key为null，则插入到槽位0处，如插入的Entry存在哈希冲突，将新Entry值放到槽位，作为冲突链表的头jiedian。
- 在扩容时，我们从原链表的头结点开始逐一遍历，遍历到每一个Entry时就放到扩容的HashMap冲突链表的头结点。
5.为什么HashMap线程不安全?
- 在put时引起数据不一致：若线程1执行完了下方代码的（1）操作后被挂起，线程2开始执行，线程2完成了哈希冲突的put操作，在指定的槽位置插入了新的元素，线程1中e指向的元素成为了链表头的next结点，这时线程1继续执行（2）操作，就会使槽位的元素设置为线程1要设置的元素值，刷新了线程2中设置的链表头结点，从而造成了数据的不一致。
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex]; (1)
table[bucketIndex] = new Entry<>(hash, key, value, e); (2)
size++;
}
-
在resize时引起死循环（CPU100%）：若线程1进行扩容执行下方代码的（1）的操作后线程挂起，线程2同样也执行扩容，并完成了全部的扩容操作（假设扩容后的结点依旧在同一个槽位），由于JDK7中哈希冲突的链表采用的是“头插法“，所以切换回线程1继续执行剩下的步骤，会出现Entry之间的循环引用，在get操作时会造成死循环，并吃掉所有CPU资源，具体流程见下图。
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next; (1)
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i]; (2)
newTable[i] = e; (3)
e = next; (4)
}
}
}
二、JDK7中的ConcurrentHashMap
1.ConcurrentHashMap数据结构，为什么他是线程安全的？
-
数据结构：在ConcurrentHashMap中外层是由segment组成的segment数组，每个segment中存在一个HashEntry数组（Segment类中有成员变量 HashEntry<K,V>[] table），如果key发生冲突，与HashMap一样会形成HashEntry链表结构，从大到小的数据结构为ConcurrentHashMap->segment->HashEntry，在网上找到的ConcurrentHashMap数据结构的示意图如下。
线程安全：由于ConcurrentHashMap数据结构中存在Segment，采用的是“分段锁”的机制保证了ConcurrentHashMap的线程安全。Segment继承ReentrantLock，相当于每个Segment都掌握一把锁，在并发操作时，只锁对应的Segment，而不会影响其他Segment的操作，但这也不代表整个ConcurrentHashMap不会上锁，ConcurrentHashMap的size()等方法在某些条件下会锁整个数据结构，在并发时候应用UNSAFE类实现了可见性，UNSAFE类相当于可以直接操作内存数据。
2.在ConcurrentHashMap中如何确定段（Segment）数和每段数组的大小等参数？
- 初始容量：ConcurrentHashMap默认大小为16，最大大小230，负载因子默认0.75，默认并发数（段数）16，最大分段数216，每段的最小容量为2。
- 如何确定：首先根据并发数concurrencyLevel确定段数，段数为最靠近concurrencyLevel2的N次方（向上取）的数，如concurrencyLevel为15，那段数就应该为16，其次根据初始容量initialCapacity确定每段的数组大小，数组的大小为初始容量除以段数后最靠近2的N次方（向上取）的数，若初始容量为100，每段数组的大小应该为8（100/16=6，最后取8）。
public ConcurrentHashMap(int initialCapacity,float loadFactor,int concurrencyLevel)
- 确定segment索引：在如何确定参数大小时，构造函数中通过sshift、ssize计算出了参数的大小，segment索引的计算也是应用这两个参数，具体的换算见下方，大体来说就是hash值的高sshift位于ssize-1（段数的掩码）进行与运算，若不存在则参照segment[0]创建一个新的，确定了segment索引后，还要定位HashEntry数组的索引，这个方法与HashMap一致。
int j = (hash >>> segmentShift) & segmentMask;
= (hash >>> (32-sshift))&(ssize-1)
3.ConcurrentHashMap的各种操作在获取锁时有什么优化？
- put：在获取分段锁的时候，如果没获取到锁，ConcurrentHashMap不会阻塞，而是做了一定的优化，总体来说可以是做了几次锁的自旋操作，在自旋中若没有获得锁，会遍历HashEntry数组来找到需要put的位置，并实例化目标HashEntry，如其他线程修改了HashEntry数组还需要重新来进行定位，当获取锁超过了设定的自旋的次数则会阻塞（默认自旋转2次）。
- resize：扩容只针对每一个Segment进行扩容，基本思想与HashMap相同，对老Table进行遍历，然后移动到新Table中，在其中会先找到一个子链表（该链表的所有结点均能定位到新槽位，且包含老Table中的最后一个结点），然后再遍历其他的结点，采用“头插”发插入到新Table中。
- size：利用每个segment的size方法获得总数，连续获得两次总数，若两次相同则认为是最终结果，若不是则锁整个ConcurrentHashMap进行统计。
三、JDK8中的HashMap
1.JDK8中的HashMap数据结构有什么优化嘛？
数据结构在用了数组+链表+红黑树的数据结构，主要解决了链表过长查询的效率问题。当冲突少的时候使用的是链表来解决冲突，当冲突结点值大于TREEIFY_THRESHOLD值（默认为8）后，会将链表树化（红黑树），当然这个前前提是HashMap的容量要大于64，如果容量小于64（MIN_TREEIFY_CAPACITY默认值）则会先扩容而不是树化。
2.初始化HashMap容量大小时是否进行了优化？
是的，JDK7中采用的是不断移位-比较的算法，JDK8中采用的是移位-异或算法，不断的将1从高位刷新到低位（指数移位），最终得到最接近2的N次方的数，之所以最开始减1后面加1是为了考虑n本身就为2的N次方的情况，这种情况如果不减1的话，最终的结果为N的二倍，总体来说该算法主要是为了提升计算HashMap容量初始值的效率问题。
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;
}
3.两次Hash算法是否进行了优化？
是的，并没有JDK7那么复杂，简化了流程，高位与地位进行与运算，让高位也参加到运算中，减少发生冲突的概率。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
4.是否了解在冲突时的树化和链化？
-
树化：当链表的长度超过限定的值时，会将链表转换成红合树，在转换的过程中首先是先将Node结点转换为TreeNode，TreeNode中依然保留了原链表的顺序（指针），主要的目的是简化链化的操作，然后，遍历所有链表的结点，通过对比hash的值，构造一颗红黑树。
在比较结点的大小时先比较hash值的大小，若相同通过Comparable接口的方法进行比较，若还不能确定大小则使用下方的“加时赛”算法确定，底层调用的Native方法进行比较。
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
- 链化：按照NodeTree结点中的原来链表的顺序构造链表即可，该方法主要发生在扩容resize()后和删除removeNode()操作。
static final class TreeNode<K,V> extends LinkedHashMap.Entry<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;
}
5.resize()方法是否进行了优化？
在JDK8中的resize()方法根据冲突的数据结构进行扩充，如果当前为链表则采用链表的扩容算法，若当前为红黑树则采用红黑树的扩容方法。扩容还是以二倍的方式进行扩容（一定要注意扩容永远是针对槽位而言，也就是HashMap数据结构中的数组）。
-
链表：假设老HashMap的容量为8，现对其中一个槽位的链表进行扩容，扩容后能够保证原插入顺序（而不是像JDK7一样使用链表的头插法）， 其中优化了确定在新旧槽位的算法，新槽位的索引是原索引加上老HashMap的容量值，具体的计算过程如下。
扩容前：
扩容后如何判断槽位：
扩容后判断结点处于新槽位还是旧槽位：
-
红黑树：在API中红黑树拆分的方法名为split，但其实并不复杂，因为TreeNode存有链表的顺序，所以按照链表的顺序遍历红黑树，将其拆分成2个小链表，然后根据链表的长度来决定是否将小链表转换为红黑树即可，之后如有插入红黑树的操作也始终维护该链表结构。
6.为什么HashMap的数组使用transient修饰符修饰？
首先我们要了解transient修饰符的意义，用transient关键字标记的成员变量不参与序列化过程，HashMap之所以这么设计是因为它本身实现了反序列化方法（readObject、writeObject），这样的做法有两个好吃，一方面，HashMap的数组可能并不是所有的槽位都存储满，所以在一定程度上节约了空间，另一方面，因为Object类的hashCode方法是一个native方法，在不同的JVM下所产生的结果可能不一样，不一样的值会导致结点不在原本的槽的位置。
四、JDK8中的ConcurrentHashMap
1.JDK8中的ConcurrentHashMap数据结构是否有改变？
是的，在JDK8中摒弃了原有的Segment的概念，而是直接采用数组+链表+红黑树+锁的数据结构。
2.ConcurrentHashMap如何初始化容量，如何计算hash值？
在之前三章的数据结构中都是根据初始化值找到大于该值，且最接近2的N次方的数组，而在该算法中不再这样，即使initialCapacity为2的N次方，那最后的容量也是initialCapacity的2倍，之所以这么考虑我想应该是尽可能的多申请一些空间，减少扩容和锁带来的性能问题。
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
在计算hash方面，与JDK8的HashMap很相似，但是唯一不同的是多了一步与操作 & HASH_BITS（0x7fffffff），主要的目的是确保最后的值是正数，在插入操作中也是用hash值的正负来判断是链表节点还是树节点。
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}
3.ConcurrentHashMap如何初始化容量在扩容时与之前有什么差别？
当槽位的冲突的元素的个数超过8（TREEIFY_THRESHOLD）个时，会将链表转成红黑树，但如果当前的ConcurrentHashMap数组大小小于64（MIN_TREEIFY_CAPACITY）时，则不会转成红黑树，会优先考虑对数组的大小进行扩容（tryPresize方法）。
java.util.concurrent.ConcurrentHashMap#treeifyBin
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
tryPresize(n << 1);
ConcurrentHashMap的扩容不是仅仅2倍的扩容，而是2的N次方倍，如当前数组的长度为16，那执行扩容方法tryPresize时参数为32，在方法中会确认最终的扩容大小，根据下方的算法可以确认扩容后的大小为64，tryPresize方法没有加锁，多线程环境下执行，当前线程会帮助去扩容。
java.util.concurrent.ConcurrentHashMap#tryPresize
int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
tableSizeFor(size + (size >>> 1) + 1);
4.ConcurrentHashMap如何在多线程下进行扩容并保证线程安全？
在JDK8的ConcurrentHashMap中，有一个ForwardingNode的数据结构，如果该槽位已经完成扩容会将Node节点替换为ForwardingNode节点，其它线程如果发现该槽位没有完成扩容会帮助其进行扩容，若发现已经完成扩容则不会再进行扩容。
扩容的核心方法为transfer，第一个进行扩容的线程会创建2倍的数组容量来进行扩容。扩容的大体的过程是，每个线程在transfer都会领取任务，任务会说说明该线程需要迁移的节点的范围，剩下的就是很多的判断，如是否全部槽位已经完成扩容、一个槽位是否已经完成扩容，在扩容的时候与HashMap类似，对对应的槽位上锁以后，则进行扩容，如果为链表则拆分为两个链表，如果为红黑树则拆分为两个红黑树，若红黑树的节点数小于8则再转化为链表。
