Java 中的 List 是非常常用的数据类型。List 是有序的 Collection,Java List 一共有三个实现类,分别是:ArrayList、Vector、LinkedList
本文分析基于 JDK8
ArrayList
ArrayList 继承自 AbstractList,实现了 List 接口。底层基于数组实现容量大小动态变化,初始容量为 10,允许值为 null,有序,非线程安全,擅长随机访问
ArrayList 还实现了 RandomAccess、Cloneable、Serializable 接口,所以 ArrayList 是支持快速访问、复制、序列化的
RandomAccess
标记接口,用来表明其支持快速随机访问。如果是实现了这个接口的 List,那幺使用 for 循环的方式获取数据会优于用迭代器获取数据
Serializable
标记该类支持序列化
Cloneable
允许在堆中克隆出一块和原对象一样的对象,并将这个对象的地址赋予新的引用。ArrayList 提供的是一种深克隆机制,即克隆除自身对象以外的所有对象,包括自身所包含的所有对象实例。实现方式是先调用 super.clone() 方法克隆出一个新对象,然后再手动将原数组中的值复制到一个新的数组,并赋值
ArrayList 扩容机制
扩容机制应该是面试中最常问的了。其他关于 ArrayList 的一些琐碎方法我就不细说了,主要介绍一下扩容机制。首先了解一下 ArrayList 的成员属性
// 表示 ArrayList 的默认容量大小 private static final int DEFAULT_CAPACITY = 10; // 一个空的 Object 数组对象,长度为 0,如果使用默认构造函数创建,则 elementData 默认是该值 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 最大容量 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // ArrayList 中存放的实际元素个数 private int size; // 当前元素对象存放的数组,不参与序列化 transient Object[] elementData;
执行 add 方法时,会先执行 ensureCapacityInternal 方法,判断当前数组容量是否足够,不够就扩容。然后将待添加元素加到 elementData 末尾
public boolean add(E e) { ensureCapacityInternal(size + 1); elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } private void ensureExplicitCapacity(int minCapacity) { modCount++; // minCapacity > elementData.length 则扩容 if (minCapacity - elementData.length > 0) grow(minCapacity); }
再分析一下 ensureCapacityInternal 方法,此时 minCapacity 是 size + 1,这里有两个嵌套方法 calculateCapacity 和 ensureExplicitCapacity,作用分别如下:
calculateCapacity
如果当前数组为空,则先设置容量为默认值 10,此时还未初始化数组
ensureExplicitCapacity
确认实际的容量,如果不够就扩容,关键的扩容函数 grow 就在这里
扩展数组大小,首先将容量扩大为原来的 1.5 倍,如果数组是空数组,则将数组初始化,默认容量为 10,如果不是,再判断是否超出最大容量,超过直接赋予最大值,否则赋予新值,复制原数组到新数组
private void grow(int minCapacity) { // 扩容前的容量 int oldCapacity = elementData.length; // oldCapacity 右移一位,等于除以二 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); }
LinkedList
LinkedList 继承自 AbstractSequentialList,实现了 List 和 Deque 接口,基于双向链表实现,每个节点都包含了对前一个和后一个元素的引用,可以被当作堆栈、队列或双端队列进行操作,有序,非线程安全
// 指向链表的第一个节点 transient Node<E> first; // 指向链表的最后一个节点 transient Node<E> last;
JDK8 中 LinkedList 有一个静态内部类 Node,它包括的属性有:当前节点所包含的值,上一个节点,下一个节点
private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }
除此之外就没啥好分析的了,LinkedList 不存在容量不足的问题,克隆函数也是将所有元素全都克隆到新的 LinkedList 对象
Vector
Vector 是一个矢量队列,和 ArrayList 类似,继承自 AbstractList,实现了 List 接口,就连额外接口也是一样。不同之处在于:
Vector 使用 synchronized 保证线程同步
Vector 中遗留了大量传统的方法,这些方法不属于集合框架
Vector 有四个构造方法
// 创建一个默认大小为 10 的向量 public Vector() // 创建指定大小的向量 public Vector(int initialCapacity) // 创建指定大小的向量,并且指定增量。增量表示向量每次增加的元素数目 public Vector(int initialCapacity, int capacityIncrement) // 创建一个包含集合 c 元素的向量 public Vector(Collection<? extends E> c)
Vector 的数据结构和 ArrayList 差不多,它包含了三个成员变量:
// 存放元素的动态数组 protected Object[] elementData; // 动态数组的实际大小 protected int elementCount; // 动态数组的增长系数 protected int capacityIncrement;
随着 Vector 中元素的增加,Vector 的容量也会动态增长,capacityIncrement 是与容量增长相关的增长系数,具体增长细节在 grow 函数中,和 ArrayList 类似
private void grow(int minCapacity) { int oldCapacity = elementData.length; // 如果 capacityIncrement > 0,新的容量大小 = 旧的容量大小 + 增长系数 // 否则容量扩大为原来的两倍 int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); }
Stack
Stack 是 Vector 的子类,实现了一个标准的后进先出的栈。Stack 也是通过数组实现的,当然了,我们也可以将 LinkedList 当作栈来使用
Stack 只定义了默认构造函数,用来创建一个空栈
public Stack()
Stack 除了具有 Vector 的所有 API,还有自己实现的方法
// 判断堆栈是否为空 public boolean empty() // 查看堆栈顶部的对象,但不从堆栈中移除它 public synchronized E peek() // 移除堆栈顶部的对象,并作为此函数的值返回该对象 public synchronized E pop() // 把对象压入堆栈顶部 public E push(E item) // 返回对象在堆栈中的位置,以 1 为基数 public synchronized int search(Object o)
Stack 的扩容机制基于 Vector,不过由于没有指定增长系数,所有默认为 0,每次扩容数组长度增大为原来的两倍
Be First to Comment