头像

带翅膀的猫

时光荏苒,我们一直都在

《JDK源码之ArrayList》

 3周前  •   JDK源码阅读  •     •   35  •   1

ArrayList

在学习JAVA集合中初次学习的容器就是ArrayList,我们深深的感到它的强大,和数组相比它能实现容量的自动增长。但是大部分人对它的了解都是不够详细的,现在跟随我的步伐窥探一下吧!

继承关系

ArrayList 继承了AbstractList,实现了List。它是一个数组队列,提供了相关的添加、删除、修改、遍历等功能。

ArrayList 实现了RandmoAccess接口,即提供了随机访问功能。RandmoAccess是java中用来被List实现,为List提供快速访问功能的。在ArrayList中,我们即可以通过元素的序号快速获取元素对象;这就是快速随机访问。稍后,我们会比较List的“快速随机访问”和“通过Iterator迭代器访问”的效率。

ArrayList 实现了Cloneable接口,即覆盖了函数clone(),能被克隆。

ArrayList 实现java.io.Serializable接口,这意味着ArrayList支持序列化,能通过序列化去传输。

重要属性

JAVAtransient Object[] elementData; //用于存储数据
private int size;//ArrayList大小(Object[]包含的元素数目)
private static final int DEFAULT_CAPACITY = 10;//默认初始化大小为10

可以发现ArrayList的底层是通过Object[]实现的。

构造方法

JAVAprivate static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public ArrayList() {
	this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

不指定容量则默认容量为10。

JAVApublic 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);
	}
}

如果初始化容量小于0则抛出IllegalArgumentException异常。

JAVApublic ArrayList(Collection<? extends E> c) {
	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;
	}
}

我们可以通过另外的Collection创建ArrayList。

测试List<Integer> list1 = new ArrayList<>();
list1.add(1);
list1.add(2);
list1.add(3);
List<Integer> list2 = new ArrayList<>(list1);//直接使用另一个Collection创建list2
for(Integer i:list2){
	System.out.println(i);
}
/**
 * 1
 * 2
 * 3
 */

add相关

JAVApublic boolean add(E e) {
	ensureCapacityInternal(size + 1);  //确保对象数组elementData有足够的容量,可以将新加入的元素e加进去
	elementData[size++] = e;//加入新元素e,size加1
	return true;
}
扩容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;//新的容量依旧不足则为minCapacity
	if (newCapacity - MAX_ARRAY_SIZE > 0)
		newCapacity = hugeCapacity(minCapacity);//新容量大于最大容量(Integer.MAX_VALUE-8),调用hugeCapacity方法重新计算
	// minCapacity is usually close to size, so this is a win:
	elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
	if (minCapacity < 0) // overflow
		throw new OutOfMemoryError();
	return (minCapacity > MAX_ARRAY_SIZE) ?
		Integer.MAX_VALUE :
		MAX_ARRAY_SIZE;
}

ArrayList不仅仅可以一个个的添加元素,还可以通过另外一个list直接批量添加。

JAVApublic boolean addAll(Collection<? extends E> c) {
	Object[] a = c.toArray();
	int numNew = a.length;
	ensureCapacityInternal(size + numNew);  // 容量检查
	System.arraycopy(a, 0, elementData, size, numNew);
	size += numNew;
	return numNew != 0;//若加入的是空集合则返回false
}
测试List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
List<Integer> list2 = new ArrayList<>();
list2.addAll(list);
for(Integer i:list2){
	System.out.println(i);
}
/**
 * 1
 * 2
 * 3
 */

get(int index)

JAVApublic E get(int index) {
	rangeCheck(index);//index合法性检查

	return elementData(index);
}

private void rangeCheck(int index) {
	if (index >= size)
		throw new IndexOutOfBoundsException(outOfBoundsMsg(index));//越界
}

set(int index,E element)

JAVApublic E set(int index, E element) {
	rangeCheck(index);//index合法性检查

	E oldValue = elementData(index);
	elementData[index] = element;
	return oldValue;//返回旧值
}

remove相关

JAVA/**
 *根据下标删除元素
 */
public E remove(int index) {
	rangeCheck(index);//index合法性检查

	modCount++;
	E oldValue = elementData(index);//获取旧值

	int numMoved = size - index - 1;//计算出需要移动的元素个数 (因为需要将后续元素左移一位 此处计算出来的是后续元素的位数)
	if (numMoved > 0)//如果这个值大于0 说明后续有元素需要左移  是0说明被移除的对象就是最后一位元素
		System.arraycopy(elementData, index+1, elementData, index,
						 numMoved);//index右边的所有元素左移一位,覆盖掉index位置上的元素
	elementData[--size] = null; // 将最后一个元素赋值为null,这样就可以被gc回收了

	return oldValue;//返回被删除的元素
}
JAVA/*
 *删除特定的对象(第一个出现的)
 */
public boolean remove(Object o) {
	if (o == null) {//如果元素是null 遍历数组移除第一个null
		for (int index = 0; index < size; index++)
			if (elementData[index] == null) {
				fastRemove(index);//遍历找到第一个null元素的下标 调用下标移除元素的方法
				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)
		System.arraycopy(elementData, index+1, elementData, index,
						 numMoved);
	elementData[--size] = null; // clear to let GC do its work
}

contains(Object o)

判断list中是否有指定的对象。

JAVApublic boolean contains(Object o) {
	return indexOf(o) >= 0;
}
//indexOf返回第一个出现的对象o的索引
public int indexOf(Object o) {
	//一个个遍历list寻找符合的对象,找到则返回第一次出现下标,否则返回-1
	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相对的还有lastIndexOf方法,它返回最后一个o的索引。

clear()

使用clear对list进行清空。

JAVApublic void clear() {
	modCount++;

	// clear to let GC do its work
	for (int i = 0; i < size; i++)
		elementData[i] = null;

	size = 0;
}

clone()

使用clone方法可以拷贝一个相同的list。注意这是浅拷贝。

测试static class Stu{
	public String name;
	public Stu(String name){
		this.name = name;
	}
	public String toString(){
		return name;
	}
}
public static void main(String[] args) {
	ArrayList<Stu> list = new ArrayList<>();
	list.add(new Stu("Java"));
	list.add(new Stu("Pyhton"));
	list.add(new Stu("Ruby"));
	System.out.println("list:"+list);
	ArrayList<Stu> listCopy = (ArrayList<String>)list.clone();
	System.out.println("listCopy:"+list);
	System.out.println("修改:");
	list.get(0).name = "C++";
	System.out.println("list:"+list);
	System.out.println("listCopy:"+listCopy);
	/**
	 * list:[Java, Pyhton, Ruby]
	 * listCopy:[Java, Pyhton, Ruby]
	 * 修改:
	 * list:[C++, Pyhton, Ruby]
	 * listCopy:[C++, Pyhton, Ruby]
	 */
}

实现深拷贝。

测试static class Stu implements Cloneable{
	public String name;
	public Stu(String name){
		this.name = name;
	}
	public String toString(){
		return name;
	}
	@Override
	public Stu clone(){
		return new Stu(this.name);
	}
}
public static void main(String[] args) {
	ArrayList<Stu> list = new ArrayList<>();
	list.add(new Stu("Java"));
	list.add(new Stu("Pyhton"));
	list.add(new Stu("Ruby"));
	System.out.println("list:"+list);
	ArrayList<Stu> listCopy = new ArrayList<>();
	for (Stu stu:list){
		listCopy.add(stu.clone());
	}
	System.out.println("listCopy:"+list);
	System.out.println("修改:");
	list.get(0).name = "C++";
	System.out.println("list:"+list);
	System.out.println("listCopy:"+listCopy);
	/**
	 * list:[Java, Pyhton, Ruby]
	 * listCopy:[Java, Pyhton, Ruby]
	 * 修改:
	 * list:[C++, Pyhton, Ruby]
	 * listCopy:[Java, Pyhton, Ruby]  //没有改变,说明是深拷贝
	 */
}

iterator()

我们除了可以使用for循环遍历list,我们也可以使用iterator遍历列表。

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

private class Itr implements Iterator<E> {
	int cursor;       // 表示下一个元素的索引位置
	int lastRet = -1; // 表示上一个元素的索引位置
	int expectedModCount = modCount;//预期被修改的次数,用于判断是否在遍历的过程中,是否发生了add、remove操作
        //这是集合迭代中的一种“fast-fial”机制,这种机制提供迭代过程中集合的安全性。

	Itr() {}

	public boolean hasNext() {
		return cursor != size;//如果cursor==size,说明已经遍历完了
	}

	@SuppressWarnings("unchecked")
	public E next() {
		checkForComodification();//检测在遍历的过程中,是否发生了add、remove操作
		int i = cursor;
		if (i >= size)
			throw new NoSuchElementException();
		Object[] elementData = ArrayList.this.elementData;
		if (i >= elementData.length)
			throw new ConcurrentModificationException();
		cursor = i + 1;
		return (E) elementData[lastRet = i];
	}

	public void remove() {//使用迭代器删除元素
		if (lastRet < 0)
			throw new IllegalStateException();
		checkForComodification();

		try {
			ArrayList.this.remove(lastRet);
			cursor = lastRet;
			lastRet = -1;
			expectedModCount = modCount;//统一expectedModCount和modCount
		} catch (IndexOutOfBoundsException ex) {
			throw new ConcurrentModificationException();
		}
	}

	final void checkForComodification() {//检测是否修改了list
		if (modCount != expectedModCount)
			throw new ConcurrentModificationException();//在迭代的过程中如果进行了修改(add/remove)则抛出异常。remove指的是不使用迭代器进行删除。
	}
}
测试ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()){
	System.out.println(iterator.next());
	list.remove(2);//迭代过程不使用迭代器进行删除,抛异常
}
/**
  * Exception in thread "main" java.util.ConcurrentModificationException
  */

如果我们使用迭代器进行删除则不会出错。

测试ArrayList<String> list = new ArrayList<>();
list.add("abc");
list.add("def");
list.add("ghi");
System.out.println("删除前:"+list);
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()){
	if("def".equals(iterator.next())){
		iterator.remove();//迭代过程使用迭代器进行删除
	}
}
System.out.println("删除后:"+list);
/**
 * 删除前:[abc, def, ghi]
 * 删除后:[abc, ghi]
 */

与ArrayList类似的容器还有Vector,不过我们需要注意的是ArrayList是线程不安全的,而Vector是线程安全的。后续会介绍Vector。

 

上一篇:
下一篇:

 评论


 已有1条评论

  1. starry 1 Mac OS X 10_14_1 | Safari浏览器 605.1.15 3天前

    牛皮,为大佬打call