2018-12-24

ArrayList相关

前言

集合框架有很多可以直接使用的集合比如常用的就有ArrayList跟HashMap 这篇文章主要研究一下ArrayList

基本用法

声明并且初始化一个arraylist

ArrayList<Integer> arrayList = new ArrayList<Integer>();
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);
/*获取list的大小*/
System.out.println("size of ArrayList is " + arrayList.size());

注意

ArrayList<Integer> arrayList = new ArrayList<Integer>();

尖括号里面只可以是类比如Integer 而不可以是基本数据类型比如int那些

我们先来看看arraylist中有哪些字段

//序列化id
private static final long serialVersionUID = 8683452581122892189L;

/**
 * 默认的初始化容量是10
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * 被空实例用的空数组实例
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * 被那些默认容量 但是目前还是空的实例用的数组实例
 * 跟上面那个EMPTY_ELEMENTDATA不一样的地方是 这个当第一个元素被添加的时候他知道什么时候开始扩张容量
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * 这就是真正存储着arraylist的元素的数组
 */
transient Object[] elementData; // non-private to simplify nested class access

/**
 * 表示数组的长度
 */
private int size;

接下来我们看一下

arrayList.add(1);

中发生了什么

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

上面很明显是先确定容量是否足够然后使用下标定位到数组中元素到最后把新的元素添加上去那么我们看一下ensureCapacityInternal函数是怎样确定容量是否足够以及怎么扩张容量的这个函数最终是使用grow函数进行扩容的

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    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);
}

从上面我们很显而易见地知道每一次扩张容量都是在原来容量的基础上增加一半

int newCapacity = oldCapacity + (oldCapacity >> 1);

从上面我们可以知道ArrayList的空间都是不够就动态增加的主要使用Arrays.copyOf这个函数重新分配空间那么就会有一个问题如果一开始我们无参构造ArrayList的时候没有指定容量那么默认容量就是10 如果这时候我们要add大量的元素比如1000个那么就需要多次动态扩容这样会造成被动扩容和数组复制的额外开销

所以 使用ArrayList之前指定恰当的容量那么是可以避免上面的额外开销但是如果容量没有指定恰当有可能会造成内存溢出

遍历问题

我看别人的博客说ArryList一般有三种遍历方式

下标遍历
for循环遍历
迭代器遍历

下标遍历

/*下标遍历 这是最快的一种方式*/
for (int i = 0; i < arrayList.size(); i++) {
    /*使用下标定位数组元素的时候 只可以使用get函数定位*/
    System.out.println(arrayList.get(i));
}

显而易见这是最快的一种遍历方式没什么好说的

for循环遍历

/*for循环遍历*/
for (Integer integer : arrayList) {
    System.out.println(integer);
}

这种方法效率介于中间但是因为无法看到这个方法的源代码所以无从分析

迭代器遍历

/*使用迭代器进行遍历*/
Iterator<Integer> iterator = arrayList.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

这是效率最低的一种方法我们可以看一下他的源代码分析一下

arrayList.iterator();

这里返回一个内置类的实例这个内之类实现了Iterator接口我们可以看一下这个内置类的一些字段比较有意思

1
2
3

int cursor;       // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;

前面两个变量顾名思义看注释也可以知道他们是干什么的后面两个
expectedModCount表示预期的数组被修改的次数 modCount是实际上被修改的次数这两个字段有什么用呢？

首先我们来看一个问题

ArrayList是非线性安全的就是有可能同时被多个线程操作的话出现数据不一致性所以ArrayList必须一个时间内只可以给一个单独的线程操作

但是如果在遍历的时候如何防止我在遍历一个ArrayList的时候避免这个arraylist同时被其他线程修改呢

迭代器遍历这种方法就可以做到这种效果因为迭代器的hasNext函数跟Next函数都可以使用checkForComodification函数来检查是否在遍历的时候被其他线程修改了怎么检查？靠的就是上面两个字段expectedModCount modCount 具体如下

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

所以了我们可以看得出上面三种遍历ArrayList的方式从效率来看肯定是
下标定位 > for循环 > 迭代器

但是如果涉及线程安全的时候又恰巧这时候使用的ArrayList(虽然在线程安全的时候不推荐使用ArrayList) 我们就可以使用迭代器遍历的方法遍历ArrayList