Java集合
简介
Java集合大致可分为Set、List、 Queue和Map四种体系，其中Set代表无序、不可重复的集合; List代表有序、重复的集合;而Map则代表具有映射关系的集合，Java 5又增加了Queue体系集合，代表一种队列集合实现。集合类主要负责保存、盛装其他数据，因此集合类也被称为容器类。所有的集合类都位于
java.util包下，后来为了处理多线程环境下的并发安全问题，Java 5还在java utilconcurrent包下提供了一些多线程支持的集合类。
Collection是一个接口，Map没有继承Collection。
Set和Map很相似,Set底层是Map实现的。Map和List的实现比较重要
Set
01 / HashSet
HashSet是Set接口的典型实现，HashSet不能 保证元素的排列顺序，它是非线程安全的,并且集合内元素的值可以是null。HashSet底层 是由HashMap实现的，它将元素存到了HashMap的key上，而对应的value则是一个空对象。
底层数据怎么存的？
有序和无序怎么保证的？
扩容机制？
//transient，该属性不需要序列化，因为只把数据存在了map的k上，即v为空，浪费空间
private transient HashMap<E,Object> map; //底层存数据
//map中的v存固定的PRESENT，而不是null，起到判断比较的作用，null无法比较，常量可以
private static final Object PRESENT = new Object();
//构造器，初始化map
public HashSet() {
map = new HashMap<>();
}
//添加数据的方法
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
//移除
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
//迭代方法
public Iterator<E> iterator() {
return map.keySet().iterator();
}
//重写序列化方法，只序列化key
for (E e : map.keySet())
s.writeObject(e);
02 / TreeSet
TreeSet可以确保集合元素处于排序状态（按照数据的值排序，可以自定义排序规则），TreeSet支持 自然排序和定制排序两种排序方式，它的底层是由TreeMap实现的。TreeSet也是非线程安全的，但是它内部元素的值不能为null（要排序，null没法比较）。
private transient NavigableMap<E,Object> m;
//底层实现
public TreeSet() {
this(new TreeMap<E,Object>());
}
//添加和移除，iterator，序列化和上面的HashSet一样
List
01 / ArrayList
ArrayList是基于数组实现的List，所以ArrayList封装 了一个动态的、允许再分配的Object数组。
ArrayList对象使用initialCapacity参数来设置该数组的长度，当 向ArrayList中添加元素超出了该数组的长度时，它的initialCapacity会 自动增加，即ArrayList会自动扩 容。若需要对ArrayList缩容，则需要主动调用trimToSize()。会主动扩容但不会主动缩容
源码解读：
定义和初始化：
/**
* Default initial capacity.首次初始化数组，默认长度为10
*/
private static final int DEFAULT_CAPACITY = 10;
//两个空的数组，区分创建集合的时候是默认长度还是指定长度，两者方式再扩容机制上不一样
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//数组中存储的具体元素
transient Object[] elementData;
//实际存放的数组长度
private int size;
/**
* Constructs an empty list with an initial capacity of ten.创建一一个默认的容量为10的数组
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//初始化数组
public ArrayList(int initialCapacity) {
//如果指定容量大于0，创建一个指定容量的数组
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {//等于0，创建一个空数组
this.elementData = EMPTY_ELEMENTDATA;
} else {//小于0报错
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
扩容机制（当数组追加到一定范围，即添加数据时）
默认长度为10，每次在上一次的容量基础上，扩展1.5倍。每次扩容其实是将原数组的数据拷贝到创建的新数组里面
public boolean add(E e) {
//先扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
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++;
// overflow-conscious code先判断一下要扩容的容量是否大于数组的长度
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//grow扩容
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;//获取数组旧的容量
//新的容量=老的容量+老的容量的一半（1.5倍）
int newCapacity = oldCapacity + (oldCapacity >> 1);
//超过int容量的最小值
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//超过int容量的最大值
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);
}
//数组容量溢出处理
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
List迭代
//两个迭代器
//因为继承关系具有的迭代器
public Iterator<E> iterator() {
return new Itr();
}
//list自己加的迭代器
public ListIterator<E> listIterator() {
return new ListItr(0);
}
private class Itr implements Iterator<E> {
int cursor; //当前游标
int lastRet = -1; //上一次迭代的位置（当前位置的前面？？不一定）
int expectedModCount = modCount;//期望得修改次数，在迭代的过程中，判断次数相等，不相等说明在迭代的过程中，你修改了（即判断在迭代的过程中，能不能修改数据）
//在迭代的过程中，删除数据时要先判断一下修改次数
}
自己的itertor实现排序，增加ListIterator是为了增加迭代的顺序，实现可以从前往后，从后向前，从中间迭代
//是itertor的子类，在其基础上扩展了一些东西
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) { //指定位置开始迭代
super();
cursor = index;
}
public E previous() {//向前迭代，
checkForComodification();//先检查修改次数，继承的
int i = cursor - 1;
}
//要覆盖某个值也要检查修改次数
ArrayList.this.set(lastRet, e);//把刚刚访问的元素覆盖掉
//添加
public void add(E e) {
checkForComodification();
try {
int i = cursor;
ArrayList.this.add(i, e);//将元素
}
}
缩容：
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
总结：
1、数组实现，默认长度为10，每次扩容1.5倍。每次扩容其实是将原数组的数据拷贝到创建的新数组里面。
2、在迭代的过程中检查修改次数，如果数据被改，就不能迭代下去。
3、支持ListIterator，可以更灵活的进行迭代。
02 / LinkedList
LinkedList是基于双向链表实现的List，它内部的元素可以为nul、可以重复，LinkedList是非线程 安全的。
源码解读：
定义和结构：
transient int size = 0;//连表里有多少个节点
transient Node<E> first;
transient Node<E> last;
//Node节点有前驱和后继，所以是双向链表
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
}
添加数据：
public boolean add(E e) {
linkLast(e); //到链表末尾
return true;
}
//指定位置的添加
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
获取数据：
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
设置值
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
删除：
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
node方法根据节点获取索引
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;
}
}
Queue
Queue用于模拟队列，它是一种先进先出 (FIFO) 的容器。
常用方法offer，poll
Deque
Deque代表双端队列，它允许你从两端来操作队列中的元素，并支持入栈及出栈操作。Deque在Queue的基础上，增加了如下两类方法:
选择一端进行操作
01 / ArrayDeque
ArrayDeque底层通过数组实现，为了满足可以同时在数组两端插入或删除元素的需求，该数组还必须是循环的，即循环数组，也就是说数组的任何一点都可能被看作起点或者终点。ArrayDeque是 非线程安全的，另外该容器不允许放入null元素。
双端队列基于数组实现，
源码解读：
transient Object[] elements;//由数组实现，数据放数组里
transient int head;//头部索引
transient int tail;//尾部索引
//默认最小容量
private static final int MIN_INITIAL_CAPACITY = 8;
//构造器，默认初始化长度为16
public ArrayDeque() {
elements = new Object[16];
}
//指定数组大小时，并不是按照你指定多少就是多少，他要计算一下
private void allocateElements(int numElements) {
elements = new Object[calculateSize(numElements)];
}
//计算容量（你指定的时候他要扩展为比你指定大的最近的，2的n次方）
private static int calculateSize(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;
// Find the best power of two to hold elements.
// Tests "<=" because arrays aren't kept full.
if (numElements >= initialCapacity) {//大于等于最小长度
initialCapacity = numElements;
initialCapacity |= (initialCapacity >>> 1);
initialCapacity |= (initialCapacity >>> 2);
initialCapacity |= (initialCapacity >>> 4);
initialCapacity |= (initialCapacity >>> 8);
initialCapacity |= (initialCapacity >>> 16);
initialCapacity++;
if (initialCapacity < 0) // Too many elements, must back off
initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
}
return initialCapacity;
}
ArrayDeuqe的容量一定是2的n次方
入队：
public boolean offer(E e) {
return offerLast(e);
}
public boolean offerLast(E e) {
addLast(e);
return true;
}
//往头部增加数据
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
//先算头指针下标
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();//扩容
}
扩容：
private void doubleCapacity() {
assert head == tail;
int p = head;
int n = elements.length;//数组的长度
//头指针右侧的元素数量
int r = n - p; // number of elements to the right of p
//新的容量是原来的2倍
int newCapacity = n << 1;
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
//数组拷贝，先拷贝头指针右侧的数据，再拷贝头指针左侧的数据
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r);
System.arraycopy(elements, 0, a, r, p);
elements = a;
head = 0;
tail = n;
}
出队：
public E pollFirst() {
int h = head;
@SuppressWarnings("unchecked")
E result = (E) elements[h];
// Element is null if deque empty
if (result == null)
return null;
//删除头指针
elements[h] = null; // Must null out slot
//头指针移位
head = (h + 1) & (elements.length - 1);
return result;
}
public E pollLast() {
//尾节点
int t = (tail - 1) & (elements.length - 1);
@SuppressWarnings("unchecked")
E result = (E) elements[t];
if (result == null)
return null;
elements[t] = null;
tail = t;//尾指针左移
return result;
}
双端队列当作栈来用
public void push(E e) {
addFirst(e);//上面讲过了
}
public E pop() {
return removeFirst();//一个方向来进和出就是栈
}
02 / LinkedList
除了实现List接口之外，LinkedList还实现 了Deque接口，可以被当成双端队列来使用，因此既可以被当成“栈"来使用，也可以当成队列使用。
源码解读：
public boolean add(E e) {
linkLast(e);
return true;
}
//入队：添加到前面去，
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
//出队
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
//解除节点的双向关系
private E unlinkFirst(Node<E> f) {
。。。
}
栈的方法：
public void push(E e) {
addFirst(e);
}
public E pop() {
return removeFirst();
}