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

原创

用户7365393

修改于 2021-10-08 15:20:36

6850

修改于 2021-10-08 15:20:36

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();
        }
    }

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

java