数据结构-01 ArrayList源码解析

时间:2021-12-21 10:18:07

本文根据Android API 21

ArrayList继承AbstractList那么首先分析继承自AbstractList的方法。

构造方法

construct01 初始化容量的构造方法

//声明一个初始化的容量来构造一个ArrayList对象的实例
public ArrayList(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException("capacity < 0: " + capacity);
}
//如果传入的容量为空,ArrayList的数组的大小就是0.
//如果传入的容量不为空,那么ArrayList的数组的大小就为传入的容量值
array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);
}

construct02 无参构造方法

 public ArrayList() {
array = EmptyArray.OBJECT;
}

construct03 构造一个包含的元素为指定的集合

用我自己的理解就是数组的每个元素是一个集合比如[{1,2,3},{9,4,3}]。

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];
//这里把数组a拷贝到newArray,这样做的目的是不直接操作集合的元素。
System.arraycopy(a, 0, newArray, 0, a.length);
a = newArray;
}
array = a;
size = a.length;
}

重新解释一下这里的拷贝思想,首先把转成数组赋值给a,再把a拷贝的值付给newArray.然后再把newArray的值付给a.这样就不会影响传入的集合的值。
数据结构-01 ArrayList源码解析

ArrayList是继承自AbstractList

继承自AbstractList的方法

1 add(E object) 向集合中插入元素

@Override public boolean add(E object) {
//定义一个和全局数组相等的局部数组
Object[] a = array;
int s = size;
//这里我不明白为什么要判断 我觉得size是array的长度,所以肯定有s==a.length
"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;
}
  • 先分析一下三个数组a,array,newArray的关系和作用

数据结构-01 ArrayList源码解析
可以看出数组a的作用就是相当于一个桥梁的作用

  • 在看一下size和array.length的关系
    在三个构造方法中 只有在ArrayList(Collection<? extends E> collection)这个方法中初始化了size,所以此时size=array.length.
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;
}

因为size定义时没有赋值,所以size的默认值为0.所以下面的构造方法。size = array.length=0.

public ArrayList() {
array = EmptyArray.OBJECT;
}

也就是说只要在调用下面这个构造方法,且容量不等于0时才会有size!=a.length.此时说明array数据为空,但是数据长度不为0.所以此时调用add方法可以直接添加元素。

public ArrayList(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException("capacity < 0: " + capacity);
}
array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);
}

2 add(int index, E object) 在集合中特定位置插入元素

@Override 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++;
}
  1. 数组没有满时
    if (s < a.length) {
    System.arraycopy(a, index, a, index + 1, s - index);
    }

    数据结构-01 ArrayList源码解析
  2. 数组已经满了
    数据结构-01 ArrayList源码解析

这里的扩容根据 当前的容量是5个5<6,所以increment = MIN_CAPACITY_INCREMENT =12。
所以currentCapacity+increment = 17

private static int newCapacity(int currentCapacity) {
int increment = (currentCapacity < (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : currentCapacity >> 1);
return currentCapacity + increment;
}

3 addAll(Collection< ? extends E> collection) 插入一个集合

@Override public boolean addAll(Collection<? extends E> collection) {
//先把集合转成数组
Object[] newPart = collection.toArray();
//数组的长度
int newPartSize = newPart.length;
if (newPartSize == 0) {
return false;
}
//定义局部数组
Object[] a = array;
//array数组的真实元素的个数
int s = size;
//添加后array数组的元素总个数
int newSize = s + newPartSize; // If add overflows, arraycopy will fail
//如果array添加元素后的总个数比array数组的长度大 需要扩容
if (newSize > a.length) {
//扩容之后的总容量
int newCapacity = newCapacity(newSize - 1); // ~33% growth room
//扩容后的数组
Object[] newArray = new Object[newCapacity];
//先将array原有的数组拷贝到newArray
System.arraycopy(a, 0, newArray, 0, s);
//再把newArray赋值给array 这样array就是实现了扩容
array = a = newArray;
}
//再将需要添加到array的数组拷贝到array
System.arraycopy(newPart, 0, a, s, newPartSize);
size = newSize;
modCount++;
return true;
}

这里的添加集合方法比较简单。概括来说就是在原有的数组基础上直接添加新的数组。添加之前先判断。如果添加后的数组真实元素的个数比array的数组长度长。那么就要先扩容。然后再用System.arraycopy方法实现拷贝。这里就不画图了。和之前的大同小异。

4 addAll(int index, Collection< ? extends E> collection) 在指定位置插入一个集合

@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) {
//把array数组中的index后的元素拷贝到index+newPartSize之后的位置。也就是说要给新插入的元素腾地方。
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);
//这里和数组容量足够大的一样,从index的位置拷贝到index+newPartSize的位置。
System.arraycopy(a, index, newArray, index + newPartSize, s-index);
array = a = newArray;
}
System.arraycopy(newPart, 0, a, index, newPartSize);
size = newSize;
modCount++;
return true;
}

此方法和第三个方法差不多。只是多了个指定位置插入集合。所以多了个先把index之后的元素向后挪的步骤。然后再把要插入的元素插入的index位置。

5 clear() 把所有的元素置空

 @Override public void clear() {
if (size != 0) {
//这个方法看下面
Arrays.fill(array, 0, size, null);
size = 0;
modCount++;
}
}
public static void fill(Object[] array, int start, int end, Object value) {
Arrays.checkStartAndEnd(array.length, start, end);
for (int i = start; i < end; i++) {
array[i] = value;
}
}

这个方法fill顾名思义 填充方法。遍历指定数组额起始到结束位置。然后用指定的值替换。所以这个方法是把数组中真实数据的元素替换为空。并不会改变数组的长度。

6 equals(Object object) 比较传入对象和当前ArrayList的内存地址是否相等。

@Override public boolean equals(Object o) {
//如果内存地址相同,返回true
if (o == this) {
return true;
}
//如果传入的对象不是一个集合
if (!(o instanceof List)) {
return false;
}
"这里我不明白为什么要强转成集合 因为已经是集合"
List<?> that = (List<?>) o;
int s = size;
//如果传入的集合和当前的ArrayList的元素数量是否相等
if (that.size() != s) {
return false;
}
Object[] a = array;
//如果that是ArrayList的实例
if (that instanceof RandomAccess) {
//遍历当前array数组的元素
for (int i = 0; i < s; i++) {
Object eThis = a[i];
Object ethat = that.get(i);
//比较array传入的that数组中的每个元素是否相等
if (eThis == null ? ethat != null : !eThis.equals(ethat)) {
return false;
}
}
} else { // Argument list is not random access; use its iterator
Iterator<?> it = that.iterator();
//遍历array中的元素
for (int i = 0; i < s; i++) {
Object eThis = a[i];
//迭代eThat中的元素
Object eThat = it.next();
//对比ethat和eThis中的每个元素是否相等
if (eThis == null ? eThat != null : !eThis.equals(eThat)) {
return false;
}
}
}
return true;
}

7 get(int index) 根据下标值 获取对应的元素

@SuppressWarnings("unchecked") @Override public E get(int index) {
if (index >= size) {
throwIndexOutOfBoundsException(index, size);
}
return (E) array[index];
}

根据下标值返回array数组中对应的元素。

8 hashCode() 计算哈希值

@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;
}

这个方法自己id那定义了哈希值的算法。没什么可说的。这个hashCode值很大啊,遍历集合的所有元素,每次*31还要再加上每个元素的哈希值。

9 indexOf(Object object) 在集合中找到和object值相等的第一个元素的下标值。

@Override public int indexOf(Object object) {
Object[] a = array;
int s = size;
//首先判断要查找的内容是不是空
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;
}

首先判空是因为空(a[i] == null)和非空(object.equals(a[i])) 时查找的方法不同。

10 iterator() 获得当前集合的迭代器

@Override public Iterator<E> iterator() {
return new ArrayListIterator();
}

这个方法只有一行代码,直接new ArrayListIterator(),并返回。
上面用到了迭代器,所以先看下迭代器这个内部类

ArrayListIterator

首先看下内部类的成员变量

表示未被迭代的数量

 private int remaining = size;

将要被移除元素的下标值 在next()方法中被赋值。也就是说这个值表示当前被迭代的元素的下标值,所以只有先调用next()方法,才能调用remove()方法。否则会抛异常。

private int removalIndex = -1;

//记录array数组被操作的次数

 private int expectedModCount = modCount;

ArrayListIterator中的方法

1 hasNext()判断当前是否还有未被迭代的元素

public boolean hasNext() {
return remaining != 0;
}

如果没有未被迭代的返回false.

2 next() 迭代集合的元素

@SuppressWarnings("unchecked") public E next() {
//当前的集合
ArrayList<E> ourList = ArrayList.this;
int rem = remaining;
//判断这个有什么卵用吗 看了下整个内部类,这两个值一直是相等的
if (ourList.modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
//如果集合的元素个数是0会抛异常
if (rem == 0) {
throw new NoSuchElementException();
}
//每迭代一次,剩余迭代数量-1
remaining = rem - 1;
//返回当前迭代的元素
return (E) ourList.array[removalIndex = ourList.size - rem];
}

每迭代一次,返回被迭代的元素

3 remove()

 public void remove() {
//定义局部数组
Object[] a = array;
//这个成员变量之前已经解释的很清楚了。
int removalIdx = removalIndex;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
//表示没有进行迭代就直接调用remove()方法。
if (removalIdx < 0) {
throw new IllegalStateException();
}

System.arraycopy(a, removalIdx + 1, a, removalIdx, remaining);
a[--size] = null; // Prevent memory leak
//重置removalIndex 为-1
removalIndex = -1;
expectedModCount = ++modCount;
}

数据结构-01 ArrayList源码解析
这样可能更把remove()方法表示的更直观。

11 lastIndexOf(Object object) 在集合中找到和object值相等的最后一个元素的下标值。

@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;
}

这个方法和第九个方法是一样的,只是遍历的时候,第9个方法是从前往后遍历,这个方法是从后往前遍历。

12 remove(int index) 根据下标值移除指定元素

@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];
System.arraycopy(a, index + 1, a, index, --s - index);
a[s] = null; // Prevent memory leak
size = s;
modCount++;
return result;
}

这个方法和迭代器里的方法几乎一样。只是这个方法将移除的元素返回。而迭代器的remove()方法没有返回值。可以参考内部类ArrayListIterator中的第三个remove方法。

13removeRange(int fromIndex, int 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);
}
//表示把array数组中下标值为toIndex以后的元素移到下标值为fromIndex的后边
System.arraycopy(a, toIndex, a, fromIndex, s - toIndex);
int rangeSize = toIndex - fromIndex;
//将下标值为s-rangSize后的数据置空。
Arrays.fill(a, s - rangeSize, s, null);
size = s - rangeSize;
modCount++;
}

14 set(int index, E object) 替换指定下标元素的值

@Override public E set(int index, E object) {
Object[] a = array;
if (index >= size) {
throwIndexOutOfBoundsException(index, size);
}
@SuppressWarnings("unchecked") E result = (E) a[index];
//核心代码 将array数组的index下标的值替换为objext.
a[index] = object;
return result;
}

至此,AbstractList< E >的方法分析完了,接下来看继承自ArrayList爷爷AbstractCollection< E >的方法。

继承自AbstractCollection< E >的方法

1 contains(Object object) 判断集合中是否包含指定元素

 @Override public boolean contains(Object object) {
Object[] a = array;
int s = size;
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;
}

这个方法和第九个方法indexOf()方法类似。indexOf()方法找到指定元素的下标值,此方法是判断是否包含指定元素。

2 isEmpty()判断集合是否为空

@Override public boolean isEmpty() {
return size == 0;
}

如果array数组的实际元素个数为0,就返回true,否则返回false.

3 size() 集合元素的个数

@Override public int size() {
return size;
}

返回array数组的实际元素个数

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++;
}

此方法目的是去掉集合中空数据,只留下aray中真实的元素。有点说不明白。大概的意思就是把占着茅坑不拉屎的整死。

实现了Cloneable 可以克隆

@Override public Object clone() {
try {
ArrayList<?> result = (ArrayList<?>) super.clone();
result.array = array.clone();
return result;
} catch (CloneNotSupportedException e) {
throw new AssertionError();
}
}

赋值和集合相同的集合。

简单的总结下ArrayLis。ArrayList通过操作一个数组来实现增删改查等操作。主要通过System.copy来移动数组内的元素。概括来说ArrayList是一个封装了的数组。他有以下特点:

  • ArrayList中的数据是连续的,所以对于数据的查询效率较高。
  • 增删数据通过移动数组来实现。所以增删数据效率不高。

    遍历ArrayList并删除元素时注意:
    不要直接使用for循环去遍历集合然后直接删除元素,因为ArrayList的remove方法会移动数组。这样会导致下次遍历的时候漏掉元素。应该用list.itrator()方法.例如:

Iterator<String> it = list.iterator();
while (it.hasNext())
{
String s = it.next();
if (s.equals("b"))
{
it.remove();
}
}

以上内容都是我自己分析和思考的,因为能力有限,有错误或不足之处欢迎指正。毕竟是我写的第一篇比较完整的博客。谢谢!