[Java知识库]java ArrayList 底层逻辑源码分析

java ArrayList 底层逻辑源码分析

我认为ArrayList 是集合中源码最简单的集合；

创建对象，将数组对象赋值一个空的数组,并没给与给长度

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

添加一个元素

public boolean add(E e) {
		//将当前的数组长度+1，第一次创建size成员变量默认是0
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    //如果是第一次创建添加元素（刚new的对象） 那么返回初始值10（DEFAULT_CAPACITY）
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
    //不是第一次添加元素，返回是size+1 （数组实际存储元素个数+1）,
        return minCapacity;
    }

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
    	// 如果 size+1 > size  实际储存的个数+1> 数组的长度
        if (minCapacity - elementData.length > 0)
            //扩容
            grow(minCapacity);
    }

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
    	// 新的容量为 旧的容量+旧的容量的一半（扩容1/2）
        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:
    //将原来的数组复制在新的长度为 newCapacity的数组里面
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

删除元素：

public boolean remove(Object o) {
    //当对象是null的时候 删除null找到对应元素下标，删除该元素
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            //当对象不是null的时候，找到对应元素下标，删除该元素
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            //将删除的元素后面的数据往前复制一格
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
    	//最后一个数据其实是重复的，将其删除（赋值为null，无法关联到GCroot,会被清除）
        elementData[--size] = null; // clear to let GC do its work
    }

总结：

底层结构、如何添加数据、扩容？

数据结构是java中的数组类型Object[],因此创建数组后就数组长度就不能再改变，new ArrayList() 后，给数组的长度是0，也就是{}，只有当数组添加元素的时候会判断容量，进行扩容，起始容量是10，没有扩容因子，当数组中元素的个数+1大于原数组长度的时候，也就是数组完全满了才会进行扩容，扩容是以1/2的容量扩容，

当元素删除后，删除的元素后面的数据会往前复制，然后把最后的一个元素删掉，注意数组的长度不会改变，改变的是集合的长度