数据结构-01 ArrayList源码解析

本文根据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++;
    }

数组没有满时
if (s < a.length) { System.arraycopy(a, index, a, index + 1, s - index); }
数组已经满了

这里的扩容根据当前的容量是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();
            }
        }

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

秒客网

数据结构-01 ArrayList源码解析

本文根据Android API 21

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

构造方法

construct01 初始化容量的构造方法

construct02 无参构造方法

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

继承自AbstractList的方法

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

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

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

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

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

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

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

8 hashCode() 计算哈希值

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

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

ArrayListIterator

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

ArrayListIterator中的方法

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

2 next() 迭代集合的元素

3 remove()

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

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

13removeRange(int fromIndex, int toIndex) 移除指定范围内的所有元素。

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

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

继承自AbstractCollection< E >的方法

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

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

3 size() 集合元素的个数

ArrayList原生方法

实现了Cloneable 可以克隆

相关文章

数据结构-01 ArrayList源码解析

本文根据Android API 21

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

构造方法

construct01 初始化容量的构造方法

construct02 无参构造方法

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

继承自AbstractList的方法

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

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

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

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

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

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

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

8 hashCode() 计算哈希值

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

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

ArrayListIterator

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

ArrayListIterator中的方法

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

2 next() 迭代集合的元素

3 remove()

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

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

13removeRange(int fromIndex, int toIndex) 移除指定范围内的所有元素。

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

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

继承自AbstractCollection< E >的方法

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

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

3 size() 集合元素的个数

ArrayList原生方法

实现了Cloneable 可以克隆

相关文章

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