JDK13源码学习笔记——ArrayList

  • 时间:
  • 浏览:0
  • 来源:跟我学网络

JDK版本:13

1 类图

1.1 实现接口

  • java.util.List:提供增删改查等基本操作
  • java.io.Serializable:标记接口,表示支持序列化
  • java.lang.Cloneable:标记接口,表示支持克隆
  • java.util.RandomAccess:这个接口可能很少注意到,其实也是一个标记接口,表示能够随机访问元素,简单来说就是底层是数组实现的集合。参考:RandomAccess 这个空架子有何用?

1.2 继承

  • java.util.AbstractList:抽象类,从注释中可以看到,它提供了List接口的基本实现,以最大程度地减少迭代遍历相关操作的实现。不过ArrayList基本都重写了AbstractList提供的实现。

2 属性

  • int elementData:储存元素的数组,ArrayList的真实大小
  • int sizeelementData中实际存放元素的数量,我们经常调用的size()方法返回的也就是它

3 构造方法

3.1 ArrayList(int initialCapacity)

    
    private static final Object[] EMPTY_ELEMENTDATA = {};
    
    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);
        }
    }

尽量预估数组大小,使用该方法创建ArrayList,合理使用内存,避免数组扩容耗费性能。

3.2 ArrayList()

    
    private static final int DEFAULT_CAPACITY = 10;
    
    
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

3.3 ArrayList(Collection<? extends E> c)

    
    public ArrayList(Collection<? extends E> c) {
        
        elementData = c.toArray();
        
        if ((size = elementData.length) != 0) {
            
            
            
            
            
            
            
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        
        } else {
            this.elementData = EMPTY_ELEMENTDATA;
        }
        
        
    }
    

4 主要方法

4.1 添加一个元素

boolean add(E e) 添加到尾部
    
    public boolean add(E e) {
        
        modCount++;
        add(e, elementData, size);
        return true;
    }
    
    private void add(E e, Object[] elementData, int s) {
        
        if (s == elementData.length)
            elementData = grow();
        
        elementData[s] = e;
        
        size = s + 1;
    }
    
void add(int index, E element) 添加到指定位置
    
    public void add(int index, E element) {
        
        rangeCheckForAdd(index);
        
        modCount++;
        final int s;
        Object[] elementData;
        
        if ((s = size) == (elementData = this.elementData).length)
            elementData = grow();
        
        
        System.arraycopy(elementData, 
                         index, 
                         elementData, 
                         index + 1, 
                         s - index); 
        
        elementData[index] = element;
        
        size = s + 1;
    }

4.2 扩容

Object[] grow()
    private Object[] grow() {
        
        return grow(size + 1);
    }
    
    
    private Object[] grow(int minCapacity) {
        
        int oldCapacity = elementData.length;
        
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, 
                    oldCapacity >> 1           );
            
            return elementData = Arrays.copyOf(elementData, newCapacity);
            
        
        } else {
            
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }

4.3 添加多个元素

boolean addAll(Collection<? extends E> c) 向末尾添加
    
    public boolean addAll(Collection<? extends E> c) {
        
        Object[] a = c.toArray();
        
        modCount++;
        
        int numNew = a.length;
        
        if (numNew == 0)
            return false;
        Object[] elementData;
        final int s;
        
        if (numNew > (elementData = this.elementData).length - (s = size))
            elementData = grow(s + numNew);
        
        System.arraycopy(a, 0, elementData, s, numNew);
        
        size = s + numNew;
        return true;
    }
boolean addAll(int index, Collection<? extends E> c) 向指定位置添加
    public boolean addAll(int index, Collection<? extends E> c) {
        
        rangeCheckForAdd(index);

        Object[] a = c.toArray();
        modCount++;
        int numNew = a.length;
        if (numNew == 0)
            return false;
        Object[] elementData;
        final int s;
        
        if (numNew > (elementData = this.elementData).length - (s = size))
            elementData = grow(s + numNew);

        int numMoved = s - index;
        
        if (numMoved > 0)
            System.arraycopy(elementData, index,
                             elementData, index + numNew,
                             numMoved);
        
        System.arraycopy(a, 0, elementData, index, numNew);
        size = s + numNew;
        return true;
    }

4.4 移除单个元素

E remove(int index) 移除指定位置的元素,并返回该元素
    public E remove(int index) {
        
        Objects.checkIndex(index, size);
        final Object[] es = elementData;

        
        @SuppressWarnings("unchecked") E oldValue = (E) es[index];
        fastRemove(es, index);
        
        return oldValue;
    }

    
    private void fastRemove(Object[] es, int i) {
        
        modCount++;
        final int newSize;
        
        
        if ((newSize = size - 1) > i) 
            System.arraycopy(es, i + 1, es, i, newSize - i);
        
        es[size = newSize] = null;
    }
boolean remove(Object o) 移除首个为o的元素,返回是否移除
    public boolean remove(Object o) {
        final Object[] es = elementData;
        final int size = this.size;
        
        int i = 0;
        found: { 
            
            if (o == null) {
                for (; i < size; i++)
                    if (es[i] == null)
                        break found;
            
            } else {
                for (; i < size; i++)
                    if (o.equals(es[i]))
                        break found;
            }
            return false;
        }
        
        fastRemove(es, i);
        return true;
    }

4.5 移除多个元素

boolean removeAll(Collection<?> c) 如果元素在集合 c 中就移除
    
    public boolean removeAll(Collection<?> c) {
        
        return batchRemove(c, false, 0, size);
    }
boolean batchRemove(Collection<?> c, boolean complement, final int from, final int end) 批量移除或保留元素

这个方法有点绕。先来看参数 complement,它表示如果一个元素在集合c中,他是保留还是删除。结合另一个方法

public boolean retainAll(Collection<?> c) { return batchRemove(c, true, 0, size); } 就很容易理解了,当complementfalse时,是移除的逻辑。而为true时,是求两个集合的交集。

这个方法的大致逻辑是:(以移除为例)先找到第一个要移除的元素索引,记为w,它的下一位记为r。然后从r的位置开始遍历,如果是要删除的元素就跳过,如果是要保留的元素,就将它写到w指向的位置,覆盖之前的元素,再把w挪向下一位,继续遍历判断。最后再把数组末尾无用的元素置为null。下文代码后我贴了一张手绘图,可以结合起来理解。或者debug调试几次。


    boolean batchRemove(Collection<?> c, boolean complement,
                        final int from, final int end) {
        
        Objects.requireNonNull(c);
        final Object[] es = elementData;
        int r;
        
        
        
        for (r = from;; r++) {
            if (r == end)
                return false;
            if (c.contains(es[r]) != complement)
                break;
        }
        
        int w = r++; 
        try {
            for (Object e; r < end; r++)
                
                
                if (c.contains(e = es[r]) == complement)
                    es[w++] = e;
        } catch (Throwable ex) {
            
            
            
            
            System.arraycopy(es, r, es, w, end - r);
            w += end - r;
            
            throw ex;
        } finally {
            
            modCount += end - w;
            
            shiftTailOverGap(es, w, end);
        }
        return true;
    }
    
    
    private void shiftTailOverGap(Object[] es, int lo, int hi) {
        
        System.arraycopy(es, hi, es, lo, size - hi);
        
        for (int to = size, i = (size -= hi - lo); i < to; i++)
            es[i] = null;
    }

批量移除给定范围内的多个元素 void removeRange(int fromIndex, int toIndex)
    
    protected void removeRange(int fromIndex, int toIndex) {
        
        if (fromIndex > toIndex) {
            throw new IndexOutOfBoundsException(
                    outOfBoundsMsg(fromIndex, toIndex));
        }
        
        modCount++;
        
        shiftTailOverGap(elementData, fromIndex, toIndex);
    }
根据条件移除元素 boolean removeIf(Predicate<? super E> filter)

略…

4.6 查找单个元素

int indexOf(Object o) 查找第一个指定元素的索引
    public int indexOf(Object o) {
        return indexOfRange(o, 0, size);
    }

    int indexOfRange(Object o, int start, int end) {
        Object[] es = elementData;
        
        if (o == null) {
            for (int i = start; i < end; i++) {
                if (es[i] == null) {
                    return i;
                }
            }
        
        } else {
            for (int i = start; i < end; i++) {
                if (o.equals(es[i])) {
                    return i;
                }
            }
        }
        
        return -1;
    }
int indexOf(Object o) 查找最后一个指定元素的索引
    public int lastIndexOf(Object o) {
        return lastIndexOfRange(o, 0, size);
    }

    int lastIndexOfRange(Object o, int start, int end) {
        Object[] es = elementData;
        if (o == null) {
            for (int i = end - 1; i >= start; i--) { 
                if (es[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = end - 1; i >= start; i--) {
                if (o.equals(es[i])) {
                    return i;
                }
            }
        }
        return -1;
    }
int indexOf(Object o) 获得指定位置的元素
    public E get(int index) {
        
        Objects.checkIndex(index, size);
        return elementData(index);
    }
    
    E elementData(int index) {
        return (E) elementData[index];
    }

4.7 设置指定位置的元素

E set(int index, E element)
    public E set(int index, E element) {
        
        Objects.checkIndex(index, size);
        
        E oldValue = elementData(index);
        
        elementData[index] = element;
        
        return oldValue;
    }

5 其他方法

5.1 转换为数组

Object[] toArray() 转换为Object[]
    
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }
    
    
    public static <T> T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
    }
Object[] toArray() 转换为给定泛型的数组
    public <T> T[] toArray(T[] a) {
        
        if (a.length < size)
            
            
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        
        System.arraycopy(elementData, 0, a, 0, size);
        
        if (a.length > size)
            a[size] = null;
        return a;
    }

对中间a[size] = null的疑惑作者在方法注释中有写到:

     * <p>If the list fits in the specified array with room to spare
     * (i.e., the array has more elements than the list), the element in
     * the array immediately following the end of the collection is set to
     * {@code null}.  (This is useful in determining the length of the
     * list <i>only</i> if the caller knows that the list does not contain
     * any null elements.)

如果调用者明确知道数组中没有空元素,那么这对于确定list的length很有帮助。emmm…插入null值作为一个标记…或许调用者可以在遍历数组时判断元素为空就不再遍历了??

5.2 求哈希值

int hashCode()
    public int hashCode() {
        
        int expectedModCount = modCount;
        
        int hash = hashCodeRange(0, size);
        
        checkForComodification(expectedModCount);
        return hash;
    }

    int hashCodeRange(int from, int to) {
        final Object[] es = elementData;
        
        if (to > es.length) {
            throw new ConcurrentModificationException();
        }
        
        int hashCode = 1;
        for (int i = from; i < to; i++) {
            Object e = es[i];
            
            hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
        }
        return hashCode;
    }
    
    
    private void checkForComodification(final int expectedModCount) {
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

参考资料:田小波的技术博客——科普:String hashCode 方法为什么选择数字31作为乘子

5.3 判断相等

boolean equals(Object o)
    public boolean equals(Object o) {
        
        if (o == this) {
            return true;
        }

        
        if (!(o instanceof List)) {
            return false;
        }

        
        final int expectedModCount = modCount;
        
        
        
        
        boolean equal = (o.getClass() == ArrayList.class)
            ? equalsArrayList((ArrayList<?>) o)
            : equalsRange((List<?>) o, 0, size);
        
        checkForComodification(expectedModCount);
        return equal;
    }
    
    private boolean equalsArrayList(ArrayList<?> other) {
        
        final int otherModCount = other.modCount;
        final int s = size;
        boolean equal;
        
        if (equal = (s == other.size)) {
            final Object[] otherEs = other.elementData;
            final Object[] es = elementData;
            
            if (s > es.length || s > otherEs.length) {
                throw new ConcurrentModificationException();
            }
            
            for (int i = 0; i < s; i++) {
                if (!Objects.equals(es[i], otherEs[i])) {
                    equal = false; 
                    break;
                }
            }
        }
        
        other.checkForComodification(otherModCount);
        return equal;
    }
    
    boolean equalsRange(List<?> other, int from, int to) {
        final Object[] es = elementData;
        
        if (to > es.length) {
            throw new ConcurrentModificationException();
        }
        
        var oit = other.iterator();
        for (; from < to; from++) {
            
            if (!oit.hasNext() || !Objects.equals(es[from], oit.next())) {
                return false;
            }
        }
        
        return !oit.hasNext();
    }

5.4 克隆

Object clone()
    public Object clone() {
        try {
            
            ArrayList<?> v = (ArrayList<?>) super.clone();
            
            v.elementData = Arrays.copyOf(elementData, size);
            
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            
            
            throw new InternalError(e); 
        }
    }

5.5 清空

void clear()
    public void clear() {
        
        modCount++;
        
        final Object[] es = elementData;
        for (int to = size, i = size = 0; i < to; i++)
            es[i] = null;
    }

5.6 序列化与反序列化

void writeObject(java.io.ObjectOutputStream s) 序列化
    @java.io.Serial
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        int expectedModCount = modCount;
        
        s.defaultWriteObject();

        
        s.writeInt(size);

        
        
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }
        
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

elementData是加了transient关键字的,序列化时会只序列化size大小的真实使用的数组,不会序列化elementData预留出的那一部分。节省时间和空间。

void readObject(java.io.ObjectOutputStream s)
    @java.io.Serial
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {

        
        s.defaultReadObject();

        
        
        s.readInt(); 

        if (size > 0) {
            
            
            SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size);
            Object[] elements = new Object[size];

            
            for (int i = 0; i < size; i++) {
                elements[i] = s.readObject();
            }

            elementData = elements;
        } else if (size == 0) {
            
            elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new java.io.InvalidObjectException("Invalid size: " + size);
        }
    }

6 End

省略了一些不常用的或简单的方法,以及逻辑重点不在ArrayList中的方法(比如sort()排序)。