HashMap源码分析

源码分析

HashMap中的主要参数 = 容量、加载因子、扩容阈值

// 1. 容量（capacity）： HashMap中数组的长度
// a. 容量范围：必须是2的幂 & <最大容量（2的30次方）
// b. 初始容量 = 哈希表创建时的容量
  // 默认容量 = 16 = 1<<4 = 00001中的1向左移4位 = 10000 = 十进制的2^4=16
  static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
  // 最大容量 =  2的30次方（若传入的容量过大，将被最大值替换）
  static final int MAXIMUM_CAPACITY = 1 << 30;

// 2. 加载因子(Load factor)：HashMap在其容量自动增加前可达到多满的一种尺度
// a. 加载因子越大、填满的元素越多 = 空间利用率高、但冲突的机会加大、查找效率变低（因为链表变长了）
// b. 加载因子越小、填满的元素越少 = 空间利用率小、冲突的机会减小、查找效率高（链表不长）
  // 实际加载因子
  final float loadFactor;
  // 默认加载因子 = 0.75
  static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 3. 扩容阈值（threshold）：当哈希表的大小 ≥ 扩容阈值时，就会扩容哈希表（即扩充HashMap的容量） 
// a. 扩容 = 对哈希表进行resize操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数
// b. 扩容阈值 = 容量 x 加载因子
  int threshold;

// 4. 其他
 // 存储数据的Entry类型 数组，长度 = 2的幂
 // HashMap的实现方式 = 拉链法，Entry数组上的每个元素本质上是一个单向链表
  transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;  
 // HashMap的大小，即 HashMap中存储的键值对的数量
  transient int size;
 

JDK1.7

在JDK1.7中，HashMap是由数组+链表实现的，原理图如下：

HashMap map = new HashMap(); // 伪初始化
map.put("键"，"值"); // 真初始化

HashMap的构造方法在执行时会初始化一个数组table，大小为0。HashMap的put方法在执行时首先会判断table的大小是否为0，如果为0则会进行真初始化，也叫做延迟初始化。

当进行真初始化时，数组的默认大小为16，当然也可以调用HashMap的有参构造方法由你来指定一个数组的初始化容量。

注：并不是你真正说了算，比如你现在想让数组的初始化容量为6，那么HashMap会生成一个大小为8的数组，如果你想数组的初始化容量为20，那么HashMap会生成一个大小为32的数组，也就是你想初始化一个大小为n的数组，但是HashMap会初始化一个大小大于等于n的二次方数的一个数组。。

对于put方法，当无需对table进行初始化或已经初始化完了之后，它接下来的主要任务是将key和value存到数组或链表中。那么怎么将一个key-value给存到数组中去呢？

我们知道，如果我们想往数组中存入数据，我们首先得有一个数组下标，而我们在进行put的时候并不需要再传一个参数来作为数组的下标，那是因为HashMap会利用hash算法将key转换为数组下标。

但是还有一个问题就是，HashCode它能直接作为数组下标吗？

HashCode它通常是一个比较大的数字，比如：

System.out.println("键".hashCode()); // 38190
// 为什么是这个结果，大家自行去看String类中的hashCode方法

所以我们不可能把这么大的一个数字作为数组下标，那怎么办？

大家可能通常会想到取模运算，但是HashMap没有用取模，而是：

static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}

这个方法就是JDK1.7HashMap中put和get方法中获取数组下标的方法，这个方法中h代表hashcode，length代表数组长度。我们发现它是用的逻辑与操作，那么问题就来了，逻辑与操作能准确的算出来一个数组下标？我们来算算，假设hashcode是01010101(二进制表示)，length为00010000(16的二进制表示)，那么h & (length-1)则为：

h:  0101 0101
15: 0000 1111
  &
    0000 0101

对于上面这个运行结果的取值方法我们来讨论一下：因为15的高四位都是0，低四位都是1，而与操作的逻辑是两个运算位都为1结果才为1，所以对于上面这个运算结果的高四位肯定都是0，而低四位和h的低四位是一样的，所以结果的取值范围就是h的低四位的一个取值范围：0000-1111，也就是0至15，所以这个结果是符合数组下标的取值范围的。

那么假设length为17呢？那么h & (length-1)则为：

h:  0101 0101
16: 0001 0000
  &
    0001 0000

当length为17时，上面的运算的结果取值范围只有两个值，要么是0000 0000，要么是0001 000，这是不太好的。

所以，如果我们想把HashCode转换为覆盖数组下标取值范围的下标，跟我们的length是非常相关的，length如果是16，那么减一之后就是15(0000 1111)，正是这种高位都为0，低位都为1的二级制数才保证了可以对任意一个hashcode经过逻辑与操作后得到的结果是我们想要的数组下标。这就是为什么在真初始化HashMap的时候，对于数组的长度一定要是二次方数，二次方数和算数组下标是息息相关的，而这种位运算是要比取模更快的。

总结：在调用put方法时，会对传入的key进行哈希运算得到一个hashcode，然后再通过逻辑与操作得到一个数组下标，最后将key-value存在这个数组下标处。

Hash冲突解决

HashMap存储结构如下图：

那么节点1和节点2组成了一个链表，那么现在如果再来put一个节点3，假设节点3也需要插在这个链表中，我们考虑链表的插入效率，将节点3插在链表的头部是最快的，那么就会如下图：

那么按照上图这种插入办法，会出现一个问题：

• 当需要get(节点2)时，只需要先将节点2的key进行哈希然后算出下标，拿到下标后可以定位到数组中的节点1，但是发现节点1不等于节点2，所以不是最终的结果，但是节点1存在下一个节点，所以可以顺着向下的指针找到节点2。
• 那么当需要get(节点3)时呢，我们可以发现是找不到节点3的，所以当把节点简单的插在链表的头部是不行的。

那HashMap是怎么实现的呢？HashMap确实是将节点插在链表的头部，但是在插完之后HashMap会将整个链表向下移动一位，移动完之后就会变成：

那么现在put的时候插入一个元素的思路就是：将新节点插在链表的头部，此时新节点就是当前这个链表的头节点，接下来把头节点移动到数组位置即可。

当我们在使用HashMap的时候，还可能会出现下面的使用方式:

HashMap<String, String> hashMap = new HashMap<>();
hashMap.put("1", "2");
String value = hashMap.put("1", "3");
System.out.println(value);

第三行代码也是put，而这个时候在HashMap里会将value覆盖，也就是key=”1”对应的value最终为”3”，而第三行代码返回的value将会是2。

我们现在来考虑这个put它是如何实现的，其实很简单，第三行代码的逻辑也是先对”1”计算哈希值以及对应的数组下标，有了数组下标之后就可以找到对应的位置的链表，而在将新节点插入到链表之前，还需要判断一下当前新节点的key值是不是已经在这个链表上存在，所以需要先去遍历当前这个位置的链表，在遍历的过程中如果找到了相同的key则会进行value的覆盖，并且返回oldvalue。

写到这里其实对于HashMap的put的主要逻辑也差不多了，总结一下：

1. 先put一个k-v对：put(key，value)
2. 对key计算一个hashcode：int hashcode = key.hashCode();
3. hashcode和(length - 1)进行运算：int index = hashcode & (数组长度-1)
4. 遍历index位置的链表，如果存在相同的key，则进行value覆盖，并且返回之前的value值
5. 将key，value封装为节点对象（Entry）
6. 将节点插在index位置上的链表的头部
7. 将链表头节点移动到数组上

这是最核心的7步，然后在这个过程中还有很重要的一步就是扩容，而扩容是发生在插入节点之前的，也就是步骤4和5之间的。

总结

不同	JDK 1.7	JDK 1.8
存储结构	数组 + 链表	数组 + 链表 + 红黑树
初始化方式	单独函数：inflateTable()	直接集成到了扩容函数resize()中
hash值计算方式	扰动处理 = 9次扰动 = 4次位运算 + 5次异或运算	扰动处理 = 2次扰动 = 1次位运算 + 1次异或运算
存放数据的规则	无冲突时，存放数组；冲突时，存放链表	无冲突时，存放数组；冲突 & 链表长度 < 8：存放单链表；冲突 & 链表长度 > 8：树化并存放红黑树
插入数据方式	头插法（先将原位置的数据移到后1位，再插入数据到该位置）	尾插法（直接插入到链表尾部/红黑树）
扩容后存储位置的计算方式	全部按照原来方法进行计算（即hashCode ->> 扰动函数 ->> (h&length-1)）	按照扩容后的规律计算（即扩容后的位置=原位置 or 原位置 + 旧容量）

注：JDK1.8以后并不是所有链表大于8的时候链表都会转化为红黑树的：当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。

• 问题1：为什么不直接采用经过hashCode（）处理的哈希码作为存储数组table的下标位置？

  容易出现 哈希码 与 数组大小范围不匹配的情况，即计算出来的哈希码可能 不在数组大小范围内，从而导致无法匹配存储位置

  

  为了解决 “哈希码与数组大小范围不匹配” 的问题，HashMap给出了解决方案：哈希码 与运算（&） （数组长度-1）；

• 问题2：为什么在计算数组下标前，需对哈希码进行二次处理：扰动处理？

  加大哈希码低位的随机性，使得分布更均匀，从而提高对应数组存储下标位置的随机性 & 均匀性，最终减少Hash冲突

• 问题3，HashMap如何扩容

  • 扩容：创建一个新的Entry空数组，长度是原数组的2倍。
  • ReHash：遍历原Entry数组，把所有的Entry重新Hash到新数组。

• 问题4：为什么要ReHash？

  因为Hash函数的公式是 index = HashCode（Key） & （Length - 1），所以如果原来长度（Length）是8，你位运算出来的值是2 ，新的长度是16你位运算出来的值明显不一样了。

• 问题5：为什么JDK1.8会使用尾插法代替头插法

  使用头插会改变链表的上的顺序，但是如果使用尾插，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。

• 问题6：JDK1.7和1.8中hash()函数有何区别？

  相比在1.7中的4次位运算，5次异或运算（9次扰动），在1.8中，只进行了1次位运算和1次异或运算（2次扰动）

• 问题7：HashMap 多线程操作导致死循环问题

  主要原因在于并发下的 Rehash 会造成元素之间会形成一个循环链表。不过，jdk 1.8 后解决了这个问题，但是还是不建议在多线程下使用 HashMap,因为多线程下使用 HashMap 还是会存在其他问题比如数据丢失。并发环境下推荐使用 ConcurrentHashMap 。

  详情请查看：https://coolshell.cn/articles/9606.html