HashMap 扩容加载因子

2022-11-24 15:31:29

HashMap：

public HashMap(int initialCapacity, float loadFactor) {

    //初始容量不能<0

    if (initialCapacity < 0)

        throw new IllegalArgumentException("Illegal initial capacity: "

                + initialCapacity);

    //初始容量不能 > 最大容量值，HashMap的最大容量值为2^30

    if (initialCapacity > MAXIMUM_CAPACITY)

        initialCapacity = MAXIMUM_CAPACITY;

    //负载因子不能 < 0

    if (loadFactor <= 0 || Float.isNaN(loadFactor))

        throw new IllegalArgumentException("Illegal load factor: "

                + loadFactor);

    // 计算出大于 initialCapacity 的最小的 2 的 n 次方值。

    int capacity = 1;

    while (capacity < initialCapacity)

        capacity <<= 1;

    this.loadFactor = loadFactor;

    //设置HashMap的容量极限，当HashMap的容量达到该极限时就会进行扩容操作

    threshold = (int) (capacity * loadFactor);

    //初始化table数组

    table = new Entry[capacity];

    init();

}

在这里提到了两个参数：初始容量，加载因子。

这两个参数是影响HashMap性能的重要参数，其中容量表示哈希表中桶的数量，初始容量是创建哈希表时的容量，

加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。

对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；

如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。系统默认负载因子为0.75，一般情况下我们是无需修改的。

加载因子：

loadFactor

扩容：

void addEntry(int hash, K key, V value, int bucketIndex) {

    Entry<K,V> e = table[bucketIndex];

        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);

        if (size++ >= threshold) // 这里是关键，一旦大于等于threshold的数值

            resize(2 * table.length); // 将会引起容量2倍的扩大

    }

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); // 复制数据过去

        table = newTable;

        threshold = (int)(newCapacity * loadFactor); // 重新计算threshold的值

    }

void transfer(Entry[] newTable) {

         // 保留原数组的引用到src中，

         Entry[] src = table;

         // 新容量使新数组的长度

         int newCapacity = newTable.length;

 　　　　　// 遍历原数组

         for (int j = 0; j < src.length; j++) {

             // 获取元素e

             Entry<K,V> e = src[j];

             if (e != null) {

                 // 将原数组中的元素置为null

                 src[j] = null;

                 // 遍历原数组中j位置指向的链表

                 do {

                     Entry<K,V> next = e.next;

                     // 根据新的容量计算e在新数组中的位置

                     int i = indexFor(e.hash, newCapacity);

                     // 将e插入到newTable[i]指向的链表的头部

                     e.next = newTable[i];

                     newTable[i] = e;

                     e = next;

                 } while (e != null);

             }

         }

     }