文章目录

今天,来分享下 HashMap 动态扩容机制。

基于 JDK 7 进行源码分析。

HashMap 初始容量大小是 16,负载因子是 0.75。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
static final float DEFAULT_LOAD_FACTOR = 0.75f;

当向 HashMap 添加对象时,会计算容量是否适当。

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

其中,最核心的方法是 addEntry(int hash, K key, V value, int bucketIndex)。如果 size 超过 threshold,则进行动态扩容,新容量扩大到原容量的 2 倍

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

请读者思考,什么时候进行扩容呢?实际上,当达到 容量大小 x 负载因子的元素个数时,就会进行扩容。而 threshold 的值就是容量大小 x 负载因子的元素个数。因此,第一次元素个数达到 12 时,把新容量扩大到原容量的 2 倍,新容量为 32。

public HashMap(Map<? extends K, ? extends V> m) {
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                  DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
    inflateTable(threshold);

    putAllForCreate(m);
}
private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    int capacity = roundUpToPowerOf2(toSize);
    // threshold = 容量大小 * 负载因子
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}
(完)

微信公众号

文章目录