欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

HashMap JDK7 扩容机制 和 ConcurrentmodificationException 异常

程序员文章站 2022-03-22 10:23:09
JDK7扩容机制HashMap扩容的目的:让链表缩短在往hashmap里面 put 数据时,hashmap会根据自己内部的逻辑进行扩容当map中元素的个数 size 大于他的阈值( capacity * LoadFacter => 数组大小 * 负载系数 ),并且当前索引所在位置不为null 才进行扩容 ,扩容是成二倍扩容 void addEntry(int hash, K key, V value, int bucketIndex) { if ((size.....

JDK7扩容机制

HashMap扩容的目的:让链表缩短

在往hashmap里面 put 数据时,hashmap会根据自己内部的逻辑进行扩容

map中元素的个数 size 大于他的阈值( capacity * LoadFacter   => 数组大小 * 负载系数 ),并且当前索引所在位置不为null 才进行扩容 ,扩容是成二倍扩容

    void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

Hashmap resize方法

    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

从代码中可以看到,如果原有的 table 达到了上限,就不能在继续扩容

如果还未达到上限就会调用 transfer 方法

    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                // 如果生成了hashseed 就重新进行hash
                // 基本上默认 false 
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

transfer 方法就是把原本 table中的元素 转移到 扩容后的 table 中,使用头插法,也就是说,新table中链表的顺序和旧列表中是相反的,在HashMap线程不安全的情况下,这种头插法可能会导致环状节点

在转移table,原有 table 的每个元素所对应的索引,在扩容后的 newTable 中可能会发生改变,因为在 table 扩容后,根据hashcode计算索引的 indexFor方法 中的 h 也会发生改变,二进制位高位会增加一位,但是即便发生改变,该索引也是有规律的,原有的索引上的元素,只会在 原索引 或 愿索引+扩容大小 所对应的索引上。

indexFor方法

    static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1);
    }

注意:这种逆序的扩容方式在多线程时有可能出现环形链表,出现环形链表的原因大概是这样的:线程1准备处理节点,线程二把HashMap扩容成功,链表已经逆向排序,那么线程1在处理节点时就可能出现环形链表

     并发下产生环形链表(死循环)的原因

 

HashMap  resize方法里的 initHashSeedAsNeeded(newCapacity)方法

    /**
     * Initialize the hashing mask value. We defer initialization until we
     * really need it.
     */
    final boolean initHashSeedAsNeeded(int capacity) {
        boolean currentAltHashing = hashSeed != 0;
        boolean useAltHashing = sun.misc.VM.isBooted() &&
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        boolean switching = currentAltHashing ^ useAltHashing;
        if (switching) {
            hashSeed = useAltHashing
                ? sun.misc.Hashing.randomHashSeed(this)
                : 0;
        }
        return switching;
    }

这个方法,判断 capacity的这个值,根据我所获取到的值来判断需不需要生成hashseed,

当 capacity的值大于某个值时,就生成一个hashseed,让hash算法的散列性,更高一点,如果不知道,则hashseed为默认值 Integer.MAX_VALUE

hashseed 的作用,让hash算法更加的复杂,让所得到的hash值更加散列

 

ConcurrentmodificationException异常

       Concurrentmodification

 

 

 

 

 

 

 

本文地址:https://blog.csdn.net/qq_41965731/article/details/109565811

相关标签: Java基础