专栏首页人生得意须尽欢通过threshold字段来判断HashMap的最大容量
原创

通过threshold字段来判断HashMap的最大容量

HashMap的实现中,通过threshold字段来判断HashMap的最大容量:

threshold = (int)(capacity * loadFactor);  

  结合负载因子的定义公式可知,threshold就是在此loadFactor和capacity对应下允许的最大元素数目,超过这个数目就重新resize,以降低实际的负载因子(也就是说虽然数组长度是capacity,但其扩容的临界值却是threshold)。默认的的负载因子0.75是对空间和时间效率的一个平衡选择。当容量超出此最大容量时, resize后的HashMap容量是容量的两倍:

if (size++ >= threshold)   
    resize(2 * table.length); 

Fail-Fast机制

  我们知道java.util.HashMap不是线程安全的,因此如果在使用迭代器的过程中有其他线程修改了map,那么将抛出ConcurrentModificationException,这就是所谓fail-fast策略。   这一策略在源码中的实现是通过modCount域,modCount顾名思义就是修改次数,对HashMap内容的修改都将增加这个值,那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。在迭代过程中,判断modCount跟expectedModCount是否相等,如果不相等就表示已经有其他线程修改了Map:注意到modCount声明为volatile,保证线程之间修改的可见性。(volatile之所以线程安全是因为被volatile修饰的变量不保存缓存,直接在内存中修改,因此能够保证线程之间修改的可见性)。   在HashMap的API中指出:   由所有HashMap类的“collection 视图方法”所返回的迭代器都是快速失败的:在迭代器创建之后,如果从结构上对映射进行修改,除非通过迭代器本身的 remove 方法,其他任何时间任何方式的修改,迭代器都将抛出 ConcurrentModificationException。因此,面对并发的修改,迭代器很快就会快速失败,而不冒在将来不确定的时间发生任意不确定行为的风险。   在迭代器创建之后,其视图中元素已确定,而这个时候,如果外界通过其他任何方式修改此试图,都将导致迭代结果的不一致性,因此这种快速失败行为可以有效的避免面对并发修改时带来的不确定风险。 因此,反过来说,迭代器的这种快速失败行为所抛出的异常,并非是提供给调用者去处理的异常,而是用于检测程序错误。

    // 内部class HashIterator迭代器  
    private abstract class HashIterator<E> implements Iterator<E> {
        Entry<K, V> next;    // 下一个桶  
        int expectedModCount;    // 保护HashMap没有变更  
        int index;        // 当前的索引  
        Entry<K, V> current;    // 当前的桶  

        // 构造方法  
        HashIterator() {
            // 保存modCount,因为如果HashMap进行了任何操作modCount都会增加,所以如果发现modCount变化了,就可以抛出失败  
            expectedModCount = modCount;
            // 进入第一个桶  
            if (size > 0) {
                Entry[] t = table;
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }
        }

        // 看看有没有下一个桶  
        public final boolean hasNext() {
            return next != null;
        }

        // 获取下一个桶  
        final Entry<K, V> nextEntry() {
            // modCount变化了,抛出失败  
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            // 得到next  
            Entry<K, V> e = next;
            // 如果next为空,抛出失败  
            if (e == null)
                throw new NoSuchElementException();

            // 如果next.next为空,将next定义为下一个格子中的桶,否则为该格子的下一个桶  
            if ((next = e.next) == null) {
                Entry[] t = table;
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }
            // 给current赋值  
            current = e;
            // 返回e  
            return e;
        }

        // 删除  
        public void remove() {
            // 如果当前为空,抛出  
            if (current == null)
                throw new IllegalStateException();
            // modCount变化了,抛出失败  
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            // 获得当前的key  
            Object k = current.key;
            // 设置current为null  
            current = null;
            // 删除掉对应key的元素  
            HashMap.this.removeEntryForKey(k);
            // 重置expectedModCount  
            expectedModCount = modCount;
        }

    }

    // 内部class ValueIterator迭代器,我们可以看到修改了next方法  
    private final class ValueIterator extends HashIterator<V> {
        public V next() {
            return nextEntry().value;
        }
    }

    // 内部class KeyIterator迭代器,我们可以看到修改了next方法  
    private final class KeyIterator extends HashIterator<K> {
        public K next() {
            return nextEntry().getKey();
        }
    }

    // 内部class EntryIterator迭代器,我们可以看到修改了next方法  
    private final class EntryIterator extends HashIterator<Map.Entry<K, V>> {
        public Map.Entry<K, V> next() {
            return nextEntry();
        }
    }

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

关注作者,阅读全部精彩内容

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HashMap原理阅读

    前言 还是需要从头阅读下HashMap的源码。目标在于更好的理解HashMap的用法,学习更精炼的编码规范,以及应对面试。 它根据键的hashCode值存储数...

    Ryan-Miao
  • 语言小知识-Java HashMap类 深度解析

    HashMap 也是比较常用的 Java 集合框架类,该类涉及到的知识比较多,包括数组、链表、红黑树等等,还有一些高效巧妙的计算,并且这个类经过几个版本的改进,...

    Wizey
  • 工作三年,小胖连 HashMap 源码都没读过?真的菜!

    在 JDK 1.7 中 HashMap 是以「数组加链表」的形式组成的,JDK 1.8 之后新增了「红黑树」的组成结构,「当链表长度大于 8 并且 hash 桶...

    一个优秀的废人
  • Debug HashMap

    最近跟两个正在找工作的同学聊天,说起集合,都是面试的重灾区,必问的选项,而且在实际的面试中并不会单独提问某一个问题,而是围绕核心知识连环炮提问。所以背面试题治标...

    Noneplus
  • HashMap都在用,原理你真的了解吗?

    以jdk1.8为例,hashMap是继承了AbstractMap抽象类,而AbstractMap抽象类是实现了Map接口的。Map是jdk中util工具集合系列...

    刘文正
  • HashMap源码阅读

    HashMap是Map家族中使用频度最高的一个,下文主要结合源码来讲解HashMap的工作原理。 1. 数据结构 HashMap的数据结构主要由数组+链表+红黑...

    butterfly100
  • Java 8系列之重新认识HashMap

    作者:美团点评技术团队 链接:https://zhuanlan.zhihu.com/p/21673805 来源:知乎 著作权归作者所有。商业转载请联系作者...

    bear_fish
  • Java集合类原理实现

    在java中所有的数据结构都可以使用数组和指针即引用来实现。而Hash也成散列,就是一个链表加数组实现。

    石的三次方
  • HashMap详解

    HashMap详解

    Java架构师必看
  • HashMap详解

    JDK1.8对HashMap底层的实现进行了优化,引入红黑树的数据结构和扩容的优化。 Java为数据结构中的映射定义了一个接口java.util.Map,此接...

    Java架构师必看
  • HashMap的源码解析

    今天学习了基于JDK1.8的HashMap的源码,主要从如下几个方面来阐述,HashMap的数据结构,HashMap如何支持动态扩容,HashMap的散列函数是...

    码农飞哥
  • Java程序员面试之HashMap

    JAVA中的基础HashMap在工作中使用的频率极高。相信很多同学在平时面试的时候经常被问到晕,今天我们来聊一下HashMap中常见的面试题吧!

    Rookie
  • JDK1.8源码分析之HashMap

    HashMap是一种Map,HashMap仅是一种Map的实现版本,下面的图片展示了java中Map的一些实现版本:

    九州暮云
  • HashMap简易版

    偶然间翻到了自己之前在学校时,倒腾的HashMap源码,当初自己通过断点一点点的分析了jdk1.7中HashMap的一些逻辑,感觉1.7的源码还是比较简单清晰一...

    敲得码黛
  • 基于JDK8的HashMap详解

    HashMap是程序员使用频率较高的一种用于映射(键值对)处理的数据类型,随着JDK(Java Development Kit)版本的更新,HashMap也在不...

    Java阿呆
  • Java并发-20.ConcurrentHashMap

    悠扬前奏
  • 集合源码解析之HashMap(基于Java8)1 概述2 HashMap的数据结构三大集合与迭代子3 源码分析单线程rehash多线程并发下的rehashFast-fail

    JavaEdge
  • Java集合源码解析 - HashMap

    HashMap是基于哈希表实现的,每一个元素是一个key-value对,其内部通过单链表解决冲突问题,容量不足(超过了阀值)时,同样会自动增长.

    JavaEdge
  • JDK1.8源码(七)——java.util.HashMap 类

      本篇博客我们来介绍在 JDK1.8 中 HashMap 的源码实现,这也是最常用的一个集合。但是在介绍 HashMap 之前,我们先介绍什么是 Hash表。...

    IT可乐

扫码关注云+社区

领取腾讯云代金券