What is the reason why the initial capacity of ArrayList in Java is 10?

Why is the initial capacity of HashMap 16?

When talking about the initialization capacity of ArrayList, we must first review the initialization capacity of HashMap. Here is the Java 8 source code as an example. There are two relevant factors in HashMap: initialization capacity and loading factor:

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

In HashMap, the default initialization capacity of the array is 16. When the data is filled to 0.75 of the default capacity When, it will be expanded by 2 times. Of course, users can also pass in the specified size during initialization. However, it should be noted that it is best to use a value of 2 to the nth power. If it is not set to 2 to the nth power, HashMap will also convert it, but it will require one more step.

Regarding the implementation principle of HashMap, I will not go into details here. There are already too many articles on the Internet about this. One thing we need to know is the algorithm of HashMap to calculate the key value coordinates, that is, by hashing the key value and then mapping it to the coordinates in the array.

At this time, ensure that the capacity of HashMap is 2 to the nth power, then bit operation can be used to directly operate the memory during hash operation without conversion to decimal, and the efficiency will be higher.

Generally, it can be considered that the reason why HashMap uses 2 to the nth power and the default value is 16, has the following considerations:

• Reduce hash collisions;

• Improve Map query efficiency;

• Allocation is too small to prevent frequent expansion;

• Excessive allocation wastes resources;

In short, the reason why HashMap uses 16 as the default value is to reduce hash collisions and improve efficiency.

Is the initial capacity of ArrayList 10?

Next, let’s first confirm whether the initial capacity of ArrayList is 10, and then discuss why it is this value.

Let’s first take a look at the source code of ArrayList initialization capacity in Java 8:

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

Obviously, the default container initialization value is 10. And from JDK1.2 to JDK1.6, this value is always 10.

Starting from JDK1.7, when initializing ArrayList, the default value is initialized to an empty array:

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

There must be friends here who say that the default value of ArrayList in Java 8 The initial size is 0, not 10. And you will also find something strange about the comments on the constructor method: construct an empty list with an initial capacity of 10. What the hell? It's obviously empty!

Reserve your doubts, let’s take a look at the add method of ArrayList first:

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

The ensureCapacityInternal method is called in the add method. When entering this method, it is an empty container at the beginning, so size=0Incoming minCapacity=1:

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

In the above method, the capacity is first calculated by calculateCapacity:

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

will find minCapacity is reassigned to 10 (DEFAULT_CAPACITY=10), pass in ensureExplicitCapacity(minCapacity);ThisminCapacity=10,

The following is the method body:

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    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);
    }

The grow method in the above code is used to handle expansion, expanding the capacity to 1.5 times the original size.

Understanding the above processing flow, we will find that essentially the initial capacity of ArrayList is still 10, but it just uses lazy loading. This is an optimization performed by Java 8 to save memory. Therefore, from beginning to end, the initial capacity of ArrayList is 10.

Let me mention one more benefit of lazy loading. When there are thousands of ArrayLists in the program, the default size of 10 objects means that 10 pointers (40 or 80) are allocated to the underlying array when created. bytes) and fill them with null values, an empty array (filled with null values) takes up a lot of memory. If you can lazily initialize an array, you can save a lot of memory space. The changes in Java 8 are for the above purpose.

Why is the initial capacity of ArrayList 10?

Finally, let’s discuss why the initial capacity of ArrayList is 10. In fact, it can be said that there is no reason, it just "feels" good, not too big, not too small, just right for the eyes!

First of all, when discussing HashMap, we said that the reason why HashMap chooses 2 to the nth power is more to consider the performance and collision of the hash algorithm. This problem does not exist for ArrayList. ArrayList is just a simple growing array, without considering optimization at the algorithm level. As long as it exceeds a certain value, it can grow. Therefore, theoretically speaking, the capacity of ArrayList can be any positive value.

The ArrayList documentation does not explain why 10 was chosen, but it is most likely due to the consideration of the best match between performance loss and space loss. 10. It’s not too big, not too small, it won’t waste too much memory space, and it won’t compromise too much performance.

If you have to ask why 10 was chosen in the first place, you may have to ask the author of this code "Josh Bloch".

If you observe carefully, you will also find some other interesting initialization capacity numbers:

ArrayList-10
Vector-10
HashSet-16
HashMap-16
HashTable-11

The initialization capacity of ArrayList is the same as that of Vector, which is 10; the initialization capacity of HashSet and HashMap Same, it is 16; and HashTable uses 11 alone, which is another very interesting question.

The above is the detailed content of What is the reason why the initial capacity of ArrayList in Java is 10?. For more information, please follow other related articles on the PHP Chinese website!