Strange, why is the ArrayList initialization capacity size 10?

background

see ArrayList Source code , Come across ArrayList The initialization capacity of is 10, This is strange ！ We all know ArrayList and HashMap The bottom layer is based on arrays , What is it for? ArrayList It's not like using HashMap Use that way 16 As the initial capacity , instead 10 Well ？

So all parties look for information , This problem is proved , This article will tell you about .

Why? HashMap The initialization capacity of is 16？

Talking about ArrayList When initializing the capacity of , Let's review it first HashMap The initialization capacity of . Here we use Java 8 Source code for example ,HashMap There are two related factors in ： Initialize capacity and load 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;

stay HashMap among , The default initialization capacity of the array is 16, When the data is filled to the default capacity 0.75 when , It will 2 Double expansion . Of course , The user can also pass in the specified size during initialization . But it should be noted that , It is best to 2 Of n The value of the power , If not set to 2 Of n Power ,HashMap It will also be converted , Instead, there is one more step .

About HashMap The content of the implementation principle of , No more details here , There are too many articles about this on the Internet . One thing we need to know is HashMap Calculation Key The algorithm of value coordinates , That is, by right Key Value for Hash, And then map to the coordinates in the array .

here , Guarantee HashMap Is the capacity of the 2 Of n Power , So in hash During operation, the memory can be directly operated by bit operation , No need to convert to decimal , More efficient .

Usually , It can be said that ,HashMap The reason why 2 Of n Power , At the same time, the default value is 16, There are the following considerations ：

• Reduce hash Collision ;
• Improve Map The query efficiency ;
• The allocation is too small to prevent frequent capacity expansion ;
• Excessive allocation wastes resources ;

All in all ,HashMap The reason why 16 As default , To reduce hash Collision , At the same time, improve efficiency .

ArrayList The initialization capacity of is 10 Do you ？

below , Let's make sure ArrayList Is the initialization capacity of 10, Then we are discussing why this value is .

First look at it. Java 8 in ,ArrayList Initialization capacity of the source code ：

/**
 * 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.

from JDK1.7 Start , Initializing ArrayList When , 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;
    }

A friend here must say ,Java 8 in ArrayList The default initialization size is 0, No 10. You will also find that there are some strange comments on the constructor ： Construct an initial capacity 10 Empty list of . What the hell? ？ It's empty ！

Keep the question , Let's take a look first ArrayList Of add Method ：

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

stay add Method is called ensureCapacityInternal Method , Entering this method starts with an empty container, so size=0 Incoming minCapacity=1：

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

In the above method, first pass calculateCapacity To calculate capacity ：

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

Will find minCapacity It's reassigned to zero 10 （DEFAULT_CAPACITY=10）, Pass in ensureExplicitCapacity(minCapacity); this minCapacity=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);
    }

In the above code grow Method is used to handle capacity expansion , Expand the capacity to the original 1.5 times .

Understand the above process , We will find that , Essentially ArrayList The initialization capacity of is still 10, It's just lazy loading , This is a Java 8 Optimization to save memory . therefore , From beginning to end ,ArrayList The initialization capacity of is 10.

Here's more about the benefits of lazy loading , When there are thousands of ArrayList In the program ,10 The default size of objects means that the underlying array is allocated at creation time 10 A pointer to the （40 or 80 byte ） And fill them with null values , An empty array （ Fill... With null values ） Take up a lot of memory . If you can delay initializing the array , Then you can save a lot of memory space .Java 8 The change of is for the above purpose .

Why? ArrayList The initialization capacity of is 10？

Last , Let's discuss why ArrayList The initialization capacity of is 10. Actually , It can be said that there is no reason , Namely “ Feeling ”10 Good , modest , It is just fine , bond between performer and audience ！

First , In the discussion HashMap When , We said to the HashMap The reason for choosing 2 Of n Power , More considering hash The performance and collision of the algorithm . This question is about ArrayList There is no such thing as .ArrayList Just a simple growth array , There is no need to consider the optimization at the algorithm level . As long as it exceeds a certain value , Just grow . therefore , In theory ArrayList Is any positive value .

ArrayList The document does not explain why 10, But it is very likely that the best match between performance loss and space loss .10, Not very much , Not very small , Not wasting too much memory space , It won't lose too much performance .

If you have to ask why you chose 10, Maybe just ask the author of this code “Josh Bloch” Is that right .

If you look closely , There are also some other interesting initialization capacity numbers ：

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

ArrayList And Vector The initialization capacity is the same , by 10;HashSet、HashMap The initialization capacity is the same , by 16; and HashTable Use alone 11, Another interesting question .

Summary

There are many problems for which there is no clear reason 、 A definite answer . It's like a girl has no feelings for you , Maybe it's because you're not good enough , Or she may have fallen in love with someone else , But there's also a good chance that you won't know the answer . But in the process of finding the reason and the answer , I can still learn a lot , Growing up a lot . No contrast, no harm , such as HashMap And ArrayList Comparison of , Without comparison, we don't know whether it is suitable , Also like HashMap And ArrayList. Of course , You can also try something unique HashTable, Maybe it suits you .

About bloggers ：《SpringBoot Technology insider 》 Technical book author , Love to study technology , Write technical dry goods articles .

official account ：「 New perspective of procedure 」, The official account of bloggers , Welcome to your attention ~

Technical communication ： Please contact blogger wechat ：zhuan2quan

---

“ New perspective of procedure ”, One 100% Technical dry cargo official account

---