【java】HashMap1.8源码详解

在first = tab[(n - 1) & hash])中，这里直接获取下标，而1.7中单独写了一个方法获取下标，1.8更加简洁。这里的下标操作，我复制了之前的博文，以免给没有看过解释HashMap1.7的博文的读者带来困惑。读过的人可以跳过。

//HashMap1.7中如何查找数组下标
static int indexFor(int h, int length) {return h & (length-1);
}

这个方法虽然只有一个说法，但是却关系到很多东西。例如，读者一定很好奇为什么默认容量是1 << 4 = 16，为什么会调用roundUpToPowerOf2(toSize)方法？这就给我们带来了Hashmap最关键的一点，就是通过哈希值来确定数组下标。由于哈希值的哈希值非常大，而数组的容量有限，因此如何确定下标就非常关键。
程序员想到的最简单的方法就是取模运算：hash % length
hash 是一个 int 类型的值。假设length为默认容量16，那么hash % length得到的数组范围为0 - 15，符合Array存储原则。
然而jdk作者选择的是位运算：hash & (length - 1)
我们通过一个例子来验证一下：假设length=16，那么length-1=15，二进制表示0000 1111

从上面验证的结论来看，得到的下标仍然在0-15之间，位运算的运算速度比取模运算要快。影响是容量必须是2的指数次方（二进制数每一位的权重是2的指数次方）。如果不是，那么capacity-1的二进制结果中的低位将不会全部为1，这样就会增加哈希冲突的概率；这很容易理解。如果低位中的某一位为0，那么无论该哈希值对应的位是1还是0，与运算的结果都会为0，那么得到相同下标的可能性就变大。

put（K键，V值）

putVal() 步骤总结：

• 如果表未初始化，则先初始化表数组
• 假设目标下标为index，判断table[index]是否为空，如果为空，则直接添加节点
• 如果不是为空，检查第一个节点，如果key相同，则保存对象
• 判断后面的节点，如果是树结构，则putTreeVal()
• 如果是链表，找到与相同key并保存对象，如果不存在则追新节点
• 追尾链表中的节点后，可能需要将链表转换为红黑树
• 如果保存的对象不为null，可能需要替换oldValue
• 添加新节点后，必须判断数组是否需要扩容
  

  //如果容器中没有该映射，则添加；如果有则替换旧值并返回旧值public V put(K key, V value) {//参数 false：更改现有值；参数 true：未处于创建模式 return putVal(hash(key), key, value, false, true);
  }// @param onlyIfAbsent 如果为true，则不会更改现有值（旧值不会被替换）
  // @param evict 该参数传递给LinkedHashMap的空方法
  // 实现了map.put()及相关方法Final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node[] tab;节点 p; int n, i;// 懒加载模式，判断数组是否初始化，如果没有，则先初始化 if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 如果下标没有节点，则直接创建节点 if ((p = tab[i = (n - 1) & hash]) == null)// null 表示说明该节点的下一个节点为空，且该节点为链表末尾 Node tab[i] = newNode(hash, key, value, null);// 该下标有一个节点，可能是链表或者树 else {Node e;K k;// 一般检查第一个，原因与 getNode() 方法一致 if (p.hash == hash &&((k = p. key) == key || (key != null && key.equals(k))))// 直接复制引用并替换末尾的oldValue e = p; // 红黑树 else if (p instanceof TreeNode) // 1.如果oldTreeNode存在，则直接返回该节点 // 2.如果oldTreeNode不存在，则将其添加到树中 e = ((TreeNode)p ).putTreeVal(this, tab, hash, key, value);else {// 遍历链表 for (int binCount = 0; ; ++binCount) {// 在尾节点判断长度才有意义链表的 if ((e = www.sychzs.cn) == null) {// p存在的意义：链表的基本操作，保存尾部加法的最后一个节点 // 尾部加法添加节点p。 next = newNode(hash, key, value, null);//TREEIFY_THRESHOLD = 8, 当节点数 >= 8 时，会转为树结构 if (binCount >= TREEIFY_THRESHOLD - 1)treeifyBin(tab, hash ）;break;}//找到key对应的节点 if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) break ;p = e;}}//存在旧映射关系 if (e != null) {V oldValue = e.value;//onlyIfAbsent 控制是否改变已有值，1.7 增强 if (!onlyIfAbsent || oldValue == null)e.value = value;// 空方法 afterNodeAccess(e); return oldValue;}}++modCount;// 1.7 的扩展条件已减少 // 1.7 的条件： (size >= Threshold) && (null != table[bucketIndex])if (++size > Threshold)resize ();//清空方法afterNodeInsertion(evict);return null;}//虽然转换成了树，但是链表的关系依然保留。为了查询该值最终 void treeifyBin(Node[] tab, int hash) {int n, index; Node e;//如果程序没有问题，那么tab永远不会等于null//如果数组很小，可以通过扩展的方式减少哈希冲突，无需转换为树 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize();// 获取目标下标的链表，准备转换为树 else if ((e = tab[index = (n - 1) ) & hash]) != null) {TreeNode hd = null, tl = null;do {// 只是调用Node构造函数生成独立节点。 TreeNode p = replacementTreeNode(e, null); // 这里独立节点变成了链表 if (tl == null)hd = p;否则{p.prev = tl; // next 成员来自 HashMap.Node ，继承关系 www.sychzs.cn = p;}tl = p;} while ((e = www.sychzs.cn) != null);if ((tab[index] = hd) != null)//真正转换为树 方法 hd.treeify(tab);}
  }public void putAll(Map m) {putMapEntries(m, true);
  }
  

  在HashMap1.7中，向链表添加节点的方式是前向插值。前向插值虽然会提高插入效率，但会造成严重的死循环问题。博主的HashMap1.7博文中有详细介绍。解释;因此1.8采用了尾部加法，但是无法避免多线程安全问题，下面会说明。

  resize() - 多线程数据丢失问题

  //初始化表，或者展开表，仍然将尾部添加到链表中最终 Node[] resize() {Node[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = Threshold;int newCap, newThr = 0;//初始化情况： // 1.用户设置了容量，则oldThr > 0为true // 2.用户没有设置容量（无参数构造），则最后一个else为true // 非初始化情况： // oldCap > 0为true，newCap必然会使其容量增加一倍，但阈值不一定会改变 if (oldCap > 0) {//如果超过最大容量，改变阈值，大约是最大容量的两倍，2^31-1 = 2*(2^30) // 如果oldCap >= MAXIMUM_CAPACITY 不为true，那么最大oldCap只能是2^29if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}//选择1：容量加倍后仍小于最大值&& oldCap >= 16，不一定为真 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)//如果条件成立，因为线性关系，只需将扩展阈值加倍 newThr = oldThr << 1;}else if (oldThr > 0)//选择2：使用双参数或单参数的结果构造函数（不包括带有map参数的构造函数） // 初始容量设置为阈值，因为双参构造函数中将容量赋值为threshold // this.threshold = tableSizeFor(initialCapacity);newCap = oldThr;// oldCap == 0 && oldThr == 0else { //使用无参构造函数或者带map参数的单参构造函数 newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}//选择1不成立或者选择当e 2 成立时，newThr == 0 成立 if (newThr == 0) {// ft 为thresholdfloat ft = (float)newCap * loadFactor;// 临界情况：newCap > MAXIMUM_CAPACITY && Threshold < MAXIMUM_CAPACITY // 这里newCap < MAXIMUM_CAPACITY 如果不是，则 newCap = MAXIMUM_CAPACITY 必须为 true newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr;@SuppressWarnings({"rawtypes"," unchecked"} )// 由于容量设置的规则，这里的newCap最大为MAXIMUM_CAPACITY，所以不需要考虑法律问题 Node[] newTab = (Node[])new Node[newCap ];table = newTab;if (oldTab != null) {//遍历数组下标。在哈希表的存储规则下，节点中存储的下标不连续 for (int j = 0; j < oldCap; ++j) {Node e ;if ((e = oldTab[j]) != null) {//线程1在if判断前挂起，线程2到达这里，保留唯一的oldTab[j] //线程1继续执行，发现oldTab[j]为空，跳过该下标的所有元素 //然后将原表数组中的数据分成两部分，两个线程都有自己的newTab // 都会覆盖表成员，无论两个线程是否覆盖表，按照前后顺序，总有一个一组数据丢失 // 这导致了严重的数据丢失。如果情况严重，可能只保留原来的链或树 // 人们不禁认为这是神来之笔，为什么oldTab要留空[j]？ // e = oldTab[j]语句已经保留了链表或树头节点的引用，gc无法回收这个节点集。 // 方法运行后，gc会自动回收原来的表引用，所以这不是没有必要吗？ //如果不留空，那么每个线程传输的都是一样的，虽然会降低性能，但是这种情况下不会丢失 oldTab[j] = null;//先检查第一个，提高效率 if (www.sychzs.cn == null) newTab[ e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode)//将原树结构拆分，形成新树 ((TreeNode)e).split(this, newTab, j , oldCap);// 这个节点集是一个链表，原来的一条链可能会变成下面的两条链。 // 至于为什么可能有两条链，请继续阅读 else {Node loHead = null, loTail = null;Node hiHead = null, hiTail = null;Node next;// do - while 这里与 getNode() 方法一致 do {next = www.sychzs.cn; // 原下标形成新链 if ((e.hash & oldCap) == 0) {// 在第一个节点处，loTail == null if (loTail == null)loHead = e;www.sychzs.cn = e; loTail = e;}//另一个下标形成一条新链 else {if (hiTail == null)hiHead = e;www.sychzs.cn = e;hiTail = e;}} while ((e = next) != null); // oldIndex 下有链，赋给数组 if (loTail != null) {www.sychzs.cn = null;newTab[j] = loHead;}​​// oldIndex + oldCap 下有链，且它被赋予数组 if (hiTail != null) { www.sychzs.cn = null;newTab[j + oldCap] = hiHead;}​​}}}}return newTab;}
  

  线程安全问题我已经在代码注释中解释得很详细了，不再赘述。
  在HashMap 1.7中，扩容后会将原来的节点分配到新的数组中，并且在转移过程中会进行rehash，即重新散列和重定位；但1.8中却不是这样，下面我们需要仔细研究1.8中的重新哈希问题。

  情况一：假设某节点的哈希值为：0000 0101，扩容前的数组容量为16，即扩容前的0001 0000。计算下标：
  0000 0101 & 0000 1111 = 0000 0101
  扩容后阵列容量为32，即0010 0000
  计算下标：
  0000 0101 & 0001 1111 = 0000 0101 结论：与原下标相同，即newIndex = oldIndex 情况2：假设某个节点的哈希值为：0001 0101 扩容前的数组容量为16，即0001 0000 Before展开，计算下标：
  0001 0101 & 0000 1111 = 0000 0101
  扩容后阵列容量为32，即0010 0000
  计算下标：
  0000 0101 & 0001 1111 = 0001 0101结论：与原来的下标不同，只是增加了0001 0000
  即newIndex = oldIndex + oldCap
  

  通过上面的验证，可以得出rehash的结果只有两种，形成这两种类型的条件是e.hash & oldCap是否为0。如上例所示，oldCap = 0001 0000 ，那么e.hash & oldCap就是判断hash值的第四位是否为1，如果是1，则结果为1，如果结果为1，则newIndex = oldIndex + oldCap。如果不为1，则newIndex = oldIndex，所以 rehash 的结果只能是这两种情况。通过这种简单的方式就可以实现1.7中rehash的相同功能，提高了效率。

  删除（对象键）

  public V remove(Object key) {Node e;return (e = removeNode(hash(key), key, null, false, true)) == null ?null : e.value;
  }// @param matchValue 如果为true，则只有当值相等时才会删除。所有键值对必须相等。
  // @param moving 如果为false，则删除时其他节点不会移动
  // 实现了map.remove及相关方法Final NoderemoveNode(int hash, Object key, Object value,boolean matchValue, boolean moving) {Node[]选项卡;节点 p; int n, index;// table存在且有效，且当前下标包含有效节点 if ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = ( n - 1) & hash]) != null) {Node  节点 = null, e; K k; V v;// 检查第一个节点 if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))node = p; else if ((e = www.sychzs.cn) != null) {// 查找红黑树 if (p instanceof TreeNode)node = ((TreeNode) p).getTreeNode(hash, key);else { // 遍历链表，看到这里你会发现代码开始重复了 do {if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) {node = e;break;}// p 是前一个节点 p = e;} while ((e = www.sychzs.cn) != null);}} // 当 matchValue 时= false，不需要比较值​​//判断值是否相同是1.8中新增加的功能，可以打开和关闭 if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {//树节点 if (node instanceof TreeNode)((TreeNode)node ).removeTreeNode(this, tab, moving);//链表删除else if (node == p)//满足node == p的条件是：第一个节点为目标节点 tab[index] = www.sychzs.cn;else//如果不是第一个节点，则前一个节点将节点链接到下一个节点 www.sychzs.cn = www.sychzs.cn;//修改个数加一++modCount;--size;//清空方法 afterNodeRemoval(node);return node;}}return null ;}public voidclear() {Node[] tab;modCount++;if ((tab = table) != null && size > 0) {size = 0;//遍历数组，将所有下标元素设置为nullfor (int i = 0; i < tab.length; ++i)tab[i] = null;}
  }
  

  HashMap1.7调用Arrays.fill(tab, null)实现clear()方法；但两者其实本质是一样的，都是被gc暴力清理回收；

  // 1.7 中调用：Arrays.fill(table, null); public static void fill(Object[] a, Object val) {for (int i = 0, len = a.length; i < len; i++ ) {a[i] = val;}
  }
  

  包含值（对象值）

  public boolean containsValue(对象值) {Node[] 选项卡; V v;if ((tab = table) != null && size > 0) {//外循环，遍历数组 for (int i = 0; i < tab.length; ++i) {//内循环遍历链表。虽然是树，但也保留了链表的关系。参见treeifyBin() // 树节点的查询是以key作为搜索的依据，可以优化性能。 get()方法使用树本身的查询方法 // 但是，搜索值无法优化。必须遍历所有节点，所以直接使用 for 循环 for (Node e = tab[i] ; e != null; e = www.sychzs.cn) {if ((v = e.value) == value ||(value != null && value.equals(v)))return true;}}}return false;
  }
  

  其实这个方法并没有什么特别之处。我列出来只是为了解释为什么树结构仍然保留着隐含的链表关系。当然，还体现在下面的方法上。

  forEach（BiConsumer行动）

  public final void forEach(Consumer action) {Node[] tab;if (action == null) throw new NullPointerException();//节点存在于表中 if (size > 0 && (tab) = table) != null) {// 遍历前确定修改次数，保证线程安全 int mc = modCount; // 遍历数组，树节点中的链表关系再次发挥作用 for (int i = 0; i < tab.length; ++i) { for (Node e = tab[i]; e != null; e = www.sychzs.cn)//节点传递给actionaction.accept(e.key) ;}//这是遍历完成后报的异常，所以当原表发生改变时 //上面的遍历结果也可能会改变，但是会报如下异常 if (modCount != mc)throw new ConcurrentModificationException() ;}
  }
  

  用过for-each的人都知道，这是java提供的一种遍历集合的语法。 HashMap 1.8 中提供了显示的 forEach()。下面将演示它的使用。代码比较简单，不再解释。

  new HashMap().keySet().forEach(new Consumer() {@Overridepublic void Accept(String t) {// TODO}
  });
  

  显示的forEach()方法在keySet()、values()、entrySet()对应的KeySet、Values、EntrySet类中也提供了，但它们的其他方法与1.7中基本相同，所以没有更多解释了。

  总结

  HashMap是一个非常强大的工具，但是它也有很多缺陷，其中最严重的是无法保证多线程的安全性，所以最好用在单线程系统中。
  这篇博文解释了HashMap1.8的核心。由于篇幅原因，其他不重要的方法就不列出来了。如果读者想要HashMap1.8完整的注解分析，可以在评论留言。