Dive into ArrayList


 

Dive into ArrayList

ArrayList源码阅读与分析

一. 继承体系

img

1.基于数组实现,是一个动态数组,其容量能自动增长。

2.ArrayList不是线程安全的,建议在单线程中使用,多线程可以选择Vector或CopyOnWriteArrayList。

3.实现了RandomAccess接口,可以通过下标序号进行快速访问

4.实现了Cloneable接口,能被克隆

5.实现了Serializable接口,支持序列化

二. 基本属性

/** 
 * 存储数组默认容量
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * 当使用 new ArrayList(0) 时赋值给elementData
 * 第一次插入元素时,将重新开辟一个容量为1的存储数组,该引用将被弃用
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * 当使用 new ArrayList() 时赋值给elementData
 * 第一次插入元素时,将重新开辟一个容量为10的存储数组,该引用将被弃用
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 *  该数组用来存放add进ArrayList的元素
 */
transient Object[] elementData; 

/**
 * 对象数组中已经存放的元素个数,并不是存储数组的容量
 */
private int size;

/**
 * 数组可开辟的最大容量,实际上一个数组所能分配的容量大小取决于JVM分配的堆内存大小
 * MAX_ARRAY_SIZE只是一个理论值,可能出于对JVM头信息存储的考虑而设计
 * 因为在hugeCapacity 方法中 minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE :
 *  MAX_ARRAY_SIZE;
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * 当前ArrayList对象被结构性修改的次数,结构性修改主要指的是对ArrayList对象
 * 的存储数组的元素个数的修改 
 */
protected transient int modCount = 0;

fail-fast 行为

该域被iterator和它的实现类(通过iterator和listIterator方法返回)所使用 在添加元素或者删除元素时,出于并发考虑,如果该域的值发生不可预期的变化, iterator或listIterator将抛出异常, 由于该域是protected的,所以ArrayList的子类可选择性地使用它,如果子类希望提供fail-fast 行为(或者说迭代行为),那么它只需在add方法和remove方法(或者其他任何会涉及到list的结构性变化的方法)中将该域增加。单独调用add或remove方法最多只能将该域递增一次,不然将会抛出异常,如果子类不希望 提供fail-fast 行为,直接忽略该域即可。

二. 构造方法

1. 无参构造

注释上说构造一个容量大小为 10 的空的ArrayList对象,但构造函数只是给 elementData 赋值了一个空的数组,真正将容量扩大至 10 是在第一次添加元素时。

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

2. 用指定容量构造

创建指定存储数组容量的ArrayList实例

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        //指定存储数组容量有效
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        //用容量为0的对象数组存储
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

3. 用 Collection 构造

当传递的参数为集合类型时,会把集合类型转化为数组类型,并赋值给elementData。

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // 当c.toArray 返回的不是Object[]时
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // 入参为空集合,用私有的空对象数组作为存储数组
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

三. 添加元素

1. add (E e)

将元素e追加到对象数组elementData后面

public boolean add(E e) {
    //确保存储elementData有足够容量将新加入元素e加进去
    ensureCapacityInternal(size + 1); 
    elementData[size++] = e;
    return true;
}

明确到底需要为存储数组分配多大的容量

如果存储数组是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 则在第一次往其中添加元素的时候将容量扩大为10,默认需要容量的是size + 1

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 判断元素数组是否为空数组
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); // 取较大值
    }
    ensureExplicitCapacity(minCapacity);
}

判断需要的容量时候超出存储数组分配的长度

如果容量指针size超过了最初分配的存储数组的分配的容量,将进行扩容;否则,表示原来的长度够用,只需将表示集合结构性修改次数加一,同时将size指针前移即可

private void ensureExplicitCapacity(int minCapacity) {
    //结构性修改的次数加1
    modCount++;

    // 扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

扩容(重新分配容量更大的数组)

oldCapacity :数组的当前的总容量

minCapacity: 目前需要多少容量

newCapacity :新分配的总容量,为旧容量的1.5倍

三者的关系: oldCapacity < minCapacity <= newCapacity <= Integer.MAX_VALUE

一般会重新开辟一个总容量为原存储数组容量的1.5倍的数组,但新分配的数组容量可能仍不够,这时因为minCapacity 肯定大于oldCapacity才需要扩容 ,所以干脆开辟容量为minCapacity 的数组,如果minCapacity 超出了上述定义的所谓“最大数组长度 (MAX_ARRAY_SIZE)” ,那么将调用hugeCapacity去判断hugeCapacity是否溢出,不溢出的话就开辟Integer.MAX_VALUE 大小容量的数组。

private void grow(int minCapacity) {
    // 旧总容量
    int oldCapacity = elementData.length; 
    // 新的总容量为旧总容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 分配的仍不够,直接将需要的容量设置为新容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    /** 
     * 新容量比最大数组容量大,调用hugeCapacity得到新的容量
     * 不溢出的话得到的是Integer.MAX_VALUE
     */
    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);
}

/**
 * 获取数组真正可以分配的最大容量 Integer.MAX_VALUE
 */ 
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // 溢出
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}

了解到扩容算法后,我们可以得出的经验是:在调用ArrayList的构造方法时,尽量选择一个比较合适的大小,因为如果给定的容量太大会造成不必要的内存浪费; 如果指定的容量太小,可能会导致频繁的扩容,在增加程序的复杂度的同时,因为扩容时用到了Arrays.copyOf方法

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType){
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

该方法会先创建一个新的数组copy,将原来的数组内容复制进copy,再将`copy返回,所以频繁地扩容也会造成一定地内存开销。

/**
 * 将Course集转为CourseVo集
 * @param courses Course集
 * @return CourseVo集
*/
private List<CourseVo> changeToVos(List<Course> courses) {
    if (courses != null && courses.size() > 0) {
        List<CourseVo> courseVos = new ArrayList<>(courses.size());
        for (Course course : courses) {
            courseVos.add(changeToVo(course));
        }
        return courseVos;
    }
    return null;
}

2. 其他 add 方法

add (int index, E element)

在特定的位置插入给定的元素,如果该位置右边有元素,则将这些元素右移

public void add(int index, E element) {
    // 检查index范围
    rangeCheckForAdd(index);
    /**
     * 判断 size + 1 是否超出 elementData 的容量,是的话重新分配一个更大容量的存储数组并将
     * elementData指向该数组,将原来的数据复制进去
     */
    ensureCapacityInternal(size + 1); 
    // 将index 右边的元素右移
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 插入元素
    elementData[index] = element;
    size++;
}

private void rangeCheckForAdd(int index) {
    // 不支持追加,追加还不如调用 add(E e)
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/**
 * java.lang.System中的 native 方法
 * 将elementData从(index, elementData.length) 的序列复制到 
 * elementData从(index + 1, size + 1)
 */
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

boolean addAll(Collection<? extends E> c)

将Collection中的所有元素以其用迭代器遍历返回的顺序追加到list后面,该方法未定义当Collection为当前list本身时的行为,默认也是可以的(list中没有null元素)。

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    
    /**
     * 判断 size + numNew 是否超出 elementData 的容量,是的话重新分配一个更大容量的存储数组并将
     * elementData指向该数组,将原来的数据复制进去
     */
    ensureCapacityInternal(size + numNew);  // modCount ++
    //将a[0,a.length] 复制到 elementData [size, number + size]
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

boolean addAll(int index, Collection<? extends E> c)

将Collection中的所有元素以它的迭代器迭代顺序插入指定位置,后面的所有元素右移

public boolean addAll(int index, Collection<? extends E> c) {
    // 检查index范围
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    
    /**
     * 判断 size + numNew 是否超出 elementData 的容量,是的话重新分配一个更大容量的存储数组并将
     * elementData指向该数组,将原来的数据复制进去
     */
    ensureCapacityInternal(size + numNew);  // modCount ++
    
    // 需要移动的元素个数
    int numMoved = size - index;
    
    /**
     * 将elementData[index, size-1] 复制到
     * elementData[index + numNew, index + numNew + numMoved]
     */
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);
    // 将a[0,a.length]复制到 elementData[index, index + numNew]
    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

四. 删除元素

boolean remove(Object o)

删除lsit中第一个出现的给定元素,如果不存在则无动作,逻辑非常简单

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        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)
        // 将elementData[index + 1, size - 1] 复制到elementData[index, size - 2]
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null;   // 将存储数组后面的单元置空,让GC处理
}

E remove(int index)

删除list中指定位置的元素,如果后面有元素则将之左移,返回删除的元素

public E remove(int index) {
    // 检查index范围
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);
    // 需要左移的元素个数
    int numMoved = size - index - 1;
    // 判断后面是否还有元素
    if (numMoved > 0)
        // 将elementData[index + 1, size - 1] 复制到elementData[index, size - 2]
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null;  // 将存储数组后面的单元置空,让GC处理
    // 返回需要删除的元素
    return oldValue;
}

// 简单地检查
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

可以看到void fastRemove(int index)E remove(int index) 基本一样,主要的区别在于没有做越界检查和返回删除值。

五. 查询和更改

因为ArrayList使用对象数组存储元素,所以获取元素与设置单元格的值都比较简单

public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

// 将 index 处的值设置为 element,返回原来的元素
public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

六. 迭代器

众所周知,在遍历List的过程,如果想要用ArrayList的remove方法删除某个元素将会抛出异常,想要删除

private void iteratingRemove() {
  List<Integer> list = Arrays.asList(1,2,3);
        Iterator iterator = list.iterator();
        while (iterator.hasNext()) {
            Integer integer = (Integer) iterator.next();
            if (integer.equals(2)) {
                list.remove(integer);  // UnsupportedOperationException occurred
              	iterator.remove();
            }
      }
}

看源码可见iterator 方法返回的是ArrayList 中定义的私有内部类 Itr对象

public Iterator<E> iterator() {
    return new Itr();
}

private class Itr implements Iterator<E> {
	// 下一个要访问的元素下标
    int cursor = 0;

 	// 上次访问的元素下标,如果该元素已被删除则返回-1
    int lastRet = -1;

    //对 ArrayList 修改次数的期望值,初始值为 modCount
    int expectedModCount = modCount;

    // 如果下一个元素的下标等于集合的大小,说明后面没有元素
    public boolean hasNext() {
        return cursor != size();
    }

    public E next() {
        // 判断 expectedModCount 和 modCount 是否相等
        checkForComodification();
        // 获取游标指向的元素,将游标后移
        try {
            /**
             * 将 cursor 赋值给 lastRet ,并返回下标为 lastRet 的元素
             * 最后将 cursor 自增 1。开始时,cursor = 0,lastRet = -1;
             * 每调用一次 next 方法, cursor 和 lastRet 都会自增 1
             */
            int i = cursor;
            E next = get(i);
            lastRet = i;
            cursor = i + 1;
            return next;
        } catch (IndexOutOfBoundsException e) {
            // 入伙在获取的时候抛出异常,检查  expectedModCount 和 modCount 是否相等
            checkForComodification();
            throw new NoSuchElementException();
        }
    }

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

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            AbstractList.this.remove(lastRet);
            if (lastRet < cursor)
                cursor--;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException e) {
            throw new ConcurrentModificationException();
        }
    }
}

可见的在调用list的iterator后,导致modCountexpectedModCount 不一致,因为循环还没有结束,所以会继续调用

iterator.next() 方法,而在该方法中会先判断 expectedModCount 和 modCount 是否相等,不等所以抛出异常,而在调用iterator.remove() 情况下,会在调用完AbstractList.this.remove(lastRet); 后将 expectedModCountmodCount的值同步。

img

所以要在ArrayList的迭代中将某个元素删除,直接调用 iterator.remove() 即可。因为在该方法中增加了 expectedModCount = modCount 操作。但是这个 remove 方法也有弊端。

  • 只能进行remove操作,add、clear 等 Itr 中没有。
  • 调用 remove 之前必须先调用 next。因为 remove 开始就对 lastRet 做了校验。而 lastRet 初始化时为 -1。
  • next 之后只可以调用一次 remove。因为 remove 会将 lastRet 重新初始化为 -1

七. 序列化

transient关键字

我们都知道一个对象只要实现了Serilizable接口,这个对象就可以被序列化,然而在实际开发过程中,我们常常会遇到这样的问题,这个类的有些属性需要序列化,而其他属性不需要被序列化,打个比方,如果一个用户有一些敏感信息(如密码,银行卡号等),为了安全起见,不希望在网络操作(主要涉及到序列化操作,本地序列化缓存也适用)中被传输,这些信息对应的变量就可以加上transient关键字。换句话说,这个字段的生命周期仅存于调用者的内存中而不会写到磁盘里持久化。

总之,java的transient关键字为我们提供了便利,只要实现Serilizable接口,将不需要序列化的属性前添加关键字transient,序列化对象时该属性就不会序列化到指定的目的地中。

上面的elementData 属性采用了transient来修饰,表明其不使用Java默认的序列化机制来序列化,但是该属性是ArrayList的底层数据结构,在网络传输或磁盘读写中一定需要将其序列化,之后使用的时候还需要反序列化,

package serial;

import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class Bean implements Serializable {

    private static final long serialVersionUID = -3450064362986273896L;

    private int number1;
    private transient int number2;
    private List<Integer> list;
 
    private Bean(int number1, int number2, List<Integer> list) {
        this.number1 = number1;
        this.number2 = number2;
        this.list = list;
    }

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>(2);
        list.add(1);
        list.add(2);
        Bean bean = new Bean(3,4, list);

        try {
            FileOutputStream fs = new FileOutputStream("F:\\foo.ser");
            ObjectOutputStream os = new ObjectOutputStream(fs);
            os.writeObject(bean);
            os.close();

            FileInputStream fi = new FileInputStream("F:\\foo.ser");
            ObjectInputStream oi = new ObjectInputStream(fi);
            Bean bean1 = (Bean)oi.readObject();
            oi.close();

            System.out.println(bean1.number1 + " " + bean1.number2);
            for (Integer integer : bean1.list) {
                System.out.print(integer + " ");
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

可以从运行结果看到ArrayList的数据仍然是可以被序列化和反序列化的,那既然不采用Java默认的序列化机制,那ArrayList又是怎么实现序列化与反序列化的呢?其实ArrayList自己实现了一套序列化和反序列化的方法

ing

但是这些方法都是私有的,那么它们是怎么被调用的呢

首先看下ObjectOutputStream的writeObject又做了哪些事情

ing

主要看下writeObject0方法,它会根据传进来的ArrayList对象得到Class信息,然后再包装成 ObjectStreamClass,因为/ArrayList实现了Serialozable接口,所以会去调用writeOrdinaryObject

经过一些预处理和判断后会去调用writeSerialData

img

在writeSerialData方法里,会调用ObjectStreamClass 的 invokeWriteObject方法,在invokeWriteObject方法中writeObjectMethod调用invoke方法,而writeObjectMethod是在ObjectStreamClass中初始化的

invoke

为什么使用transient修饰elementData?

既然要将ArrayList的字段序列化(即将elementData序列化),那为什么又要用transient修饰elementData呢?

回想ArrayList的自动扩容机制,elementData数组相当于容器,当容器不足时就会再扩充容量,但是容器的容量往往都是大于或者等于ArrayList所存元素的个数。

比如,现在实际有了8个元素,那么elementData数组的容量可能是8x1.5=12,如果直接序列化elementData数组,那么就会浪费4个元素的空间,特别是当元素个数非常多时,这种浪费是非常不合算的。

所以ArrayList的设计者将elementData设计为transient,然后在writeObject方法中手动将其序列化,并且只序列化了实际存储的那些元素,而不是整个数组

见源码:

// Write out all elements in the proper order.
for (int i=0; i<size; i++) 
{
    s.writeObject(elementData[i]);
}
Java, Security developer https://jordonyang.github.io/ Guangzhou, China 本站所有文章如未说明均为原创,请勿随意转载,如需转载请联系我 (linfengit@qq.com)