“ 一起来了解集合中ArrayList的源码实现 。” —— 23号老板
0
1
引入
先送一张图。好好珍藏~ (来自网络)
回归基础,回归原理,你会有更深的领悟。今天来聊一聊在Java当中常用的一个集合类:ArrayList。
在大学学习数据结构的时候,我们知道常见的一种数据结构,就是集合。而在Java中的集合,是用于存储对象的工具类容器,它实现了常用的数据结构,提供了一系列公开的方法用于增加、删除、修改、查找和遍历数据,降低了日常开发的成本,提高了开发效率。
从上面的框架图中可以看出,Java的集合主要分为两类。
1、按照单个元素存储的Collection,在其继承树中,Set、List都实现了Collection接口;
2、按照Key - Value存储的Map,也是当下最流行的一种数据结构,业内出现了以此为基础的各式Nosql数据存储层产品。
02
了解ArrayList
List集合是线性数据结构的主要实现,集合元素通常存在一个明确的元素关系,Pre、Next。因此,List集合的遍历结果是稳定的。ArrayList就是List集合中的一个实现类,在开发中也是最常使用的一个集合类。这里以最常使用的JDK8为例,如果有版本上的不一致,请参看对比。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
也许你会在面试当中,常说到这样的话,和LinkedList作一次对比。ArrayList在使用上查询效率较高,新增元素的效率较低,balabala......然后就没什么可说的。再一问,这是为什么?不知道。
简单来说,ArrayList在内存上的存储,是利用了一个连续的存储空间,是一个顺序容器。即元素存放的数据与放进去的顺序相同,允许放入null元素,底层通过数组实现。
ArrayList的几个实现。
1、实现RandomAccess类
其原理的本质就在于indexedBinarySerach(list,key)或iteratorBinarySerach(list,key)方法。你会发现实现RandomAccess接口的List集合采用一般的for循环遍历,而未实现这接口则采用迭代器。通过大量的测试可以知道,使用迭代器遍历集合的速度会比for循环遍历差。
2、实现Cloneable类
Cloneable是一个标记接口,只有实现这个接口后,然后在类中重写Object中的clone方法,然后通过类调用clone方法才能克隆成功,如果不实现这个接口,则会抛出CloneNotSupportedException(克隆不被支持)异常。
3、实现Serializable类
实现Serializable接口的作用是就是可以把对象存到字节流,然后可以恢复(反序列化),能够进行关于对象的网络传输方式。
0
3
深入理解
/**
* 默认初始容量
*/
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 空表的表示方法
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 底层的数组为elementData
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* ArrayList的大小
*/
private int size;
/**
* 带有初始容量的构造器
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {//大于0时创建一个initialCapacity大小的数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
}
}
/**
* 无参构造,默认空表数组 {}
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 当size大于0,采用Arrays.copyOf的复制方法赋值数组
*/
public 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;
}
}
03
add、remove等
ArrayList的底层是基于动态数组实现的原因,动态数组的意思就是指底层的数组大小并不是固定的,而是根据添加的元素大小进行一个判断,不够的话就动态扩容,扩容的代码就在ensureCapacity里。
/**
* 确保在扩容时的容量
*/
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
/**
* 数组的最大长度值,超过则OutOfMemoryError
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 扩容,原数组长度的2倍+1,采用的Arrays.copyOf复制方法
*/
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);
elementData = Arrays.copyOf(elementData, newCapacity);
}
public int size() { return size;}
public boolean isEmpty() { return size == 0;}
public boolean contains(Object o) { return indexOf(o) >= 0;}
空间的问题解决后,插入过程就显得非常简单。
/**
* 获取index位置的元素
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
/**
* 替换index位置上的元素
*/
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
/**
* 新增元素
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
/**
* 删除元素
*/
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
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
return oldValue;
}
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)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
删除是每次进行数组复制,然后让旧的elementData置为null进行垃圾回收。
以remove()方法为例。
可以看到这个 remove() 方法被重载了,一种是根据下标删除,一种是根据元素删除,这也都很好理解。
根据下标删除的 remove() 方法,大致的步骤如下:
1、检查有没有下标越界,就是检查一下当前的下标有没有大于等于数组的长度
2、列表被修改(add和remove操作)的次数加1
3、保存要删除的值
4、计算移动的元素数量
5、删除位置后面的元素向左移动,这里是用数组拷贝实现的
6、将最后一个位置引用设为 null,使垃圾回收器回收这块内存
7、返回删除元素的值
根据元素删除的 remove() 方法,大致的步骤如下:
1、元素值分为null和非null值
2、循环遍历判等
3、调用 fastRemove(i) 函数
a、修改次数加1
b、计算移动的元素数量
c、数组拷贝实现元素向左移动
d、将最后一个位置引用设为 null
e、返回 fase
4、返回 true
04
小结
现在,你对ArrayList是不是有了一个更深入的理解。深入源码,有时候能够让你更加理解代码的逻辑和数据结构。
文章部分内容来自网络博客,综合整理,在此鸣谢。