HashMap（JDK 1.7）

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

HashMap（JDK 1.7） - 图1

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

数组部分

初始化

HashMap 的构造方法在执行时会初始化一个数组 table，大小为 0。
HashMap 的 PUT 方法在执行时首先会判断 table 的大小是否为 0，如果为 0 则会开始进行真初始化，也叫做延迟初始化。
当进行真初始化时，数组的默认大小为 16，当然也可以调用 hashmap 的有参构造方法由你来指定一个数组的初始化容量，但是注意，并不是你真正说了算，比如你现在想让数组的初始化容量为 6，那么 hashmap 会生成一个大小为 8 的数组，如果你想数组的初始化容量为 20，那么 hashmap 会生成一个大小为 32 的数组，也就是你想初始化一个大小为 n 的数组，但是 hashmap 会初始化一个大小大于等于 n 的二次方数的一个数组。

HashCode（key）

对于 PUT 方法，当无需对 table 进行初始化或已经初始化完了之后，它接下来的主要任务是将key 和 value 存到数组或链表中。那么怎么将一个键值对给存到数组中去呢？
我们知道，如果我们想往数组中存入数据，我们首先得有一个数组下标，而我们在进行 put 的时候并不需要再传一个参数来作为数组的下标，那么 hashmap 中下标是怎么获取来的呢？答案为哈希算法，这也是为什么叫 hashmap 而不叫其他的 map

对于哈希算法，了解过的人应该都知道它需要一个哈希函数，这个函数接收一个参数返回一个 HashCode，哈希函数的特点是对于相同的参数那么返回的 HashCode 肯定是相同的，对于不相同的参数，函数会尽可能的去返回不相同的 HashCode，所以换一个角度理解，对于哈希函数，给不相同的参数可能会返回相同的 HashCode，这个就叫哈希冲突或哈希碰撞。

那么我们能直接把这个 HashCode 来作为数组下标吗，另外一个很重要的问题是我们到底应该对 key 做哈希运算还是对 value 做哈希运算，还是对 key-value 同时做哈希运算？

那么这个时候我们就要考虑到 GET 方法了，因为 get 只需要传入一个 key 作为参数，而实际上 get 方法的逻辑就是通过把 key 进行哈希运算快速的得到数组下标，从而快速的找到 key 所对应的 value。所以对于 put 方法虽然传入了两个参数，但是只能对 key 进行哈希运算得到数组下标，这样才能方便 GET 方法快速查找。
**

数组下标（index）

但是还有一个问题就是，HashCode 它能直接作为数组下标吗？
**
HashCode 它通常是一个比较大的数字，比如：

  1. System.out.println("键".hashCode()); // 38190

所以我们不可能把这么大的一个数字作为数组下标，那怎么办？
大家可能通常会想到取模运算，但是 HashMap 没有用取模，而是：

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

这个方法就是 JDK1.7 HashMap 中 PUT 和 GET 方法中获取数组下标的方法（PUT 和 GET 两个方法都要去获取下标？是的，如果你看到这里看不懂了，那么你再去想想上面的讲的提高GET方法效率的逻辑吧），这个方法中 h 代表 hashcode，length 代表数组长度。我们发现它是用的逻辑与操作，那么问题就来了，逻辑与操作能准确的算出来一个数组下标？我们来算算，假设 hashcode 是 0101 0101（二进制表示），length 为 0001 0000（16的二进制表示），那么 **h & ( length - 1 )** 则为：

  1. h:  0101 0101
  2. 15: 0000 1111
  3. &   ---------
  4.     0000 0101

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

所以我们发现，如果我们想把 HashCode 转换为覆盖数组下标取值范围的下标，跟我们的 length 是非常相关的，length 如果是16，那么减一之后就是 15（0000 1111），正是这种高位都为 0，低位都为 1 的二级制数才保证了可以对任意一个 hashcode 经过逻辑与操作后得到的结果是我们想要的数组下标。这就是为什么在真初始化 HashMap 的时候，对于数组的长度一定要是二次方数，二次方数和算数组下标是息息相关的，而这种位运算是要比取模更快的。
**所以到此我们可以理一下：在调用 PUT 方法时，会对传入的 key 进行哈希运算得到一个 hashcode，然后再通过逻辑与操作得到一个数组下标，最后将 entry 存在这个数组下标处。

确定了 entry 该存的位置之后，上文说过，对于不同的参数可能会得到相同的 HashCode，也就是会发生哈希冲突，反应到 HashMap 中就是，当 PUT 两个不同的 key 时可能会得到相同的 HashCode 从而得到相同的数组下标，其实在 HashMap 中就算 key 所对应的 HashCode 不一样，那么也有可能在经过逻辑与操作之后得到相同的数组下标，那么这时 HashMap 是如何处理的呢？对，就是用链表来实现的


链表部分

链表结构

HASHMAP（JDK1.7）在 PUT 的时候会发生冲突，而解决冲突的方式就是使用链表，那么我们假设 HASHMAP 存储结构如下图：
HashMap（JDK 1.7） - 图2
那么节点1和节点2组成了一个链表，那么现在如果再来 PUT 一个节点3，假设节点3也需要插在这个链表中，我们考虑链表的插入效率，将节点3插在链表的头部是最快的，那么就会如下图：
HashMap（JDK 1.7） - 图3
那么按照上图这种插入办法，会出现一个问题：

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

实现方式

那 HashMap 是怎么实现的呢？HashMap 确实是将节点插在链表的头部，但是在插完之后 HashMap 会将整个链表向下移动一位，移动完之后就会变成：
HashMap（JDK 1.7） - 图4
那么现在PUT的时候插入一个元素的思路就是：将新节点插在链表的头部，此时新节点就是当前这个链表的头节点，接下来把头节点移动到数组位置即可。
**

值替换

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

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

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

PUT 总结

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

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

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

扩容

当进行 PUT 操作的时候，会引发扩容的现象：

  • 当 HASHMAP 的数组长度超过阈值（初始化的长度 * 加载因子），并且原有数据位已经存在链表（JDK 1.8 后剔除了该条件），就会发生扩容，每次扩容都会增加原有长度的两倍，比如原来是 16，就会扩容（创建一个新的数组）成 32。
  • 扩容后，会循环原有数组，然后再循环数组中的链表（需要的话会重新计算 hash 值，根据 jdk.map.althashing.threshold 参数控制），将数据转移到扩容后的数组中。
  • 如果是多线程进行扩容的话，会出现循环链表的问题，就导致死循环的现象。

  • modCount

    记录修改 HashMap 的次数，当在循环中利用 map.remove(key) 的方式删除元素时，会记录一个遍历 expectModeCount = modCount，每次 map.remove(key) 的时候都会比较这两个值是否一致，否则抛出异常，这就解释了为什么在 HashMap 中循环删除元素会报错的原因

解决办法

  • remove 后立刻 break
  • 利用 iterator 的方式方式删除 iteator.remove()