资料整理自:一个 HashMap 跟面试官扯了半个小时

一、HashMap的内部数据结构

JDK1.8及以上，内部使用数组 + 链表 / 红黑树。

alt

注意：链表长度 > 8 && 数组大小 >= 64为真时，单向链表才转换成红黑树。

二、HashMap的数据插入原理

alt

过程详解：

  1. 判断数组是否为空，为空进行初始化;
  2. 不为空，计算k的hash值，通过(n - 1) & hash计算应当存放在数组中的下标index;
  3. 查看table[index]是否存在数据，没有数据就构造一个Node节点存放在table[index]中；
  4. 存在数据，说明发生了hash冲突, 继续判断key是否相等，相等，用新的value替换原数据(onlyIfAbsent为false)；
  5. 如果不是树型节点，创建普通Node加入链表中；判断链表长度是否大于 8， 大于的话链表转换为红黑树；
  6. 插入完成之后判断当前节点数是否大于阈值，如果大于开始扩容为原数组的二倍。

三、HashMap是怎么设定初始容量大小的？

一般如果new HashMap() 不传值，默认大小是16，负载因子是0.75， 如果自己传入初始大小k，初始化大小为 大于k的 2的整数次方，例如如果传10，大小为16。

（补充说明:实现代码如下）

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，2，4，8，16位，与自己异或，把高位第一个为1的数通过不断右移，把高位为1的后面全变为1，111111 + 1 = 1000000 = （符合大于50并且是2的整数次幂 ）

alt

三、HashMap的哈希函数是怎么设计的？

hash函数是先拿到通过key 的hashcode，是32位的int值，然后让hashcode的高16位和低16位进行异或操作。

alt

高16位和低16位进行异或操作的原因：

  1. 尽可能降低hash碰撞，越分散越好；
  2. 算法一定要尽可能高效，因为这是高频操作，因此采用位运算。

为什么采用高16位和低16位进行异或操作就能降低hash碰撞？能不能直接用key的hashcode？

因为 key.hashCode() 函数调用的是key键值类型自带的哈希函数，返回int型散列值。int值范围为**-2147483648~2147483647**，前后加起来大概40亿的映射空间。只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个40亿长度的数组，内存是放不下的。你想，如果HashMap数组的初始大小才16，用之前需要对数组的长度取模运算，得到的余数才能用来访问数组下标。

源码中模运算就是把散列值和数组长度-1做一个"与"操作，位运算比%运算要快。


bucketIndex = indexFor(hash, table.length);

static int indexFor(int h, int length) {
     return h & (length-1);
}

顺便说一下，这也正好解释了为什么HashMap的数组长度要取2的整数幂。因为这样（数组长度-1）正好相当于一个“低位掩码”。“与”操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。以初始长度16为例，16-1=15。2进制表示是00000000 00000000 00001111。和某散列值做“与”操作如下，结果就是截取了最低的四位值。

  10100101 11000100 00100101
& 00000000 00000000 00001111
----------------------------------
  00000000 00000000 00000101    //高位全部归零，只保留末四位

右位移16位，正好是32bit的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。

结果显示，当HashMap数组长度为512的时候（），也就是用掩码取低9位的时候，在没有扰动函数的情况下，发生了103次碰撞，接近30%。而在使用了扰动函数之后只有92次碰撞。碰撞减少了将近10%。看来扰动函数确实还是有功效的。

另外Java1.8相比1.7做了调整，1.7做了四次移位和四次异或，但明显Java 8觉得扰动做一次就够了，做4次的话，多了可能边际效用也不大，所谓为了效率考虑就改成一次了。

四、HashMap1.8的优化

  1. 数组+链表改成了数组+链表/红黑树;

原因：防止发生hash冲突，链表长度过长，将时间复杂度由O(n)降为O(logn)。

  1. 链表的插入方式从头插法改成了尾插法;

因为头插***使链表发生反转，多线程环境下会产生环。 A线程在插入节点B，B线程也在插入，遇到容量不够开始扩容，重新hash，放置元素，采用头插法，后遍历到的B节点放入了头部，这样形成了环，如下图所示： alt

  1. 扩容的时候1.7需要对原数组中的元素进行重新hash定位在新数组的位置，1.8采用更简单的判断逻辑，位置不变或者索引+旧容量大小。

这是由于扩容是扩大为原数组大小的2倍，用于计算数组位置的掩码仅仅只是高位多了一个1，举个例子：

扩容前长度为16，用于计算 (n-1) & hash 的二进制n - 1为0000 1111，  
扩容后为32后的二进制就高位多了1，============>为0001 1111。

因为是& 运算，1和任何数 & 都是它本身，那就分二种情况，如下图：原数据hashcode高位第4位为0和高位为1的情况；

第四位高位为0，重新hash数值不变，第四位为1，重新hash数值比原来大16（旧数组的容量）

alt

  1. 在插入时，1.7先判断是否需要扩容再插入，1.8先进行插入，插入完成再判断是否需要扩容。

五、HashMap是线程安全的吗？

不是，在多线程环境下，1.7 会产生死循环、数据丢失、数据覆盖的问题，1.8 中会有数据覆盖的问题。

以1.8为例，当A线程执行到下面代码第6行判断index位置为空后正好挂起，B线程开始执行第7 行，往index位置的写入节点数据，这时A线程恢复现场，执行赋值操作，就把A线程的数据给覆盖了；

六、怎么解决HashMap线程不安全的问题？

ava中有HashTable、Collections.synchronizedMap、以及ConcurrentHashMap可以实现线程安全的Map。

  1. HashTable是直接在操作方法上加synchronized关键字，锁住整个数组，粒度比较大；
  2. Collections.synchronizedMap是使用Collections集合工具的内部类，通过传入Map封装出一个SynchronizedMap对象，内部定义了一个对象锁，方法内通过对象锁实现；
  3. ConcurrentHashMap使用分段锁，降低了锁粒度，让并发度大大提高。

ConcurrentHashMap的分段锁的实现原理

ConcurrentHashMap成员变量使用volatile 修饰，免除了指令重排序，同时保证内存可见性，另外使用CAS操作和synchronized结合实现赋值操作，多线程操作只会锁住当前操作索引的节点。

如下图，线程A锁住A节点所在链表，线程B锁住B节点所在链表，操作互不干涉。

alt

为什么链表转红黑树的阈值是8，红黑树转链表的阈值是6？ 因为经过计算，在hash函数设计合理的情况下，发生hash碰撞8次的几率为百万分之6，概率说话。。因为8够用了，至于为什么转回来是6，因为如果hash碰撞次数在8附近徘徊，会一直发生链表和红黑树的转化，为了预防这种情况的发生。