1.List集合概要
2.Iterable接口
1.概要
2.重要方法
- forEach方法：对Collection集合中的每个对象进行消费
List<Student> list = Stream.generate(() -> new Student("张三", 23)).limit(100).collect(Collectors.toList());
list.forEach(System.out::println);
- spliterator方法：获取Spliterator迭代器
3.Collection接口
1.重要方法
- spliterator()：创建Spliterator
- stream()：创建串行流Stream
- parallelStream()：创建并行流Stream
4.RandomAccess接口
1.概要
这是一种标识型接口，用于标识某个类具有某种功能特性的接口。
5.Vector
1.Vector集合概要
Vector是一个线程安全的集合，其中的大部分方法都加了synchronized关键字。
2.重要变量
- Vector中重要的变量信息
// 集合Vector存放对象的数组
protected Object[] elementData;
// 集合Vector存储的对象数量
protected int elementCount;
// elementData数组每次扩容的大小
protected int capacityIncrement;
3.Vector的扩容操作
- 初始化Vector的扩容操作
// 1. 指定了初始化容量和每次扩容时的增量
// 则下次扩容为initialCapacity + capacity，依次类推
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
// 2. 指定初始化容量和每次扩容时的增量为0
// 则下次扩容为2 * initialCapacity
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
// 3.指定初始化容量为10，则下次扩容为20， 40...
public Vector() {
this(10);
}
- 向集合Vector添加对象，elementData数组容量不足时：2倍扩容
// minCapacity为期望的elementData数组容量
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// 客户指定的每次数组扩容大小超过0，则扩容为newCapacity = oldCapacity + capacityIncrement
// 否则进行2倍扩容
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
// 确保数组扩容为期望的elementData数组容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
- 客户端重新设置Vector的容量时，可能会进行扩容操作
public synchronized void setSize(int newSize) {
modCount++;
// 新容量大于当前Vector集合中的对象数量则进行扩容
if (newSize > elementCount) {
ensureCapacityHelper(newSize);
} else {
for (int i = newSize ; i < elementCount ; i++) {
elementData[i] = null;
}
}
elementCount = newSize;
}
6.ArrayList
1.ArrayList概要
ArrayList是一个多线程环境下有些操作不安全的集合
2.ArrayList集合中重要的常量和变量
// 默认的初始化数组容量
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 存放集合ArrayList中的对象的数组
transient Object[] elementData;
// 集合ArrayList中包含的对象数量
private int size;
3.ArrayList集合的初始化操作
// 使用指定的初始化容量进行初始化
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
// 构造一个长度为0的ArrayList集合，
// 后面使用add方法添加元素会将elementData扩容成长度为10的数组
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 根据另一个集合构造ArrayList
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
4.ArrayList的扩容操作
- 扩容：按照1.5倍扩容
// minCapacity为期望的数组最低容量（即原数组容量 + 1）
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// 1.5倍进行扩容
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 确保容器达到最低容量10，最低下限
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 确保容器的最大容量，最大上限
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
5.ArrayList内部数组的移动操作
- 移动数组元素的操作都是通过
System.arraycopy这个本地方法完成。
6.ArrayList的删除操作removeIf
- 删除操作removeIf方法中使用BitSet根据相应的位标记需要删除的元素。
// size为容器中的元素个数
final BitSet removeSet = new BitSet(size);
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked")
final E element = (E) elementData[i];
if (filter.test(element)) {
// 需要删除的元素标记为1
removeSet.set(i);
// 统计需要删除的元素个数
removeCount++;
}
}
7.Vector和ArrayList的对比
- 两者的内部结构都是数组。
- Vector集合默认采用当前容量的1倍大小进行扩容，且可以指定一个固定的扩容增量；ArrayList再进行扩容操作时会将当前容量增大50%。
- Vector集合大大部分操作都是线程安全的，但是使用的是synchronized锁，锁的粒度太过粗放，保证线程安全性不推荐使用Vector；ArrayList集合不是线程安全的，在多线程环境下不能使用它。
- Vector集合在序列化的过程中，当前elementData数组中多余的索引位被序列化，产生不必要的性能消耗；在对ArrayList集合进行序列化时，只会对elementData数组中已使用的索引位进行序列化，未使用的索引位不会被序列化；相对地，在原ArrayList集合中已被序列化的各个数据对象被反序列化成新的ArrayList集合中的数据对象时，新的elementData数组不会产生多余的容量，只有在下一次被要求向该集合中添加数据对象时，才会开始新一轮的扩容操作。
7.Stack
1.Stack概要
2.Stack和Vector的对比
- Stack继承自Vector，内部结构都是数组，都存在数组扩容的问题，每次将数组容量增大一倍的方式不灵活。
- 两者都是线程安全的，但是不推荐使用。已经被LinkedBlockingQueue和CopyOnWriteArrayList等替代。
- 两者没有针对序列化过程和反序列化过程进行任何优化，而工作效果相似的ArrayDeque集合、ArrayList集合都对序列化过程的反序列化过程进行了优化。
8.LinkedList
1.LinkedList集合的继承体系
2.LinkedList中重要的变量
- LinkedList底层由双向链表实现
// 集合LinkedList的对象个数
transient int size = 0;
// 指向头节点（双向链表的第一个节点）
transient Node<E> first;
// 指向尾节点（双向链表的最后一个节点）
transient Node<E> first;
// 双链表节点结构
private static class Node<E> {
// 节点存储的元素
E item;
// 指向下一个节点
Node<E> next;
// 指向前一个节点
Node<E> prev;
}
3.LinkedList集合的添加操作
- linkFirst(E e)：在双链表头部插入一个新节点
- linkLast(E e)：在双链表尾部插入一个新节点
- linkBefore(E e, Node
succ)：在指定节点前插入一个新节点
4.LinkedList集合的移除操作
- unlinkFirst(Node
f)：移除双链表的第一个节点 - unlinkLast(Node
l)：移除双链表的最后一个节点 - unlink(Node
x)：移除双链表的指定节点
5.LinkedList的查找操作
- 查询指定索引位置的节点
// 根据索引和集合长度的一半对比，来决定在头部还是尾部开始搜索。
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
6.LinkedList和ArrayList的对比
- 基于数组结构的ArrayList的删除和插入操作效率不高，需要考虑数组扩容元素复制、移动数组元素的问题；基于双向链表的LinkedList的插入和修改操作需要考虑查询索引位的节点的时间消耗，如果在靠近双向链表的中间位置插入新的节点，则找到正确的索引位置节点的时间复杂度为o(n)。
- ArrayList集合支持随机访问，所以查询的效率很高，时间复杂度为O(1)；LinkedList集合的查询操作时间复杂度为o(n);