Forum Stats

  • 3,722,191 Users
  • 2,244,246 Discussions
  • 7,849,699 Comments

Discussions

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

ArrayList Constructs initial capacity of ten?

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

initial capacity Should it actually be 0?


Best Answer

  • Patrycja Wegrzynowicz
    Patrycja Wegrzynowicz Member Posts: 4 Red Ribbon
    Accepted Answer

    The Javadoc comment is not entirely precise, however more or less true if we take into account the lazy initialisation.

    The initial capacity of ten is guaranteed lazily. During addition of a new element there is a check whether an array needs to grow. If the ArrayList object was constructed with a non-arg constructor, than the first addition will trigger the allocation of an array with DEFAULT_CAPACITY (10).

    /**
     * This helper method split out from add(E) to keep method
     * bytecode size under 35 (the -XX:MaxInlineSize default value),
     * which helps when add(E) is called in a C1-compiled loop.
     */
    private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }
    
    private Object[] grow(int minCapacity) {
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
    }
    
    private Object[] grow() {
        return grow(size + 1);
    }
    
    /**
     * Returns a capacity at least as large as the given minimum capacity.
     * Returns the current capacity increased by 50% if that suffices.
     * Will not return a capacity greater than MAX_ARRAY_SIZE unless
     * the given minimum capacity is greater than MAX_ARRAY_SIZE.
     *
     * @param minCapacity the desired minimum capacity
     * @throws OutOfMemoryError if minCapacity is less than zero
     */
    private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity <= 0) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }
    

    The rationale behind such a lazy initialisation is performance optimization: http://mail.openjdk.java.net/pipermail/core-libs-dev/2013-April/015585.html

    User_0Y5EK

Answers

  • Patrycja Wegrzynowicz
    Patrycja Wegrzynowicz Member Posts: 4 Red Ribbon
    Accepted Answer

    The Javadoc comment is not entirely precise, however more or less true if we take into account the lazy initialisation.

    The initial capacity of ten is guaranteed lazily. During addition of a new element there is a check whether an array needs to grow. If the ArrayList object was constructed with a non-arg constructor, than the first addition will trigger the allocation of an array with DEFAULT_CAPACITY (10).

    /**
     * This helper method split out from add(E) to keep method
     * bytecode size under 35 (the -XX:MaxInlineSize default value),
     * which helps when add(E) is called in a C1-compiled loop.
     */
    private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }
    
    private Object[] grow(int minCapacity) {
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
    }
    
    private Object[] grow() {
        return grow(size + 1);
    }
    
    /**
     * Returns a capacity at least as large as the given minimum capacity.
     * Returns the current capacity increased by 50% if that suffices.
     * Will not return a capacity greater than MAX_ARRAY_SIZE unless
     * the given minimum capacity is greater than MAX_ARRAY_SIZE.
     *
     * @param minCapacity the desired minimum capacity
     * @throws OutOfMemoryError if minCapacity is less than zero
     */
    private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity <= 0) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }
    

    The rationale behind such a lazy initialisation is performance optimization: http://mail.openjdk.java.net/pipermail/core-libs-dev/2013-April/015585.html

    User_0Y5EK
Sign In or Register to comment.