ArrayList 的一些认识：
- 非线程安全的动态数组（Array升级版），支持动态扩容
- 实现 List 接口、底层使用数组保存所有元素，其操作基本上是对数组的操作，允许null值
- 实现了 RandmoAccess 接口，提供了随机访问功能
- 线程安全可见Vector，实时同步
- 适用于访问频繁场景，频繁插入或删除场景请选用linkedList
■ 类定义
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
- 继承 AbstractList，实现了 List，它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能
- 实现 RandmoAccess 接口，实现快速随机访问：通过元素的序号快速获取元素对象
- 实现 Cloneable 接口，重写 clone()，能被克隆（浅拷贝）
- 实现 java.io.Serializable 接口，支持序列化
■ 全局变量
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to
* DEFAULT_CAPACITY when the first element is added.
* ArrayList底层实现为动态数组； 对象在存储时不需要维持，java的serialzation提供了持久化
* 机制，我们不想此对象被序列化，所以使用 transient
*/
private transient Object[] elementData;
/**
* The size of the ArrayList (the number of elements it contains).
* 数组长度 ：注意区分长度（当前数组已有的元素数量）和容量（当前数组可以拥有的元素数量）的概念
* @serial
*/
private int size;
/**
* The maximum size of array to allocate.Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in OutOfMemoryError:
* Requested array size exceeds VM limit
* 数组所能允许的最大长度；如果超出就会报`内存溢出异常` -- 可怕后果就是宕机
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
■ 构造器
/**
* Constructs an empty list with the specified initial capacity.
* 创建一个指定容量的空列表
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity is negative
*/
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
this.elementData = new Object[initialCapacity];
}
/**
* Constructs an empty list with an initial capacity of ten.
* 默认容量为10
*/
public ArrayList() {
this(10);
}
/**
* Constructs a list containing the elements of the specified collection,
* in the order they are returned by the collection's iterator.
* 接受一个Collection对象直接转换为ArrayList
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null 万恶的空指针异常
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();//获取底层动态数组
size = elementData.length;//获取底层动态数组的长度
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
■主要方法
- add()
- 从源码上看，ArrayList 一般在尾部插入元素，支持动态扩容
- 不推荐使用频繁插入/删除是因为在执行add()/remove() 会调用非常耗时的 System.arraycopy()，频繁插入/删除场景请选用 LinkedList
/**
* Appends the specified element to the end of this list.
* 使用尾插入法，新增元素插入到数组末尾
* 由于错误检测机制使用的是抛异常，所以直接返回true
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
//调整容量，修改elementData数组的指向; 当数组长度加1超过原容量时，会自动扩容
ensureCapacityInternal(size + 1); // Increments modCount!! add属于结构性修改
elementData[size++] = e;//尾部插入，长度+1
return true;
}
/**
* Inserts the specified element at the specified position in this list.
* Shifts the element currently at that position (if any) and any subsequent elements to
* the right (adds one to their indices).
* 支持插入一个新元素到指定下标
* 该操作会造成该下标之后的元素全部后移（使用时请慎重，避免数组长度过大）
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
//下标边界校验，不符合规则 抛出 `IndexOutOfBoundsException`
rangeCheckForAdd(index);
//调整容量，修改elementData数组的指向; 当数组长度加1超过原容量时，会自动扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
//注意是在原数组上进行位移操作，下标为 index+1 的元素统一往后移动一位
System.arraycopy(elementData, index, elementData, index + 1,size - index);
elementData[index] = element;//当前下标赋值
size++;//数组长度+1
}
- ensureCapacity() : 扩容，1.8 有个默认值的判断
//1.8 有个默认值的判断
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY; if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
} private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
- set() / get()： 直接操作下标指针
/**
* Replaces the element at the specified position in this list with
* the specified element.
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
rangeCheck(index); //检测插入的位置是否越界 E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
rangeCheck(index); return elementData(index);
}
- remove()： 移除其实和add差不多，也是用的是 System.arrayCopy(...)
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their indices).
*
* 移除指定下标元素，同时大于该下标的所有数组元素统一左移一位
*
* @param index the index of the element to be removed
* @return the element that was removed from the list 返回原数组元素
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
rangeCheck(index);//下标边界校验
E oldValue = elementData(index);//获取当前坐标元素
fastRemove(int index);//这里我修改了一下源码，改成直接用fastRemove方法，逻辑不变
return oldValue;//返回原数组元素
}
/**
* Removes the first occurrence of the specified element from this list,if it is present.
* If the list does not contain the element, it is unchanged.
* More formally, removes the element with the lowest index <tt>i</tt> such that
* <tt>(o==null?get(i)==null:o.equals(get(i)))</tt> (if such an element exists).
* Returns <tt>true</tt> if this list contained the specified element
* (or equivalently, if this list changed as a result of the call).
* 直接移除某个元素：
* 当该元素不存在，不会发生任何变化
* 当该元素存在且成功移除时，返回true，否则false
* 当有重复元素时，只删除第一次出现的同名元素 ：
* 例如只移除第一次出现的null（即下标最小时出现的null）
* @param o element to be removed from this list, if present
* @return <tt>true</tt> if this list contained the specified element
*/
public boolean remove(Object o) {
//按元素移除时都需要按顺序遍历找到该值，当数组长度过长时，相当耗时
if (o == null) {//ArrayList允许null，需要额外进行null的处理（只处理第一次出现的null）
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
- 封装 fastRemove()
/*
* Private remove method that skips bounds checking and does not return the value removed.
* 私有方法，除去下标边界校验以及不返回移除操作的结果
*/
private void fastRemove(int index) {
modCount++;//remove操作属于结构性改动，modCount计数+1
int numMoved = size - index - 1;//需要左移的长度
if (numMoved > 0)
//大于该下标的所有数组元素统一左移一位
System.arraycopy(elementData, index+1, elementData, index,numMoved);
elementData[--size] = null; // Let gc do its work 长度-1，同时加快gc
}
■ 遍历、排序
/**
* Created by meizi on 2017/7/31.
* List<数据类型> 排序、遍历
*/
public class ListSortTest {
public static void main(String[] args) {
List<Integer> nums = new ArrayList<Integer>();
nums.add(3);
nums.add(5);
nums.add(1);
nums.add(0); // 遍历及删除的操作
/*Iterator<Integer> iterator = nums.iterator();
while (iterator.hasNext()) {
Integer num = iterator.next();
if(num.equals(5)) {
System.out.println("被删除元素：" + num);
iterator.remove(); //可删除
}
}
System.out.println(nums);*/ //工具类(Collections) 进行排序
/*Collections.sort(nums); //底层为数组对象的排序，再通过ListIterator进行遍历比较，取替
System.out.println(nums);*/ //②自定义排序方式
/*nums.sort(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
if(o1 > o2) {
return 1;
} else if (o1 < o2) {
return -1;
} else {
return 0;
}
}
});
System.out.println(nums);*/ //遍历 since 1.8
Iterator<Integer> iterator = nums.iterator();
iterator.forEachRemaining(obj -> System.out.print(obj)); //使用lambda 表达式 /**
* Objects 展示对象各种方法，equals, toString, hash, toString
*/
/*default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}*/
} }
■ JDK 1.8 新增接口/类方法
public interface Collection<E> extends Iterable<E> {
.....
//1.8新增方法：提供了接口默认实现，返回分片迭代器
@Override
default Spliterator<E> spliterator() {
return Spliterators.spliterator(this, 0);
}
//1.8新增方法：提供了接口默认实现，返回串行流对象
default Stream<E> stream() {
return StreamSupport.stream(spliterator(), false);
}
//1.8新增方法：提供了接口默认实现，返回并行流对象
default Stream<E> parallelStream() {
return StreamSupport.stream(spliterator(), true);
}
/**
* Removes all of the elements of this collection that satisfy the given
* predicate. Errors or runtime exceptions thrown during iteration or by
* the predicate are relayed to the caller.
* 1.8新增方法：提供了接口默认实现，移除集合内所有匹配规则的元素，支持Lambda表达式
*/
default boolean removeIf(Predicate<? super E> filter) {
//空指针校验
Objects.requireNonNull(filter);
//注意：JDK官方推荐的遍历方式还是Iterator，虽然forEach是直接用for循环
boolean removed = false;
final Iterator<E> each = iterator();
while (each.hasNext()) {
if (filter.test(each.next())) {
each.remove();//移除元素必须选用Iterator.remove()方法
removed = true;//一旦有一个移除成功，就返回true
}
}
//这里补充一下：由于一旦出现移除失败将抛出异常，因此返回false指的仅仅是没有匹配到任何元素而不是运行异常
return removed;
}
}
public interface Iterable<T>{
.....
//1.8新增方法：提供了接口默认实现，用于遍历集合
default void forEach(Consumer<? super T> action) {
Objects.requireNonNull(action);
for (T t : this) {
action.accept(t);
}
}
//1.8新增方法：提供了接口默认实现，返回分片迭代器
default Spliterator<T> spliterator() {
return Spliterators.spliteratorUnknownSize(iterator(), 0);
}
}
public interface List<E> extends Collection<E> {
//1.8新增方法：提供了接口默认实现，用于对集合进行排序，主要是方便Lambda表达式
default void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}
//1.8新增方法：提供了接口默认实现，支持批量删除，主要是方便Lambda表达式
default void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final ListIterator<E> li = this.listIterator();
while (li.hasNext()) {
li.set(operator.apply(li.next()));
}
}
/**
* 1.8新增方法：返回ListIterator实例对象
* 1.8专门为List提供了专门的ListIterator，相比于Iterator主要有以下增强：
* 1.ListIterator新增hasPrevious()和previous()方法，从而可以实现逆向遍历
* 2.ListIterator新增nextIndex()和previousIndex()方法，增强了其索引定位的能力
* 3.ListIterator新增set()方法，可以实现对象的修改
* 4.ListIterator新增add()方法，可以向List中添加对象
*/
ListIterator<E> listIterator();
}
■ 并行分片迭代器
- 并行分片迭代器是Java为了并行遍历数据源中的元素而专门设计的迭代器
- 并行分片迭代器借鉴了Fork/Join框架的核心思想：用递归的方式把并行的任务拆分成更小的子任务，然后把每个子任务的结果合并起来生成整体结果
- 并行分片迭代器主要是提供给Stream，准确说是提供给并行流使用，使用时推荐直接用Stream即可
default Stream<E> parallelStream() {//并行流
return StreamSupport.stream(spliterator(), true);//true表示使用并行处理
}
static final class ArrayListSpliterator<E> implements Spliterator<E> {
private final ArrayList<E> list;
//起始位置（包含），advance/split操作时会修改
private int index; // current index, modified on advance/split
//结束位置（不包含），-1 表示到最后一个元素
private int fence; // -1 until used; then one past last index
private int expectedModCount; // initialized when fence set
/** Create new spliterator covering the given range */
ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
int expectedModCount) {
this.list = list; // OK if null unless traversed
this.index = origin;
this.fence = fence;
this.expectedModCount = expectedModCount;
}
/**
* 获取结束位置，主要用于第一次使用时对fence的初始化赋值
*/
private int getFence() { // initialize fence to size on first use
int hi; // (a specialized variant appears in method forEach)
ArrayList<E> lst;
if ((hi = fence) < 0) {
//当list为空，fence=0
if ((lst = list) == null)
hi = fence = 0;
else {
//否则，fence = list的长度
expectedModCount = lst.modCount;
hi = fence = lst.size;
}
}
return hi;
}
/**
* 对任务(list)分割，返回一个新的Spliterator迭代器
*/
public ArrayListSpliterator<E> trySplit() {
//二分法
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
return (lo >= mid) ? null : // divide range in half unless too small 分成两部分，除非不够分
new ArrayListSpliterator<E>(list, lo, index = mid,expectedModCount);
}
/**
* 对单个元素执行给定的执行方法
* 若没有元素需要执行，返回false；若可能还有元素尚未执行，返回true
*/
public boolean tryAdvance(Consumer<? super E> action) {
if (action == null)
throw new NullPointerException();
int hi = getFence(), i = index;
if (i < hi) {//起始位置 < 终止位置 -> 说明还有元素尚未执行
index = i + 1; //起始位置后移一位
@SuppressWarnings("unchecked") E e = (E)list.elementData[i];
action.accept(e);//执行给定的方法
if (list.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
return false;
}
/**
* 对每个元素执行给定的方法，依次处理，直到所有元素已被处理或被异常终止
* 默认方法调用tryAdvance方法
*/
public void forEachRemaining(Consumer<? super E> action) {
int i, hi, mc; // hoist accesses and checks from loop
ArrayList<E> lst; Object[] a;
if (action == null)
throw new NullPointerException();
if ((lst = list) != null && (a = lst.elementData) != null) {
if ((hi = fence) < 0) {
mc = lst.modCount;
hi = lst.size;
}
else
mc = expectedModCount;
if ((i = index) >= 0 && (index = hi) <= a.length) {
for (; i < hi; ++i) {
@SuppressWarnings("unchecked") E e = (E) a[i];
action.accept(e);
}
if (lst.modCount == mc)
return;
}
}
throw new ConcurrentModificationException();
}
/**
* 计算尚未执行的任务个数
*/
public long estimateSize() {
return (long) (getFence() - index);
}
/**
* 返回当前对象的特征量
*/
public int characteristics() {
return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
}
}
■ list 与 Array 的转换问题
- Object[] toArray(); 可能会产生 ClassCastException
- <T> T[] toArray(T[] contents) -- 调用 toArray(T[] contents) 能正常返回 T[]
public class ListAndArray {
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("java");
list.add("C++");
String[] strings = list.toArray(new String[list.size()]); //使用泛型可避免类型转换的异常，因为java不支持向下转换
System.out.println(strings[0]);
}
}
■ 关于Vector 就不详细介绍了，因为官方也并不推荐使用： (JDK 1.0)
- 矢量队列，作用等效于ArrayList，线程安全
- 官方不推荐使用该类，非线程安全推荐 ArrayList，线程安全推荐 CopyOnWriteList
- 区别于arraylist, 所有方法都是 synchronized 修饰的，所以是线程安全
-----------------------------------------
2018.8.21 新增ArrayList 1.8 功能