HashMap底层实现

目录索引

1.java中Map相关结构体系

2.HashMap源码中的细节

3.JDK1.8中对HashMap的改进

4.高并发下的HashMap

1 Map结构体系简单介绍

            上文ArrayList相关介绍中有提到java中除了单个元素成“列”存储的列表容器以外，还提供了存储  key-value 成对格式的对象容器。Map的实现类有HashMap、Hashtable、LinkedHashMap和TreeMap，类继承关系如下图所示：

图片来源于Java 8系列之重新认识HashMap

注：图中LinkedHashMap少了一个字母‘h’  哈哈，抠细节

2.1 HashMap定义

          HashMap 继承了 AbstractMap 抽象类实现了Map接口，用于存储Key-Value键值对的集合，它的主干是一个存储Entry对象（1.8中改为了Node）的数组，初始值都被设置为null.。当每次插入一个新的Entry对象，首先根据该对象的 key 值计算一个 hashcode ，然后通过一个 hash 函数计算出该元素应该放在 Entry 应该放在哪个桶中。

图片来源于Java 8系列之重新认识HashMap -

        如上图所示，整个  HashMap 相当于一个 table,每个 table 由若干个桶组成，每个桶中存储一个单向链表，在JDK 1.8中某个桶中的链表长度超过 8时，将会把该桶中的元素构建为一颗红黑树。

2.2 HashMap源码中的一些细节

          每次想在HashMap中存储一个键值对时，第一步先创建一个Entry(java8中改成了Node)对象，然后将该对象键的 hashcode 值通过 hash 函数映射计算出该 Entry 应该存储在HashMap中的具体位置下标；通常情况下 ，多个不同的对象可能会计算出相同的hashcode 值，这样就会出现散列冲突，为了解决冲突，具有相同hashcode值的不同对象会通过链表的形式存储在同一个索引上,当一个索引的长度超过8时，会把链表转换为红黑树。关于红黑树是个大专题在这里不瞎谈，改天单独认真聊。

put  时值的注意的一些细节：  为什么要求hashMap的默认长度以及扩    容后的 Node桶的个数必须是 2 的次幂

      简单的说是为了避免出现过多的hash冲突，举个例子说明  假设 key = "Apple"的hashcode值为：  1111 1111 1111 1111 1111 0000 1110 1010                                                                                              &

假设table的Node桶的个数 length 为10：    0000 0000 0000 0000 0000 0000 0000 1010

  计算结果是：      0000 0000 0000 0000 0000 0000 0000 1010

          如果下一个要存入的 Node 对象的key的 hashcode 最低四位是： 1111  那么和 1010 取 & 运算结果仍然是 1010，明显 hashcode 的最后四位值不相同，结果经过 hash 后却获得了相同的索引；还有一个问题就是在上面的例子中，有些索引值是永远不会出现的：比如1111 0101 0001 0100      这样会导致更多的hash冲突不说还会导致某些索引值所在的位置永远不会存入元素，这些都是我们不希望看到的。然后把问题回到起点，发生更多的hash冲突的原因是table中的node桶个数的二进制低位上有 0，这样取 & 运算 0 所在的位置当然不会计算出 1，为了解决这个问题java设计师将Node 桶个数规定为 2 的次幂，这样 hashcode 值和 length-1 取 & 运算就会使得每次计算出的索引值都和 hashcode 的低位值一致（上面例子中的最后四位）。 并且不会出现某些索引被遗忘的情况，继续上面的例子：

        key = "Apple"的 hashcode 值为：          1111 1111 1111 1111 1111 0000 1110 1010

                                                                      &

假设table的Node桶的个数length-1为15： 0000 0000 0000 0000 0000 0000 0000 1111

                                          计算结果是：        0000 0000 0000 0000 0000 0000 0000 1010 

如果下一个要存入的Node对象key的hashcode最后四位是： 1111 那么和 1010 取 & 运算结果是1111，这样就很大程度上减少了hash冲突，同时也不会出现某些桶不会存入Node对象的情况 JDK1.7中的hash函数就是这样实现的，但是在JDK 1.8 中又做了进一步的改进，假设有两个Node对象的 hashcode 值计算出来低16位完全相同，但是高 16 位值不同，当table的桶个数较小的时候这两个对象的hashcode值直接和length - 1取 &，求得的索引是相同的，但是如果在取 & 之前，将两个对象的hashcode值右移16位，再和原来的 hashcode 值取异或，这样就会使得原来相同的低16 变为不同，接着和 length-1 取&，求得的索引值是不相同的两个数，很好地解决了这种冲突，但是这样也会有不好的情况，就是可能会把之前低 16 不相等 hashcode 值变为相等，不过出现的几率会很小。

JDK 1.8 hash 函数 putVal 的部分源码

putVal 中 的片段说明，虽然没有了1.7 中 的 indexOf 方法单独确定下标，但是在做插入判断的时候依然是 和 length-1 做 & 运算

*  if ((p = tab[i = (n - 1) & hash]) == null)

举个例子说明一下前面说到的“不足”：

  hashcode值1：1111 1111 1111 1010 1111 0000 1110 1010

                                  ^

  >>>16    0000 0000 0000 0000 1111 1111 1111 1010

  异或结果  0000 0000 0000 0000 1111 1111 1111 0000

                                                                                          & 

  length-1：                                          1111

hash  结果：                                        0000

*  hashcode值2：1111 1111 1111 0101 1111 0000 1110 0101

                                      ^

                >>>16    0000 0000 0000 0000 1111 1111 1111 0101

                  异或结果  1111 1111 1111 1111 0000 1111 0001 0000

                                                                                          &

          length-1 ：                            1111                                                       

          hash 结果：                          0000               

如上面的例子所示，本来不相同两个 hashcode 值，却计算出了相同的下标；不过这种情况出现的概率是很小的，总得来说每一次改进都只是更好的一种优化权衡，而不是直接消除 hash 冲突，因为hash冲突只能尽量避免而不能完全消除。不然链地址法就完全没有用武之地了。

接下来谈谈table中很重要的一个字段 threshold：

        threshold  = Load factor负载因子(默认值是0.75)* length;引入负载因子的目的是用它来衡量一个 table 到底能装多满，负载因子很大则说明内存空间被充分利用，由于查找效率和table中的桶个数有关，table  装的越满，则查找效率越低；相反如果负载因子很小则说明一个table中有很多的空桶，这样会造成内存空间浪费，除非在对内存空间和执行效率把控特别到位的时候才可以适当调整默认值 0.75，否则慎改。

put具体步骤：（摘自Java 8系列之重新认识HashMap - ）

putVal流程图

①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；

②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；

③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；

④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；

⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；

⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

JDK1.8 中 的扩容优化：

      首先会创建原table两倍大小的新table，然后将旧数组中的元素通过再hash插入到新的数组中，与1.7 不同的是在移动旧元素时1.8中会根据元素在旧数组中索引位 判断出该元素在新数组中应该插入的位置而不需要再次 hash，因为新数组的长度是原数组的 2 倍，所以假如再次进行  hash 变化的只是第三步和 length-1 做 & 运算的时候，由于 length-1 比之前多了一位 1，多出来的一位和 hashcode 高低位异或后对应的那一位要么是 0 要么是 1 ； 如果是 0，那么该元素应该插入到与旧数组索引值相同的位置，如果是 1，那么该元素应该插入到在旧数组索引值加上旧数组的总长度的位置。这样就很好的避免了再次求 hash 值，只需要查看原来的 hash 值中异或后多出来的一位时 0 还是 1。举例见下图：

JDK1.8 hash 原理图

3  最后聊聊 HashMap 的线程不安全

大家都知道在多线程环境下 HashMap 是线程不安全的，最可怕的是如果两个线程同时并发执行同一个 HashMap 时有可能形成一个隐藏起来的环，就像一个定时炸弹一样，在某个时刻随时爆发。下面举个例子，简单说明一下形成换的过程：

下图是JDK 1.7 中扩容时将旧数组中的元素移动到新数组的具体过程，从源码中可以看出每移动一个元素都要重新 hash 求得在新数组中的索引值。插入时若索引冲突将会按头插法插入到对应桶的链表中

新旧更替

          现在模拟一个并发场景，有两个线程同时对一个 HashMap 对象进行扩容操作，线程一新建一个长度为两倍的新 table，接下来线程二抢夺CPU同样新建了一个新 table；然后线程一继续获得CPU执行到 transfer 方法中的 next = e.next 时线程二再次抢夺了CPU执行完整个转移操作。此时两线程的状态如下图所示：

第一阶段

线程二执行完了转移操作，线程一获得CPU，由于线程一上次执行到了 next = e.next，所以此时继续执行，当前为线程一的第一次循环：

e = 3    next  = 7    e.next = newTable[i] = null    newTable[i] = e = 3          e = next = 7

第一次循环后的状态

注意：原先的旧数组已经被线程一置空了，所以线程一指向的 e = 3 和 next = 7 都已经被移动到了线程二创建的新 table 中。

接下来执行第二次循环：

e = 7      next = 3    e.next = newTable[i] = 3      newTable[i] = 7    e = next = 3

第二次循环后的状态

第三循环见证奇迹：

e = 3    next = null    e.next = newTable[i] = 7    newTable[i] = 3  e = null  插入完毕

最后一次循环后的状态

e 最终指向了null 就这样悄无声息的转移完成了，然而如上图所示索引值为 3 的桶中的链表出现了一个环，3 指向了 7 ====》7 指向了3；这样在以后某个时刻当调用get方法时，查找的元素索引值刚好是3，但是该元素在链表中不存在，这样执行get的线程将会在一个环中查找一个不存在的，永不停歇直到世界末日，哈哈。

好了，今天就先写到这，关于HashMap还有很多值得聊的地方，下次再说。

晚安，牧羊十二

民谣很穷，一支烟就诉尽了一生