java arraylist源码记录

1. ArrayList 实现了RandomAccess接口, RandomAccess接口用于标记是否可以随机访问

2. 继承了AbstractList类, 因此获取了modcount , modcount用于实现快速失败机制, 如果list有修改, 那么modcount自增

3. ArrayList不支持并发, 是非线程安全的

4. 支持存放null元素

5. 扩容, 每次都是原来大小的1.5倍

public void ensureCapacity(int minCapacity) {
        //如果elementData不等于EMPTY_ELEMENTDATA(因为初始化时有可能等于), 那么minExpand为0或者DEFAULT_CAPACITY
        //如果elementData不为空minExpand为0, 可以用这个来处理minCapacity为负数的情况
        //如果elementData为空, 那么就是默认容量
        int minExpand = (elementData != EMPTY_ELEMENTDATA)
                // any size if real element table
                ? 0
                // larger than default for empty table. It's already supposed to be
                // at default size.
                : DEFAULT_CAPACITY;

        //如果最小容量大于minExpand, 那么进行明确扩容
        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

    //已确定扩容minCapacity
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++; //修改次数加1

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //newCapacity为oldCapacity的1.5倍, 这里有可能会溢出为-1
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        ....
    }

6. lastIndexOf, contains, indexOf方法用于查找, 时间复杂度均为O(N), 使用对象的equals方法进行比较
7. clone() 方法为深复制, 所谓深复制和浅复制的区别在于复制内部引用对象时的不同, 深复制会将原来的对象重新clone一份, 让复制对象的引用指向新对象, 而浅复制仅仅复制引用, 仍指向原来的对象. java Object中的clone方法为浅复制

8. set() 和 get() 为O(1)的时间复杂度

9. 调用ensureCapacityInternal(int) 会使modCount+1. ArrayList中的添加元素都会调用这个函数 ,例如add(object)和add(int,Object)

10. add(Object) 和add(int,Object)的时间复杂度为O(N), 因为底层数组的复制移动

11. remove(int)方法也会使modCount+1, 时间复杂度为O(N) , 同时内部使用elementData[--size] = null;用来防止内存泄漏, 以便gc释放内存

12. remove(Object) 使用了fastRemove非法, fastRemove如果未找到删除元素, 那么modCount是不会变的, 反之modCount+1 , 之所以fastRemove称之为fast是因为使用了System.arrayCopy进行元素移动, System.arrayCopy是一个native方法, 可以躲避java访问数组时的下标检查.

13. clear方法, modCount+1

14. addAll(...) 都会调用ensureCapacityInternal方法, 从而使modCount+1, O(N)的时间复杂度

15. removeAll(object)//补集和retainAll(object)//交集都可以使用batchRemove方法, O(N^2)的时间复杂度, modCount+1.

16. 快速失败机制体现在容器的遍历中, Iterator会在对象初始化过程中保存当前容器的modCount, 并在每次遍历检查modCount, 如果两者不一致, 那么说明容器在遍历时被修改, 抛出ConcurrentModificationException.

   private class Itr implements Iterator<E> {

        int expectedModCount = modCount;

        public E next() {
            checkForComodification();
            int i = cursor;
           ...
        }

        public void remove() {
           ...
            checkForComodification();

           ...
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }