上文讲到 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 遍历的数据不是有序的是无序的
来源: https://www.cnblogs.com/Scramblecode/p/11205088.html