ArrayList及HashMap的扩容规则

你的名字 2022-08-18 15:25 198阅读 0赞

## 1、ArrayList ##

*  默认大小为10

/** * Default initial capacity. */
    private static final int DEFAULT_CAPACITY = 10;

*  最大容量为2^30 - 8

/** * The maximum size of array to allocate. * Some VMs reserve some header words in an array. * Attempts to allocate larger arrays may result in * OutOfMemoryError: Requested array size exceeds VM limit */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
    
    /** * A constant holding the maximum value an {@code int} can * have, 2<sup>31</sup>-1. */
    public static final int   MAX_VALUE = 0x7fffffff;

*  扩容规则为：oldCapacity\*1.5

/** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

## 2、HashMap ##

*  默认大小： 16

/** * The default initial capacity - MUST be a power of two. */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

*  最大容量为：2^30

/** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */
    static final int MAXIMUM_CAPACITY = 1 << 30;

*  扩容规则为：大于oldCapacity的最小的2的n次方整数

/**
     * Adds a new entry with the specified key, value and hash code to
     * the specified bucket.  It is the responsibility of this
     * method to resize the table if appropriate.
     *
     * Subclass overrides this to alter the behavior of put method.
     */
    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);
    }