类集

发表于

List接口 – 允许保存重复数据

<--more-->

  • java类集的引出，使用动态数组解决定长问题

ArrayList，Vector，LinkedList

1552897701468

  • 每种集合的通用逻辑，都被抽象到相应的抽象类中，AbstractList集中了各种List操作的通用部分。这些集合不是完全孤立的，LinkList本身既是List，也是Deque

ArrayList

ArrayList类通过extends关键字继承AbstractList抽象类，通过关键字implement实现List集合接口，RandomAccess标记接口，Cloneable克隆接口，Serializable序列化接口

1
2
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

1552898663072

接口RandomAccessa.java（实现随机访问）
  • 此接口的主要目的是允许一般的算法更改其行为，从而在将其应用到随机或连续访问列表时能提供良好的性能。
  • 接口RandomAccess 是一个标记接口，实现该接口的集合List 支持快速随机访问。List 集合尽量要实RandomAccess 接口，如果集合类是RandomAccess 的实现，则尽量用for(int i = 0; i < size; i++) 来遍历效率高，而不要用Iterator迭代器来遍历(如果List是Sequence List，则最好用迭代器来进行迭代)
接口Cloneable

  • 实现接口的目的是重写java.lang.Object的clone()的方法，实现浅拷贝。深拷贝和浅拷贝针对像 Object, Array 这样的复杂对象的。浅拷贝只复制一层对象的属性，而深拷贝则递归复制了所有层级。

    关于深浅拷贝

    • 浅拷贝
    • 深拷贝
接口Serializable

  • 该接口无继承实现关系，实现给接口的类支持序列化。所以ArrayList支持序列化

    关于序列化

    • 序列化：将一个内存中保存的对象变成二进制数据流的形式进行传输，或者是将其保存在文本中。
    • 反序列化：可以将其他地方所存储的数据通过二进制数据流的方式读取出来

源码分析：

ArrayList的构造方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//序列版本号
private static final long serialVersionUID = 8683452581122892189L;

//空数组
private static final Object[] EMPTY_ELEMENTDATA = {};

//默认构造函数的空数组
 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
 
//数组缓冲区，存储元素的底层实现，真正存放元素的数组
//使用transient关键字修饰的elementData是不支持序列化的
transient Object[] elementData;// non-private to simplify nested class access


 //指定初始化容量的构造方法
    public ArrayList(int initialCapacity) {
		//若初始容量大于0，则新建一个大小为指定容量的Object数组
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
		//若容量为0，则直接将空数组赋给elementData
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
		//若容量小于0，则抛出异常
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
	
//默认构造方法
//将默认的构造函数的空数组赋给elementData
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
 
//利用别的集合类构建ArrayList的构造方法
    public ArrayList(Collection<? extends E> c) {
		//用Collection.toArray()方法取得一个对象数组，并赋给elementData
		//浅拷贝
        elementData = c.toArray();
		//size为集合元素数量，通过别的集合来构造ArrayList时，就需要给size赋值
		//如果size为0，直接空数组赋给elementData即可
		//如果size不为0，则要将Collection对象中的内容拷贝到elementData中
        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;
        }
    }
  • 无参构造方法中直接初始化Object[] elementData={};
  • 带参构造方法是new Object()或者通过Arrays的方法转化为数组对象
问题一：ArrayList是数组还是集合
  • ArrayList实现List接口，重写其中的add()，get()，remove()等方法，而方法的内部代码是基于数组来处理数据的。
  • ArrayList是实现List接口的集合，是基于数组的集合，数据的存储容器是数组，集合方法是通过数组实现的（例如：泛型参数构造方法是将传入的集合c先转化为数组在进行处理的）。

通关add方法查看初始容量

  • ArrayList中定义了一个默认存储容器大小DEFAULT_CAPACITY=10，我们发现在构造方法创建ArrayList是并没有使用到该常量。在add添加元素的时候，先将size+1传入到ensureCapacityInternal()判断当前数组elementData是否需要扩容，足够size自增1，直接添加元素即可。
    • 扩容：当数组还是默认的空数组时，这里的size+1=0 < DEFAULT_CAPACITY 会将容器大小扩容为10，此时的elementData扩容为Object[10]

问题二：ArrayList的初始容量是多少？

  • 当调用构造方法创建ArrayList时，默认无参构造对象的容器初始大小为0。而当调用add方法时才会将数组扩容为10.

ArrayList的扩容问题：

当elementData.length < size+1时才会进行扩容，调用grow方法。

  • 先取到当前容器大小oldCapacity，进行扩容，判断扩容容量是否合法，是否溢出，然后处理为合理的大小
    • 使用newCapacity = oldCapacity + (oldCapacity >> 1)计算出来预计扩容的大小，如果该大小仍然小于数组所扩容后的大小，newCapacity = minCapacity;重新改写新扩容后数组容量，如果新数组大小大于数组的最大容量限度，调用huneCapacity()方法，直接将容量大小定义为Integer的最大值，最后调用Arrays方法进行拷贝
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
--------------------------------------------------------------------
 //默认初始化数组容量
	private static final int DEFAULT_CAPACITY = 10;
 // 集合最大容量     
	private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 //当前数组的大小
 	private int size;
    public int size() {
        return size;
    }
    public boolean isEmpty() {
        return size == 0;
    }

 //添加元素，添加成功返回true
 //每次添加元素之前都会检查一下是否需要扩容
	public boolean add(E e) {
		//判断添加后的容量，选择是否需要扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
		//在数组末尾添加元素，更新size
        elementData[size++] = e;
        return true;
    }

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
 
 //当第一次添加元素，需要获取数组初始容量，返回minCapacity和默认初始容量中的较大值
 //当不是第一次添加元素，则直接返回minCapacity
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
 
 //moCount(修改次数)自增1,判断是否需要扩充数组长度
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
			//增加数组长度
            grow(minCapacity);
    }
 
 //数组扩容，默认需要扩容1.5倍
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
		//新数组大小为原数组的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
		//如果新数组大小仍然小于minCapacity，则更新newCapacity的值
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
		//如果新数组大小大于数组的最大容量限度，调用huneCapacity()方法
        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);
    }
 
 //新数组的大小
    private static int hugeCapacity(int minCapacity) {
		//若minCapacity小于0，抛异常
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        //超过最大值不合法，直接将容量大小定义为Integer的最大值
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

 //指定位置添加元素
	public void add(int index, E element) {
		//越界判断，如果越界抛异常
        rangeCheckForAdd(index);
		
		//判断是否需要扩容，步骤和上面一样
        ensureCapacityInternal(size + 1);  // Increments modCount!!
		//将数组从index开始的数据往后移一位
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
		//添加元素
        elementData[index] = element;
        size++;
    }
ArrayList的序列化问题补充
  • 集合的存储容器elementData 使用transient 关键字修饰不支持序列化，但是我们知道ArrayList 是支持序列化的，那我们是怎么序列化集合中的数据呢，这里不直接序列化elementData，而是遍历每个数据分别进行IO 流处理来实现存储容器中对象的序列化的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// ArrayList 列表结构被修改的次数。        
   protected transient int modCount = 0;

   private void writeObject(java.io.ObjectOutputStream s)
       throws java.io.IOException{
       // Write out element count, and any hidden stuff
       //ArrayList 列表结构被修改的次数
       int expectedModCount = modCount;
       s.defaultWriteObject();
       // Write out size as capacity for behavioural compatibility with clone()
       s.writeInt(size);
       //对每一对象进行IO流的写处理
       // Write out all elements in the proper order.
       for (int i=0; i<size; i++) {
           s.writeObject(elementData[i]);
       }

       if (modCount != expectedModCount) {
           throw new ConcurrentModificationException();
       }
   }
  • modCount是表示ArrayList对象被修改的次数，Iterator中有一个成员变量expectedModCount，在创建时会将modCount赋值给他，用来检验在迭代过程中List对象是否被修改，如果被修改就会抛出ConcurrentModificationException异常。在每次调用Iterator对象的next方法时都会调用checkForComodification()方法进行检验，将modCount与expectedModCount进行对比。