ArrayList相关问题

设定初始化容量new一个list

List<String> list = new ArrayList<>(10);

list.add(“s”);

进入构造方法

//属性elementData，ArrayList就是一个数组

transient Object[] elementData;

public ArrayList(int initialCapacity) {

        //没啥特殊的，容量大于0就直接定义个initialCapacity长度的数组，赋值给initialCapacity

        if (initialCapacity > 0) {

            this.elementData = new Object[initialCapacity];

        } else if (initialCapacity == 0) {

            //参数为0，直接给elementData赋值空的数组

            this.elementData = EMPTY_ELEMENTDATA;

        } else {

            //小于0，抛异常

            throw new IllegalArgumentException("Illegal Capacity: "+

                                               initialCapacity);

        }

    }

进入 add()---> 参数为泛型类型，也就是elementData数组中元素类型

public boolean add(E e) {

    //计数器，开始为0

    modCount++;

    add(e, elementData, size);

    return true;

}

直接进入add(e, elementData, size)
- elementData是一个空的数组，长度为10
- size现在应该是0 没有被赋值

- 进入三个参数的add()

private void add(E e, Object[] elementData, int s) {

//可以知道，s指的就是数组的索引

if (s == elementData.length)

//如果索引刚好等于数组长度，那么需要扩容！

elementData = grow();

//否则，直接在数组s索引的位置，赋值e

elementData[s] = e;

//索引 + 1

size = s + 1;

- 到这里，添加目测应该是结束了，进入`grow()`看看写了什么东西

private Object[] grow() {

return grow(size + 1);

}

- 继续进入`grow(size + 1)`，注意：传入参数为初始化容量 +1 ，在本例中为 11

private Object[] grow(int minCapacity) {

return elementData = Arrays.copyOf(elementData,

newCapacity(minCapacity));

}



- 不难发现，其实扩容操作就是针对elementData 属性

- 将此数组容量经过`newCapacity`()，形成一个扩容后新的数组，赋值给原数组！

- 那么扩容了多少呢？

- 进入`newCapacity(minCapacity)`

private int newCapacity(int minCapacity) {

// overflow-conscious code

//oldCapacity赋值为原数组长度 = 10

int oldCapacity = elementData.length;

//oldCapacity + oldCapacity /2 = 1.5 * oldCapacity

//newCapacity = 15

int newCapacity = oldCapacity + (oldCapacity >> 1);

//出现意外了！newCapacity 明明是1.5倍的newCapacity

//为什么 <= newCapacity 了，如下2种情况！

if (newCapacity - minCapacity <= 0) {

    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)

        //情况1，数组为空，即newCapacity = 0

        //返回常量 DEFAULT_CAPACITY 10

        return Math.max(DEFAULT_CAPACITY, minCapacity);

    if (minCapacity < 0) // overflow

        //入参 < 0 ，抛异常

        throw new OutOfMemoryError();

    return minCapacity;

}

//判断 newCapacity  是不是特别大(大到只比最大的Integer小8)

//是的话，就进入hugeCapacity() ，不做讨论

//正常的话，直接返回一个newCapacity

return (newCapacity - MAX_ARRAY_SIZE <= 0)

    ? newCapacity

    : hugeCapacity(minCapacity);

}



- 那么问题来了，为什么扩容之前，要size+1，在本例中，入参为11

`int newCapacity = oldCapacity + (oldCapacity >> 1);`

    - 采用如上方式计算新的容量，在于 >> 1

    - 也就是转成二进制之后右移1

    - 对于1,3,5,7等奇数，二进制最后一位是 1 ，右移后末尾的1直接没了

    - 所以要 +1，使其变成偶数，在乘1.5

    - 本例中，10+1变成11，右移，得到5

    - 如果是9，变成10后，右移，得到5

- 综上，若参数为`m`，实际扩容的容量数值 = m=奇数 ？ m+1 * 1.5 : m*1.5！

巴特西

ArrayList相关问题

设定初始化容量new一个list

最新文章

热门文章