ArrayList源码分析与手写

不念不忘少年蓝@ 2022-11-07 05:48 194阅读 0赞

本节主要分析JDK提供的ArrayList的源码，以及与自己手写的ArrayList进行对比。

# ArrayList源码分析 #

## 构造方法 ##

private static final int DEFAULT_CAPACITY = 10;
    
    private static final Object[] EMPTY_ELEMENTDATA = { };
    
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };
    
    transient Object[] elementData; // non-private to simplify nested class access
    
    private int size;
    
    public ArrayList(int initialCapacity) {  // 指定容量初始化
        if (initialCapacity > 0) { 
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) { 
            this.elementData = EMPTY_ELEMENTDATA;
        } else { 
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
    
    public ArrayList() { 
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // 默认初始化为空数组
    }
    
    public ArrayList(Collection<? extends E> c) {  // 通过集合构造ArrayList
        elementData = c.toArray();
        if ((size = elementData.length) != 0) { 
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else { 
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

JDK的ArrayList构造时默认初始化为空数组，而我手写的ArrayList默认初始化数组长度为`DEFAULT_CAPACITY`。

## add() ##

public boolean add(E e) { 
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    
    // 扩容
    private void ensureCapacityInternal(int minCapacity) { 
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    
    private static int calculateCapacity(Object[] elementData, int minCapacity) { 
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
            return Math.max(DEFAULT_CAPACITY, minCapacity); // 添加第一个元素时会将数组初始化为10
        }
        return minCapacity;
    }
    
    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); // 1.5倍扩容
        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); // 将旧数组元素复制到新数组中
    }
    
    public void add(int index, E element) { 
        rangeCheckForAdd(index);
    
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index); // 将index及后面的元素后移一位
        elementData[index] = element;
        size++;
    }

*  当添加第一个元素时会将数组容量初始化为10
 *  当元素个数大于数组长度时触发扩容，扩容后数组的长度为原来数组长度的1.5倍
 *  JDK的ArrayList使用的是`Arrays.copyOf`来移动或拷贝数组，效率更高

## indexOf() ##

public int indexOf(Object o) { 
        if (o == null) { 
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else { 
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

`indexOf()`中根据对象是否为空来进行遍历，而我手写的ArrayList是使用的`Objects.equals()`方法。

## remove() ##

public E remove(int index) { 
        rangeCheck(index);
    
        modCount++;
        E oldValue = elementData(index);
    
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    
        return oldValue;
    }

`remove()`需要将index后的元素前移一位。

# 手写ArrayList #

ArrayList底层是一个动态数组。

## 构造方法 ##

public static final int DEFAULT_CAPACITY = 10;
    
    private int size;
    
    private E[] elements;
    
    public ArrayList() { 
        this(DEFAULT_CAPACITY);
    }
    
    public ArrayList(int capacity) { 
        capacity = Math.max(capacity, DEFAULT_CAPACITY); // 让容量必须>=DEFAULT_CAPACITY，减少扩容次数
        elements = (E[]) new Object[capacity];
    }

默认构造方法会初始化数组的大小为10，也可以指定数组初始化的大小。

## size() && isEmpty() && clear() ##

public int size() { 
        return size;
    }
    
    public boolean isEmpty() { 
        return 0 == size;
    }
    
    public void clear() { 
        // 仅需要清除到size位置，后面没有元素，而不是elements.length
        for (int i = 0; i < size; i++) { 
            elements[i] = null;
        }
        size = 0;
    }

clear()方法要将数组的所有元素赋值为null，这样数组中的对象就会被垃圾回收器回收，释放内存，这里也可以考虑缩容。

## add() ##

public void add(E e) { 
        add(size, e);
    }
    
    public void add(int index, E e) { 
    
        rangeCheckForAdd(index);
        ensureCapacity(size + 1);
    
        // 索引从index至size-1的元素后移一位
        for (int i = size - 1; i >= index; i--) { 
            elements[i + 1] = elements[i];
        }
    
        elements[index] = e;
        size++;
    }
    
    // 添加的时候允许添加至size位置
    private void rangeCheckForAdd(int index) { 
        // 0<=index<=size
        if (index > size || index < 0) { 
            throw new IndexOutOfBoundsException();
        }
    }
    
    // 扩容
    private void ensureCapacity(int n) { 
        int oldCapacity = elements.length;
        if (n > oldCapacity) {  // 元素个数大于数组
            int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍扩容
            E[] newElements = (E[]) new Object[newCapacity];
    
            for (int i = 0; i < size; i++) { 
                newElements[i] = elements[i]; // 将旧数组的元素逐一拷贝至新数组
            }
    
            elements = newElements;
        }
    }

`add(E e)`在数组最后添加元素，时间复杂度为O(1)。`add(int index, E e)`在数组指定索引位置添加元素，因为需要将指定索引位置及后面的元素后移一位，时间复杂度为O(n)。

## set() ##

public void set(int index, E e) { 
        rangeCheck(index);
        elements[index] = e;
    }
    
    private void rangeCheck(int index) { 
        // 0<=index<size
        if (index >= size || index < 0) { 
            throw new IndexOutOfBoundsException();
        }
    }

`set()`通过数组下标随机访问元素，时间复杂度为O(1)。

## get() ##

public E get(int index) {
        rangeCheck(index);
        return elements[index];
    }

`get()`通过数组下标随机访问元素，时间复杂度为O(1)。

## indexOf() && lastIndexOf() ##

public int indexOf(E e) { 
        for (int i = 0; i < size; i++) { 
            if (Objects.equals(e, elements[i])) {  // Objects.equals处理了空和值相等的情况
                return i;
            }
        }
        return ELEMENT_NOT_FOUND;
    }
    
    public int lastIndexOf(E e) { 
        for (int i = size - 1; i >= 0; i++) { 
            if (Objects.equals(e, elements[i])) { 
                return i;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

`indexOf()`是从索引0开始往后查找指定元素，一旦找到立刻返回对应的索引，时间复杂度为O(n)。`lastIndexOf()`是从数组最后开始往前查找指定元素，一旦找到立刻返回对应的索引，时间复杂度为O(n)。

## contains() ##

public boolean contains(E e) { 
        return ELEMENT_NOT_FOUND != indexOf(e);
    }

`contains()`判断是否包含指定元素，时间复杂度为O(n)。

## remove() ##

public E remove(int index) { 
        rangeCheck(index);
    
        E oldValue = elements[index];
    
        // 索引从index+1至size-1的元素前移一位
        for (int i = index + 1; i < size; i++) { 
            elements[i - 1] = elements[i];
        }
        elements[--size] = null;
        return oldValue;
    }
    
    public boolean remove(E e) { 
        int index = indexOf(e);
    
        if (index == ELEMENT_NOT_FOUND) { 
            return false;
        }
    
        remove(index);
        return true;
    }

`remove(int index)`删除指定索引的元素，需要将索引后的元素往前移动一位，时间复杂度为O(n)。`remove(E e)`删除指定元素，需要先查找指定元素的索引，然后再将索引后的元素往前移动一位，时间复杂度为O(n)。

# 总结 #

*  ArrayList适合在数组最后添加元素，以及根据索引随机访问元素，如果要频繁的删除元素就不适合了。
 *  如果在创建ArrayList时知道存储的元素个数，就可以指定创建ArrayList的容量，这样就能减少扩容。