Java集合-ArrayList源码分析

1.结构特性
2.构造函数
3.成员变量
4.常用的成员方法
5.底层数组扩容原理
6.序列化原理
7.集合元素排序
8.迭代器的实现
9.总结

1.结构特性

Java ArrayList类使用动态数组来存储元素。它就像一个数组，但是没有大小限制。可以随时添加或删除元素。有以下特性：

底层使用数组来存储元素
没有固定的容量限制，底层数组会自动扩容
允许包含null值
允许包含重复的值
保存了元素的添加顺序
不是线程安全的

2.构造函数

// 1.构建一个空的数组列表

ArrayList()

// 2.构造了一个包含指定元素集合的数组列表

ArrayList(Collection<? extends E> c)

// 3.构建一个数组列表，指定初始化容量

ArrayList(int initialCapacity)

3.成员变量

// ArryList包含的元素数量

private int size;

// ArrayList底层装载元素的数组

transient Object[] elementData;

4.常用的成员方法

// 1.增加元素到数组列表尾部

boolean add(E e)

// 2.增加元素到指定位置

void add(int index, E element)

// 3.获取指定位置的元素

E get(int index)

// 4.设置指定位置的元素

E set(int index, E element)

// 5.检查包含指定元素

E remove(int index)

// 6.返回指定元素在此列表中首次出现的索引

int indexOf(Object o)

// 7.返回一个数组包含所有的元素

Object[] toArray()

// 8.返回此列表中指定的fromIndex（包括）和toIndex（不包括）之间的视图。

List<E> subList(int fromIndex, int toIndex)

// 9.移除数组列表中所有的元素

void clear()

// 10.返回true表示数组列表中没有任何元素

boolean isEmpty()

// 11.数组列表中包含的元素个数

int size()

// 12.检查并增加ArrayList实例的容量，以确保它至少可以容纳参数指定的元素数量。

void ensureCapacity(int minCapacity)

5.底层数组扩容原理

1.添加元素的时候，首先检查并增加底层elementData的容量，以确保它至少可以容纳指定的元素数量。

public boolean add(E e) {

    // 检查容量

    ensureCapacityInternal(size + 1);  // Increments modCount!!

    ......

}

2.新的容量是在原容量的基础上增加 50 %

 private void grow(int minCapacity) {

      // overflow-conscious code

      int oldCapacity = elementData.length;

      // 计算新容量

      int newCapacity = oldCapacity + (oldCapacity >> 1);

      ......

}

3.将elementData 中元素拷贝到一个新数组，索引位置的元素保持不变，然后将新的数组实例赋值给 elementData。

private void grow(int minCapacity) {

      ......

      // 拷贝新数组

      elementData = Arrays.copyOf(elementData, newCapacity);

}

6.序列化原理

1.通过ArrayList的声明可以看到实现了Serializable接口，对象可以序列化。

public class ArrayList<E> extends AbstractList<E>

        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{

      ......

}

2.序列化时调用 writeObject() 方法将size和element写入ObjectOutputStream。

private void writeObject(java.io.ObjectOutputStream s)

        throws java.io.IOException{

      ......

}

3.反序列化时调用readObject，从ObjectInputStream获取size和element，再恢复到elementData。

private void readObject(java.io.ObjectInputStream s)

        throws java.io.IOException, ClassNotFoundException {

      ......

}

4.成员变量 elementData 是一个缓存数组，会预留一些容量，使用了 transient 关键字修饰，不会序列化到目的地中，从而节省时间和空间。

7.集合元素排序

1.使用Collections.sort()方法传入 ArrayList 实例进行排序（字典序）

@Test

public void testArrayListSort () {

    ArrayList<String> list = new ArrayList<>(10);

    list.add("one");

    list.add("two");

    Collections.sort(list);

    System.out.println(list);   // output: [one, two]

}

2.使用Collections.sort()方法传入 ArrayList 实例和Commparator接口的类的对象，实现自定义排序。

@Test

public void testArrayListSort () {

    ArrayList<Integer> list = new ArrayList<>(10);

    list.add(20);

    list.add(18);

    Collections.sort(list, new Comparator<Integer>() {

        @Override

        public int compare(Integer o1, Integer o2) {

            return o1 - o2;

        }

    });

    System.out.println(list);   // output: [18, 20]

}

3.使用成员方法 sort() 传入Commparator接口的类的对象，实现自定义排序。

@Test

public void testArrayListSort () {

    ArrayList<Integer> list = new ArrayList<>(10);

    list.add(20);

    list.add(18);

    list.sort(new Comparator<Integer>() {

        @Override

        public int compare(Integer o1, Integer o2) {

            return o1 - o2;

        }

    });

    System.out.println(list);   // output: [18, 20]

}

8.迭代器的实现

1.ArrayList 内部类 Itr 实现了Iterator 接口用来遍历 elementData 中的元素，调用实例的成员方法 iterator() 返回迭代器。

private class Itr implements Iterator<E> {

      ......

}

2.Iterator支持从前向后顺次遍历elementData中元素。

3.Itr类实现迭代器 Iterator的方法：

// 判断指针cursor是否到达elementData数组右边界

public boolean hasNext() {

      return cursor != size;

}

public E next() {

  // 返回指针cursor指向的元素

  int i = cursor;

  ......

  // cursor右移动一位

  cursor = i + 1;

  return (E) elementData[lastRet = i];

}

public void remove() {

    ......

    try {

        // 将新近返回的元素删除

        ArrayList.this.remove(lastRet);

        cursor = lastRet;

        lastRet = -1;

        expectedModCount = modCount;

    } catch (IndexOutOfBoundsException ex) {

        throw new ConcurrentModificationException();

    }

}

9.总结

以上就是对ArrayList的理解，如果有理解不正确的地方，欢迎指正，最后，补充一张脑图：

巴特西