HashMap源码分析二看完彻底了解HashMap

上文讲到 HashMap 的增加方法，现在继续 [上文链接]()

HashMap 在上一篇源码分析的文章中，如果使用 put 的时候如果元素数量超过 threshold 就会调用 resize 进行扩容

1. 扩容机制

想要了解 HashMap 的扩容机制你要有这两个问题

• 1. 什么时候才需要扩容
• 2.HashMap 的扩容是什么

在添加元素的时候如果超过 threshold 设置的阀值点就会进行扩容，简单的来说就是一个水壶容量是二升，然后这个时候已经满了但是你还要继续加水，咋办？换个大的。所以 HashMap 的扩容就和你这个水壶一样，水已经满了那我就在换个大的水壶继续加水。不过在你换水壶的时候是有很多条件的。

在我看这个 resize 的源码的时候我也是一脸懵逼，最后请教了大佬得到的回答是因为 1.8 加入了红黑树比较麻烦可以看一下 1.7 的，然后我有去网上看了一下别人写的文章基本上都是基于 1.7 的 resize。所以这里就看 1.7 的 resize 来分析。

来看 JDK1.7 中 resize 的实现。

复制操作是调用的 transfer 方法

在 1.7 中的 resize 结合一下我们的小例子可以这样理解，去超市买一个大一点的水壶，然后把以前水壶里面的水给倒进新的水壶里面。再把我们当前的水壶的容量替换掉，告诉别人我的容量更大了。（强行比喻哈哈哈哈哈）

1.7 中的 resize 就是这么简单，那我们在看一下 1.8 中的 resize(), 这样再看就不会一脸懵逼了

我在这里把 1.8 的 resize 方法分为两部分

• 1. 计算新的 newCap(新的容量) 和 newThr(新阀值点)
• 2. 复制新的数组

第一部分

第二部分

对比一下 1.7

• 1.7 元素不需要更换位置。1.8 元素的位置要么是在原位置，要么是在原位置再移动 2 次幂的位置
• 不需要像 1.7 一样重新计算 hash

2. 删除

删除的话就是首先先找到元素的位置，如果是链表就遍历链表找到元素之后删除。如果是用红黑树就遍历树然后找到之后做删除，树小于 6 的时候要转链表。

删除方法：

调用 removeNode：

3. 查找元素

查找方法，通过元素的 Key 找到 Value。

调用 getNode() 方法

看完可以知道逻辑是先通过 Key 计算出索引的位置，然后先检查第一个节点看看是否是我们要的节点，如果不是在去查看是否死红黑树和链表。

4. 遍历

我们通过下面几个例子来演示一下 HashMap 怎么遍历

1. 分别遍历 Key 和 Values

         for (String key:map.keySet()){System.out.println(key);
        }
        for (Object value : map.values()) {System.out.println(value);
        }

2. 迭代

         Iterator<Map.Entry<String, Object>> iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {Map.Entry<String, Object> mapEntry = iterator.next();
            System.out.println(mapEntry.getKey() + "====" + mapEntry.getValue());
        }

3. 获取 key 集合

     Set<String> keySet = map.keySet();
        for (String str : keySet) {System.out.println(str + "====" + map.get(str));
        }

4. 获取 Entry 集合，遍历 Entry 集合

    Set<Map.Entry<String, Object>> entrySet = map.entrySet();
        for (Map.Entry<String, Object> entry : entrySet) {System.out.println(entry.getKey() + "====" + entry.getValue());
        }

对比来说使用迭代的方式是最好的，也可以在迭代的时候对集合的元素进行删除

总结

基于 JDK1.8 的 HashMap 是由数组 + 链表 + 红黑树组成，当链表长度超过 8 时会自动转换成红黑树，当红黑树节点个数小于 6 时，又会转化成链表。相对于早期版本的 JDK HashMap 实现，新增了红黑树作为底层数据结构，在数据量较大且哈希碰撞较多时，能够极大的增加检索的效率。HashMap 并不是线程安全的，支持 K 和 V 为 null ,k 重复会覆盖，V 可以重复， 还有一点 HashMap 遍历的数据不是有序的是无序的