ArrayList是如何组织数据的，ArrayList组织数据
分享于 点击 24656 次 点评：52
ArrayList是如何组织数据的，ArrayList组织数据
ArrayList简介
ArrayList是我们十分常用的一个类，它的底层是由数组实现。不同于基本数组的是，它的容量能自动增长。
数据结构
如上所述，ArrayList其实是对数组的包装，无论是add方法，亦或是remove,都是操作一个全局的数组。
这个全局数组定义如下
Object[] array;JAVA中所有所有对象都继承自Object，所以array可以装下所有对象。
初始化
要把刚刚声明的array初始化，并指定其容量为capacity，只需如下代码即可实现。
array = new Object[capacity];所以ArrayList指定容量的构造函数如下
public ArrayList(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException("capacity < 0: " + capacity);
}
array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);
}我们用这个构造函数初始化一个容量为7的list，并只允许它装入String类型的数据。
ArrayList<String> list = new ArrayList<>(7);数组是一块连续的内存，初始化值是null,所以此时它在内存里应该是这样的。
使用add方法依次add进去”w”、”i”、”n”、”d”、”c”、”a”、这6个字符串类型的字母之后。再取一下内存的快照应当如下
此时应当有两个疑问，按顺序add进去的元素会按顺序排列么？
以及如果我再添加”k”、”e”两个数据，6加2就等于8了，list会做哪些工作来装第8个元素呢？
add方法和扩容
刚才执行的add方法源码如下，它的功能是添加一个元素到ArrayList的尾部。
public boolean add(E object) {
Object[] a = array;
int s = size;
if (s == a.length) {
Object[] newArray = new Object[s +
(s < (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : s >> 1)];
System.arraycopy(a, 0, newArray, 0, s);
array = a = newArray;
}
a[s] = object;
size = s + 1;
modCount++;
return true;
}
此时我们再执行add方法，添加一个”k”。然后根据上边代码分析其运行。
list.add("k");当前数组里的数据有6个，也就是size的值为6。
而初始化的容量为7，即a.length为7。
所以if条件下的代码不执行，而会顺序执行这句话。
a[s] = object如下图所示，将object加入到s位置，就是尾部了。
这个时候，最初初始化的array容量已满,也就是size和a.length已经相等了，但是还有”e”没有放进去。好，那我们继续放。
list.add("e");此时会执行if语句里的代码，其实就是触发了扩容。扩容并不是增大原来数组的容量，而是new一个容量更大的数组，把小的旧数组里的数据复制到新的大数组去。然后全局的array指向这个新数组，显然底层的数组已经不是原来的数组了，但在ArrayList使用者的角度看List还是那个List。MIN_CAPACITY_INCREMENT是最小容量常量，默认值是12，如果当前容量小于 6（MIN_CAPACITY_INCREMENT / 2）就增加12（MIN_CAPACITY_INCREMENT），否则 就增加当前容量的一半 （s >> 1）。因为add方法太常用了，所以上边那句话被直接写在了add方法里，省去子函数调用，以提高程序性能。当然它还被封装成了一个方法，再其他地方出没。
private static int newCapacity(int currentCapacity) {
int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ? MIN_CAPACITY_INCREMENT : currentCapacity >> 1);
return currentCapacity + increment;
}由于当前容量是7，大于6，所以容量应当增加 7 >> 1，即newArray如下。
新数组准备好之后，将旧数组里的数据拷贝过来，并将全局的array指向这个数组。
然后再把”e”添加进去
此时所有的工作就做完了。
就像在食堂打饭，总有比你还饿的同学想去前边加塞。又或者发现我的字母写错了，我想写成”wind&cake”，那能不能让“&”加个塞呢。
list.add(4,"&");是的，执行这条语句就能实现加塞操作。但是，它到底是加塞呢，还是说把索引为4的元素替换了呢。看一下源码吧。
public void add(int index, E object) {
Object[] a = array;
int s = size;
if (index > s || index < 0) {
throwIndexOutOfBoundsException(index, s);
}
if (s < a.length) {
System.arraycopy(a, index, a, index + 1, s - index);
} else {
// assert s == a.length;
Object[] newArray = new Object[newCapacity(s)];
System.arraycopy(a, 0, newArray, 0, index);
System.arraycopy(a, index, newArray, index + 1, s - index);
array = a = newArray;
}
a[index] = object;
size = s + 1;
modCount++;
}接上文，此时size是8，而list在底层经过一次偷偷扩容之后变成了10。满足if条件会执行如下语句
System.arraycopy(a, index, a, index + 1, s - index);这个函数定义在lang包下的System类里，它的参数意义依次如下。
src:源数组；
srcPos:源数组要复制的起始位置；
dest:目的数组；
destPos:目的数组放置的起始位置；
length:复制的长度。
此方法的原数组和目的数组可以相同，它在底层实现的时候是先将原数组拷贝到一个临时数组里去。然后再拷贝到目的数组。因此以上写法并不会出现问题。把它翻译成自然语言：
把a数组中的数据从index开始复制s - index个，
然后从a数组的index + 1位置开始依次放入。
最后执行第17行，将”&”放入。
于是，插队操作就完成了，相对于排队操作，插队会移动大量数据，所以代价略大。
ArrayList如何组织数据就分析完了。联系到实际情况，在排队打饭时会有组团排队、组团插队，忽然不想吃饭离队、看看自己女朋友有没有在排队、饭卖完了大家都出去吃等情况出现，ArrayList也为我们提供了相应的方法。
单独拿出两个方法，尽管配了图，毕竟也难查ArrayList全貌而进行全局把握，下面贴出ArrayList源码并加入简单注释，以供在上下文中理解。
public class ArrayList<E> extends AbstractList<E> implements Cloneable, Serializable, RandomAccess {
// ArrayList的最小增长容量，它是充分考虑了程序运行的时间和所占用的内存空间后所得出来的值。
private static final int MIN_CAPACITY_INCREMENT = 12;
// list中实际有多少个数据
int size;
// list用这个数组来存放数据，没有数据的位置为空。
transient Object[] array;
// 指定初始容量的构造参数
public ArrayList(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException("capacity < 0: " + capacity);
}
array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);
}
// 默认构造函数，实际大小为0.
public ArrayList() {
array = EmptyArray.OBJECT;
}
// 包含集合的构造函数
public ArrayList(Collection<? extends E> collection) {
if (collection == null) {
throw new NullPointerException("collection == null");
}
Object[] a = collection.toArray();
if (a.getClass() != Object[].class) {
Object[] newArray = new Object[a.length];
System.arraycopy(a, 0, newArray, 0, a.length);
a = newArray;
}
array = a;
size = a.length;
}
// add方法
@Override public boolean add(E object) {
Object[] a = array;
int s = size;
if (s == a.length) {
// 扩容
Object[] newArray = new Object[s +
(s < (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : s >> 1)];
System.arraycopy(a, 0, newArray, 0, s);
array = a = newArray;
}
a[s] = object;
size = s + 1;
modCount++;
return true;
}
// 在某个位置插入某个对象
@Override public void add(int index, E object) {
Object[] a = array;
int s = size;
if (index > s || index < 0) {
// 耳熟能详
throwIndexOutOfBoundsException(index, s);
}
// 当前内容小于List容量，加入一个不会越界。
if (s < a.length) {
// 把index之后的数据都向后拱一个位置，以便留出index空位
// src:源数组；
// srcPos:源数组要复制的起始位置；
// dest:目的数组；
// destPos:目的数组放置的起始位置；
// length:复制的长度。
System.arraycopy(a, index, a, index + 1, s - index);
} else {
// new一个扩大容量的list，然后分两步。
// 第一步：复制index之前的数据到新数组
// 第二步：复制index之后的数据到新数组
Object[] newArray = new Object[newCapacity(s)];
System.arraycopy(a, 0, newArray, 0, index);
System.arraycopy(a, index, newArray, index + 1, s - index);
array = a = newArray;
}
// 把要add的数据放在index位置，然后容量+1
a[index] = object;
size = s + 1;
modCount++;
}
// MIN_CAPACITY_INCREMENT是最小容量常亮，默认值是12
// 如果当前容量小于 6（MIN_CAPACITY_INCREMENT / 2）就增加12（MIN_CAPACITY_INCREMENT）
// 否则 就增加当前容量的一半 （s >> 1 ）
private static int newCapacity(int currentCapacity) {
int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : currentCapacity >> 1);
return currentCapacity + increment;
}
// add一个集合，排在原来数据的后边
// 原理和add一个元素一致
@Override public boolean addAll(Collection<? extends E> collection) {
Object[] newPart = collection.toArray();
int newPartSize = newPart.length;
if (newPartSize == 0) {
return false;
}
Object[] a = array;
int s = size;
int newSize = s + newPartSize; // If add overflows, arraycopy will fail
if (newSize > a.length) {
// 进行扩容，并将原来数据复制到newArray里
int newCapacity = newCapacity(newSize - 1); // ~33% growth room
Object[] newArray = new Object[newCapacity];
System.arraycopy(a, 0, newArray, 0, s);
array = a = newArray;
}
// 把需要add的newPart复制到新数组的后边
System.arraycopy(newPart, 0, a, s, newPartSize);
size = newSize;
modCount++;
return true;
}
// 在指定位置add一个新集合
// 原理和在指定位置add一个数据一致
@Override
public boolean addAll(int index, Collection<? extends E> collection) {
int s = size;
if (index > s || index < 0) {
throwIndexOutOfBoundsException(index, s);
}
Object[] newPart = collection.toArray();
int newPartSize = newPart.length;
if (newPartSize == 0) {
return false;
}
Object[] a = array;
int newSize = s + newPartSize; // If add overflows, arraycopy will fail
if (newSize <= a.length) {
System.arraycopy(a, index, a, index + newPartSize, s - index);
} else {
int newCapacity = newCapacity(newSize - 1); // ~33% growth room
Object[] newArray = new Object[newCapacity];
System.arraycopy(a, 0, newArray, 0, index);
System.arraycopy(a, index, newArray, index + newPartSize, s-index);
array = a = newArray;
}
System.arraycopy(newPart, 0, a, index, newPartSize);
size = newSize;
modCount++;
return true;
}
// 清空集合
@Override public void clear() {
if (size != 0) {
Arrays.fill(array, 0, size, null);
size = 0;
modCount++;
}
}
// 克隆方法
@Override public Object clone() {
try {
ArrayList<?> result = (ArrayList<?>) super.clone();
result.array = array.clone();
return result;
} catch (CloneNotSupportedException e) {
throw new AssertionError();
}
}
// 保证集合能装下minimumCapacity这么多的数据
public void ensureCapacity(int minimumCapacity) {
Object[] a = array;
// 如果装不下，就new一个minimumCapacity容量的数组，然后装进去
if (a.length < minimumCapacity) {
Object[] newArray = new Object[minimumCapacity];
System.arraycopy(a, 0, newArray, 0, size);
array = newArray;
modCount++;
}
}
// get方法，直接索引速度很快。
@SuppressWarnings("unchecked") @Override public E get(int index) {
if (index >= size) {
throwIndexOutOfBoundsException(index, size);
}
return (E) array[index];
}
// 返回List中实际数据的大小
@Override public int size() {
return size;
}
// 是否为空 size为0时为空
@Override public boolean isEmpty() {
return size == 0;
}
// 是否包含某个元素
@Override public boolean contains(Object object) {
Object[] a = array;
int s = size;
// 不为null用equals方法，为null用 ==
if (object != null) {
for (int i = 0; i < s; i++) {
if (object.equals(a[i])) {
return true;
}
}
} else {
for (int i = 0; i < s; i++) {
if (a[i] == null) {
return true;
}
}
}
return false;
}
// 索引
@Override public int indexOf(Object object) {
Object[] a = array;
int s = size;
// 不为null用equals方法，为null用 ==
if (object != null) {
for (int i = 0; i < s; i++) {
if (object.equals(a[i])) {
return i;
}
}
} else {
for (int i = 0; i < s; i++) {
if (a[i] == null) {
return i;
}
}
}
return -1;
}
// 反向索引
@Override public int lastIndexOf(Object object) {
Object[] a = array;
if (object != null) {
for (int i = size - 1; i >= 0; i--) {
if (object.equals(a[i])) {
return i;
}
}
} else {
for (int i = size - 1; i >= 0; i--) {
if (a[i] == null) {
return i;
}
}
}
return -1;
}
// 按索引remove
@Override public E remove(int index) {
Object[] a = array;
int s = size;
if (index >= s) {
throwIndexOutOfBoundsException(index, s);
}
@SuppressWarnings("unchecked") E result = (E) a[index];
// 覆盖掉index的数据
System.arraycopy(a, index + 1, a, index, --s - index);
// 此时a[s]的数据复制到a[s-1]去了，所以a[s]置空，避免内存泄漏。
a[s] = null;
size = s;
modCount++;
return result;
}
@Override public boolean remove(Object object) {
Object[] a = array;
int s = size;
if (object != null) {
// 挨个索引比较，如果相等，逻辑同上。
for (int i = 0; i < s; i++) {
if (object.equals(a[i])) {
System.arraycopy(a, i + 1, a, i, --s - i);
a[s] = null; // Prevent memory leak
size = s;
modCount++;
return true;
}
}
} else {
for (int i = 0; i < s; i++) {
if (a[i] == null) {
System.arraycopy(a, i + 1, a, i, --s - i);
a[s] = null; // Prevent memory leak
size = s;
modCount++;
return true;
}
}
}
return false;
}
// 删除掉从fromIndex到toIndex之间的全部元素。
@Override protected void removeRange(int fromIndex, int toIndex) {
if (fromIndex == toIndex) {
return;
}
Object[] a = array;
int s = size;
if (fromIndex >= s) {
throw new IndexOutOfBoundsException("fromIndex " + fromIndex
+ " >= size " + size);
}
if (toIndex > s) {
throw new IndexOutOfBoundsException("toIndex " + toIndex
+ " > size " + size);
}
if (fromIndex > toIndex) {
throw new IndexOutOfBoundsException("fromIndex " + fromIndex
+ " > toIndex " + toIndex);
}
System.arraycopy(a, toIndex, a, fromIndex, s - toIndex);
int rangeSize = toIndex - fromIndex;
Arrays.fill(a, s - rangeSize, s, null);
size = s - rangeSize;
modCount++;
}
// 指定位置的数据换掉
@Override public E set(int index, E object) {
Object[] a = array;
if (index >= size) {
throwIndexOutOfBoundsException(index, size);
}
@SuppressWarnings("unchecked") E result = (E) a[index];
a[index] = object;
return result;
}
// 返回ArrayList的Object数组
@Override public Object[] toArray() {
int s = size;
Object[] result = new Object[s];
System.arraycopy(array, 0, result, 0, s);
return result;
}
// 返回ArrayList元素组成的数组
@Override public <T> T[] toArray(T[] contents) {
int s = size;
// 如果contents装不下当前List元素，就新建一个刚好能装下的，然后再装
// 否则直接装
if (contents.length < s) {
@SuppressWarnings("unchecked") T[] newArray
= (T[]) Array.newInstance(contents.getClass().getComponentType(), s);
contents = newArray;
}
System.arraycopy(this.array, 0, contents, 0, s);
if (contents.length > s) {
contents[s] = null;
}
return contents;
}
// 把ArrayList的容量设置成和当前元素个数一样大
public void trimToSize() {
int s = size;
if (s == array.length) {
return;
}
if (s == 0) {
array = EmptyArray.OBJECT;
} else {
Object[] newArray = new Object[s];
System.arraycopy(array, 0, newArray, 0, s);
array = newArray;
}
modCount++;
}
@Override public Iterator<E> iterator() {
return new ArrayListIterator();
}
private class ArrayListIterator implements Iterator<E> {
/** Number of elements remaining in this iteration */
private int remaining = size;
/** Index of element that remove() would remove, or -1 if no such elt */
private int removalIndex = -1;
/** The expected modCount value */
private int expectedModCount = modCount;
public boolean hasNext() {
return remaining != 0;
}
@SuppressWarnings("unchecked") public E next() {
ArrayList<E> ourList = ArrayList.this;
int rem = remaining;
if (ourList.modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
if (rem == 0) {
throw new NoSuchElementException();
}
remaining = rem - 1;
return (E) ourList.array[removalIndex = ourList.size - rem];
}
public void remove() {
Object[] a = array;
int removalIdx = removalIndex;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
if (removalIdx < 0) {
throw new IllegalStateException();
}
System.arraycopy(a, removalIdx + 1, a, removalIdx, remaining);
a[--size] = null; // Prevent memory leak
removalIndex = -1;
expectedModCount = ++modCount;
}
}
@Override public int hashCode() {
Object[] a = array;
int hashCode = 1;
for (int i = 0, s = size; i < s; i++) {
Object e = a[i];
hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
}
return hashCode;
}
@Override public boolean equals(Object o) {
if (o == this) {
return true;
}
if (!(o instanceof List)) {
return false;
}
List<?> that = (List<?>) o;
int s = size;
if (that.size() != s) {
return false;
}
Object[] a = array;
if (that instanceof RandomAccess) {
for (int i = 0; i < s; i++) {
Object eThis = a[i];
Object ethat = that.get(i);
if (eThis == null ? ethat != null : !eThis.equals(ethat)) {
return false;
}
}
} else { // Argument list is not random access; use its iterator
Iterator<?> it = that.iterator();
for (int i = 0; i < s; i++) {
Object eThis = a[i];
Object eThat = it.next();
if (eThis == null ? eThat != null : !eThis.equals(eThat)) {
return false;
}
}
}
return true;
}
private static final long serialVersionUID = 8683452581122892189L;
private void writeObject(ObjectOutputStream stream) throws IOException {
stream.defaultWriteObject();
stream.writeInt(array.length);
for (int i = 0; i < size; i++) {
stream.writeObject(array[i]);
}
}
private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
stream.defaultReadObject();
int cap = stream.readInt();
if (cap < size) {
throw new InvalidObjectException(
"Capacity: " + cap + " < size: " + size);
}
array = (cap == 0 ? EmptyArray.OBJECT : new Object[cap]);
for (int i = 0; i < size; i++) {
array[i] = stream.readObject();
}
}
}
相关文章
- 暂无相关文章
用户点评