Java集合系统学习
前言
本文将全面学习和介绍 Java 集合，Java Collection 是开发Java应用最常用的工具包，封装了常用数据结构和基础算法，掌握和理解好 Java 集合是非常有必要的，它可以帮助你编写更加高效和安全的代码。
1. 集合框架
Java 集合框架是对常用数据结构和算法的封装，是一个基础工具库。
1.1 接口总览
Java集合框架，分为 Collection 和 Map 两大接口。其中Collection 表示集合，Map表示映射，Collection 又分为 List、Set、Queue三个接口，Map的Key集合和Value集合分别都是Set类型的。
1.2 版本
本文基于 Java7、Java8 进行研究和学习。
1.3 Joshua Bloch
Joshua Bloch（约书亚▪布洛克），Java平台库架构师，Java集合框架创办人，《Effective Java》一书作者；2004年之前在Sun公司工作，之后在Google公司工作。
1.4 前言
本文不会对数据结构最基础的概念进行详细讲解，如在hashMap 中使用的 hash算法、红黑树性质及实现，栈、队列、链表、数组等基础的数据结构相关性质和原理的讲解，查找，排序等常用算法也不会详细讲解。如果想研究以上知识点，请移步我的另一篇文章《算法与数据结构基础学习篇》，那里会有更详细的讲解。
本文也不会对具有阻塞和并发安全特性的集合进行详细的原理讲解，想研究该知识点，请移步我的另一篇文章《Java并发编程笔记》。本文重点内容是学习在Java基础类库中，如何将这些数据结构和算法进行应用的。
2. 列表 List
列表是一个基本的线性数据结构。
2.1 List 接口
List 接口表示一个列表，主要操作如下：
public interface List<E> extends Collection<E> {
//查询操作
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator<E> iterator();
Object[] toArray();
//修改操作
boolean add(E e);
boolean remove(Object o);
//位置访问操作
E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
int indexOf(Object o);
List<E> subList(int fromIndex, int toIndex);
//批量操作
boolean addAll(Collection<? extends E> c);
boolean addAll(int index, Collection<? extends E> c);
boolean removeAll(Collection<?> c);
void clear();
}List 接口的主要实现有ArrayList 和 LinkedList，它俩都是非线程安全的。
2.2 ArrayList
ArrayList 是一个动态数组，内部使用数组存储元素，数组的大小会随着元素的增多而自动扩容。
//部分核心代码如下:
public class ArrayList<E> implements List<E>{
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
private int size;
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
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);
}
}
}查询元素
get(int index) 方法用来查询指定位置的元素，因为是按数组下标访问数组元素，所以该操作的效率是O(1)，查询效率是极快的！同样，按数组下标修改值的 set(int index, E element) 方法，操作效率也是O(1)；
添加元素
添加元素的 add(E e) 和 add(int index, E element) 源码就不贴出来了（这部分源码很容易理解），当数组容量不够时会进行扩容，扩容为原数组长度的1.5倍，即提升50%的容量。
扩容的具体细节是创建一个新数组，然后把原数组的数据全部复制进去，然后再添加新元素。
add(E e) 方法是在元素列表的最后一个位置添加元素，不牵扯后面的元素移动这种情况； 而 add(int index, E element) 是在指定位置添加元素，目标位置后的所有元素都要后移一位，开销比前一种操作要大一些。
删除元素
remove(int index) 和 remove(Object o) 用于删除一个元素， remove(int index) 会将指定位置后面的全部元素前移一位，效率是O(N)，而 remove(Object o) 还要通过遍历找到目标位置，然后进行删除，效率比前面的操作还要低一些。
迭代器
ArrayList 内部实现的是 fail-fast 迭代器，迭代期间不允许新增或删除，否则抛出 ConcurrentModificationException 异常。
总结
基于数组实现的 ArrayList 查找效率是很高的，但添加和删除元素的效率却一般，所以 ArrayList 适合在查询次数多，而修改次数少的场景下使用。
2.3 LinkedList
LinkedList 不仅实现了 List 接口，也实现了 Deque 接口，所以 LinkedList 既是列表，也是双端队列。这里只讨论 LinkedList 是列表的情况，双端队列的实现在介绍 Deque 接口时会详细分析。
//部分核心代码如下：
public class LinkedList<E> implements List<E>{
Node<E> first;
Node<E> last;
int size = 0;
public LinkedList() {
}
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 作为列表时，相关的操作实现就很简单了。
查询元素
get(int index) 方法用于查询指定位置的元素，此时基于链表实现的LinkedList 就会遍历所有结点，以找到目标数据，查询效率是O(N)，同样， set(int index, E element) 操作也会遍历所有结点。
插入元素
add(E e) 方法直接在链表最后位置插入新元素，效率是O(1)； add(int index, E element) 方法是在指定位置插入元素，不同于数组的插入，链表中插入一个节点的效率是相当高的，找到目标位置然后改变目标位置前后节点的指针指向就可以了，其他元素不受影响，此时的效率是O(N)；
删除元素
remove(int index) 和 remove(Object o) 用于删除一个元素，同 add 操作一样，找到目标位置然后改变目标位置前后节点的指针指向就可以了，其他元素不受影响，此时的效率是O(N)；
总结
基于链表实现的 LinkedList 插入和删除操作的效率要高于数组，并且链表的插入操作不牵扯扩容问题，但查找效率却不如数组，所以 LinkedList 适合在查询次数少，而修改次数多的场景下使用。
2.4 并发安全的List
Vector
Vector 是线程安全的列表，它在每个操作上（get，set，remove）加了 synchronized 关键字来保证线程安全，即同一时刻只允许一个线程操作，即便是查询操作也会获取独占锁，其他方面和 ArrayList 几乎没有差别。
Vector 并发效率一般，在多读少写的场景下，CopyOnWriteArrayList 的并发效率要优于 Vector 和同步的 ArrayList。
集合同步化
使用 Collections 的工具方法 synchronizedCollection() 可以让一个非线程安全的集合变为线程安全的Collection。
ArrayList<Integer> arrayList = new ArrayList<>();
Collection<Integer> syncList = Collections.synchronizedCollection(arrayList);CopyOnWriteArrayList
CopyOnWriteArrayList 采用写时复制的思想，即进行写入操作时，拷贝一份数据出来修改，修改完成后再重新赋值给原来的数组引用。CopyOnWriteArrayList 允许多个线程同时访问，允许一写多读，但不允许同时多写。
在多读少写的场景下，CopyOnWriteArrayList 的并发效率要优于 Vector 和同步的 ArrayList。
3. 队列 Queue
队列是先进先出 FIFO 的线性数据结构。
Java 集合中与队列相关的接口和类如下
队列：
| 接口/类 | 描述 |
|---|---|
| Queue | 队列（接口） |
| Deque | 双端队列（接口） |
| LinkedList | 双端队列 |
| PriorityQueue | 优先队列 |
阻塞队列（并发安全）：
| 接口/类 | 描述 |
|---|---|
| BlockingQueue | 阻塞队列（接口） |
| LinkedBlockingQueue | 阻塞队列（链表实现） |
| ArrayBlockingQueue | 阻塞队列（数组实现） |
| BlockingDeque | 阻塞双端队列（接口） |
| LinkedBlockingDeque | 阻塞双端队列 |
| PriorityBlockingQueue | 阻塞优先队列 |
非阻塞队列（并发安全）：
| 接口/类 | 描述 |
|---|---|
| ConcurrentLinkedQueue | 并发安全的队列 |
| ConcurrentLinkedDeque | 并发安全的双端队列 |
科普 queue 和 deque 的发音：
- queue 【/kju/】
- deque 【/‘di:ke/】
注：
并发安全的集合，几乎都是并发包实现的，本文只讨论数据结构方面的操作，不涉及线程和并发安全方面的研究，因此支持阻塞和非阻塞的并发安全集合，不在本文讨论范围。
3.1 Queue 队列
队列是一个先进先出FIFO 线性数据结构。元素在队尾插入，在队首获取或移除。
public interface Queue<E> extends Collection<E> {
boolean add(E e); //添加元素,如果队列已满,则抛出异常 IllegalStateException
boolean offer(E e); //添加元素,如果队列已满,则返回 false
E remove(); //删除并返回队列头部元素,如果队列为空则抛出异常 NoSuchElementException
E poll(); //删除并返回队列头部元素,如果队列为空则返回null
E element(); //返回队列头部元素但不删除,如果队列为空则抛出异常 NoSuchElementException
E peek(); //返回队列头部元素但不删除,如果队列为空则返回null
}注:
Queue 接口提供了队列的增删查三种基本操作，每种操作提供了2种风格，失败后抛出异常还是返回特殊值（null 或 false）。
实现
Queue 是一个高层接口，直接实现类并不多，但基于该接口实现的拓展接口和类却有很多：
- LinkedList
- BlockingQueue
- LinkedBlockingQueue
- ArrayBlockingQueue
- PriorityQueue
- PriorityBlockingQueue
- ConcurrentLinkedQueue
- Deque
可以看到有很多都是线程安全的队列，包括阻塞队列和非阻塞队列，本文不对并发安全的集合做研究，重点放在普通队列的实现类上，即线程不安全的队列。
3.2 Deque 双端队列
Deque 可以看成是 Double Queue 的合成词，意为双端队列。
双端队列是一个支持在两端分别进行插入和删除的线性数据结构。支持 FIFO 和 LIFO 。
Deque 接口
public interface Deque<E> extends Queue<E> {
//双端队列操作
void addFirst(E e); //在队首添加元素,如果队列已满则抛出异常
void addLast(E e); //在队尾添加元素,如果队列已满则抛出异常
boolean offerFirst(E e); //在队首添加元素,如果队列已满则返回false
boolean offerLast(E e); //在队尾添加元素,如果队列已满则返回false
E removeFirst(); //在队首移除并返回,如果队列为空抛异常
E removeLast(); //在队尾移除并返回,如果队列为空抛异常
E pollFirst(); //在队首移除并返回,如果队列为空返回 null
E pollLast(); //在队尾移除并返回,如果队列为空返回 null
E getFirst(); //获取队首元素,如果队列为空抛异常
E getLast(); //获取队尾元素,如果队列为空抛异常
E peekFirst(); //获取队首元素,如果队列为空返回 null
E peekLast(); //获取队尾元素,如果队列为空返回 null
//Queue 的接口方法
boolean add(E e); //等同于 addLast
boolean offer(E e); //等同于 offerLast
E remove(); //等同于 removeFirst
E poll(); //等同于 pollFirst
E element(); //等同于 getFirst
E peek(); //等同于 peekFirst
//栈操作
void push(E e); // 压栈,等同于 addFirst
E pop(); // 弹栈,等同于 removeFirst
//集合相关操作
boolean remove(Object o);
boolean contains(Object o);
public int size();
Iterator<E> iterator();
}可以看到 Deque 接口定义了双端队列的各种增删查操作，以 First 单词结尾的方法表示在队首进行插入、删除和获取操作，以 Last 单词结尾的方法表示在队尾进行插入、删除和获取操作；
另外，Queue 的接口方法在 Deque 中 也有对应的等价操作，如 add 等同于 addLast，remove 等同于 removeFirst，element 等同于 getFirst。
同样的，每种操作提供抛异常和返回特殊值两种类型的风格。
主要实现
Deque 接口的主要实现有以下几个：
| 接口/类 | 描述 |
|---|---|
| LinkedList | 双端队列（链表实现） |
| ArrayDeque | 双端队列（数组实现） |
| ConcurrentLinkedDeque | 非阻塞双端队列（线程安全） |
| LinkedBlockingDeque | 阻塞双端队列（线程安全） |
LinkedList
LinkedList 是基于链表实现的双端队列。
它的内部节点保存了数据和前后节点的指针,因此 LinkedList 是一个双向链表, 并且支持在链表的两端分别进行插入和删除的操作,如 addFirst(), getFirst() ,removeFirst() 和 addLast(), getLast() ,removeLast() , 这些操作也是实现栈和队列的基本操作。
public class LinkedList<E>{
Node<E> first;
Node<E> last;
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;
}
}
}3.3 PriorityQueue 优先队列
PriorityQueue 是由二叉堆实现的优先队列，内部使用 Object [] 数组来存储元素，构造一棵完全二叉树。
使用
public static void main(String[] args) {
PriorityQueue<Integer> integers = new PriorityQueue<Integer>();
integers.offer(45);
integers.offer(4);
integers.offer(63);
integers.offer(7);
integers.offer(14);
int size = integers.size();
for (int i=0;i<size;i++){
System.out.println(integers.poll());
}
}输出：
4
7
14
45
63实现
数组存储元素
优先队列可以用一个完全二叉树来表示，所以使用数组会方便很多。
private Object[] queue;通过上浮或下沉使堆有序化
//添加元素到队列最后一个位置: 使其上浮让堆有序化(容量不够就扩容);
public boolean offer(E e) {
if (e == null) throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length) grow(i + 1);
size = i + 1;
if (i == 0) queue[0] = e;
else
siftUp(i, e);
return true;
}
//移除队列头部元素并返回: 队列最后一个元素取出,并把该位置置空,放到队列头部,使其下沉让堆有序化
public E poll() {
if (size == 0) return null;
int s = --size;
modCount++;
E result = (E) queue[0];
E x = (E) queue[s];
queue[s] = null;
if (s != 0)
siftDown(0, x);
return result;
}比较器
无论是增加还是删除元素，都离不开比较。若在初始化优先队列的时候，没有指定比较器 comparator ，那么元素将使用自身的比较规则，即实现 Comparable 接口的 compareTo（）方法来比较元素。如果指定比较器，则使用比较器的规则进行排序。
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}扩容策略
如果容量很小（oldCapacity < 64），就以二倍速度扩容；容量超过64，则每次扩容50%；
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
int newCapacity =
oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1));
// overflow-conscious code
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}应用
在JDK并发包中，延迟队列 DelayQueue 内部使用优先队列 PriorityQueue 存储元素，而定时任务的线程池 ScheduledThreadPoolExecutor 是使用延迟队列来构造的。
public class DelayQueue implements BlockingQueue<E> {
private final transient ReentrantLock lock = new ReentrantLock();
private final Condition available = lock.newCondition();
private final PriorityQueue<E> q = new PriorityQueue<E>();
}ScheduledThreadPoolExecutor 并没有使用 DelayQueue ，而是自己实现了一个内部类 DelayedWorkQueue，并不是 DelayQueue 满足不了需求，而是在基础的并发包中，不想引入过多的依赖，直接使用Lock + 数组实现的二叉堆，性能也会好一些。（除此之外，DelayQueue 和 DelayedWorkQueue并没有什么不同）
static class DelayedWorkQueue implements BlockingQueue<Runnable> {
private final ReentrantLock lock = new ReentrantLock();
private final Condition available = lock.newCondition();
private RunnableScheduledFuture[] queue = new RunnableScheduledFuture[16];
}4. 栈 Stock
栈是一种后进先出 LIFO 的数据结构（最后压入栈的元素，最先弹出）。
LinkedList 能够直接实现栈的所有功能和方法。
public interface Stack<E> {
E push(E item);
E pop() throws EmptyStackException;
E peek() throws EmptyStackException;
boolean contains(Object o);
boolean empty();
int size();
void clear();
}4.1 LinkedList 实现 Stack
使用LinkedList 实现Stack：
public class Stack<E>{
private LinkedList<E> linkedList = new LinkedList<E>();
public void push(E item) { linkedList.addFirst(item); }
public E pop() {return linkedList.removeFirst(); }
public E peek() {return linkedList.getFirst(); }
public boolean contains(Object o) {return linkedList.contains(o); }
public boolean isEmpty() {return linkedList.isEmpty(); }
public int size() {return linkedList.size(); }
public void clear() {linkedList.clear(); }
}注：
在 java.util 包中提供了 Stack 类的实现，但是Stack 类的实现手法实在是不优雅，它是通过实现List 接口来实现的，这就使得Stack 也拥有了父类的方法，非常不纯净，因此该类不推荐使用。
5. Map
Map 接口提供了元素与元素的映射关系，即Key-value 映射，可以通过键来查找值。
public interface Map<K,V> {
//查询操作
int size();
boolean isEmpty();
boolean containsKey(Object key);
boolean containsValue(Object value);
V get(Object key);
//修改操作
V put(K key, V value);
V remove(Object key);
//批量操作
void putAll(Map<? extends K, ? extends V> m);
void clear();
//集合视图
Set<K> keySet();
Collection<V> values();
Set<Map.Entry<K, V>> entrySet();
}PS：将对象映射到其他对象的能力是解决编程问题的杀手锏。
Map 接口有3个主要实现：
| Map | 描述 |
|---|---|
| HashMap | Key的排列是无序的，基于哈希表实现 |
| TreeMap | Key按照比较大小进行排序，基于红黑树实现 |
| LinkedHashMap | Key按照插入顺序进行排序， |
5.1 HashMap
HashMap 是基于哈希表实现的Map，哈希表的特点是查询效率极高，时间复杂度为O(1)。
JDK1.8 版本的HashMap和 JDK1.7 的区别很大， JDK1.7 之前HashMap使用 数组+链表实现；而到了1.8 加入了红黑树的实现，这也使得HashMap 1.8 的源码量比1.7的多了一倍还要多。
HashMap之1.7和1.8的区别
- 数据结构不一样，1.7是数组+链表，1.8是数组+链表+红黑树；
- 当哈希冲突在链表上新增节点时，1.7在头部插入，1.8在尾部插入；（这也是1.8不容易出现环形链表的原因）
- 1.8的哈希函数比1.7更简单；
- 扩容时，1.7在插入数据之前扩容，而1.8在插入数据之后扩容；
插入 put
查找 get
迭代器(Iterator)。HashMap的迭代器(Iterator)是fail-fast迭代器
哈希函数
在哈希表中，拿到Key值，经过一系列运算，计算出元素存放的数组下标（int类型的整数值），需要三个步骤：
- Key本身的hashCode() 方法运算得到哈希码；
- HashMap提供的 hash() 函数进一步扰动计算得到哈希值；
- 根据哈希值计算得到对应的数组下标；
扰动计算
JDK1.7和1.8哈希函数的扰动计算方式不同：
//1.7
int hash = hash(key.hashCode());
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
//1.8
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}1.7的哈希函数需要4次位移和4次异或计算，而1.8只需要1次位移和1次异或，从计算次数分析，1.8的哈希函数效率比1.7要快，因为运算次数少了很多，但哈希函数设计的不仅看哈希值的运算效率，还要看哈希值的散列质量如何，即散列值分布的是否均匀。
hash 函数是对 key 的 hashCode 进行扰动计算，防止不同的 hashCode 因为高位不同而低位相同导致的hash冲突，换句话说，就是把hashCode 的高位特征和低位特征结合起来，尽量做到任何一位变化都能对最终结果产生影响，从而降低哈希冲突的概率。
为什么是2的整数次幂
位运算比基本的算数运算（乘法、除法、取余）效率高很多，又因满足 hash % length = hash & (length-1) 公式成立的前提是
length = 2^n^ ，因此规定 length = 2^n^ ，从而使用位运算取余，加快获取数组索引下标的速度。
得到哈希值后，再进行一步位与运算就得到了数组下标：
//相当于一次取余操作: hash % length (前提是length = 2^n);
int index = hash & (length-1);5.2 TreeMap
TreeMap 是基于红黑树实现的Map，get 、put、remove和 containsKey 操作提供了 log（N）的时间效率。
TreeMap 实现了 SortedMap 接口，保证Key的有序性。TreeMap中的Key必须实现 Comparable 接口。
TreeMap 和 HashMap
TreeMap 可以保证key的有序性，正因为这样，TreeMap 的操作效率要略低于HashMap，所以在没有排序要求的情况下，应该优先使用HashMap，只有在对key 的顺序有要求的情况下才考虑使用TreeMap 。
5.3 LinkedHashMap
LinkedHashMap 继承自 HashMap ，绝大多数操作直接复用 HashMap，与HashMap的主要区别在于Node节点的设计，HashMap的Node节点存储了hash值、key值、value值和同在一个哈希槽的下一个拉链节点，LinkedHashMap 的节点继承HashMap的Node节点，并加入了before、after引用，使其成为双向链表，节点的构造顺序就是元素的插入先后顺序，同时Entry节点也是拉链的单向链表。
//HashMap
public class HashMap<K,V> implements Map<K,V>{
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
}
//LinkedHashMap
public class LinkedHashMap<K,V> extends HashMap<K,V>{
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
//覆盖父类方法
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);//插入到双向链表的尾节点
return p;
}
}5.4 EnumMap
HashMap是一种通过对key计算hashCode()，通过空间换时间的方式，直接定位到value所在的内部数组的索引，因此，查找效率非常高。
如果作为key的对象是enum类型，那么，还可以使用Java集合库提供的一种EnumMap，它在内部以一个非常紧凑的数组存储value，并且根据enum类型的key直接定位到内部数组的索引，并不需要计算hashCode()，不但效率最高，而且没有额外的空间浪费。
5.5 并发安全的Map
Hashtable
Hashtable 是最早实现的并发安全的Map，在每个操作上（put(), remove(), get ）加上 synchronized 来保证线程安全，即同一时刻只允许一个线程操作Map，即便是查询操作也会获取独占锁，Hashtable 的并发效率很一般，现在很少使用了。
ConcurrentHashMap
ConcurrentMap 接口是JDK1.5在并发包中加入的接口，表示并发安全的Map，ConcurrentHashMap 是主要实现，ConcurrentHashMap 的并发效率很高，在保证线程安全的前提下，允许多个线程同时操作Map，若想使用并发安全的Map，ConcurrentHashMap 是首选。
6. Set
Set 表示一个集合，和数学中的集合一样，集合中的元素之间没有关联，它们只是在同一个集合中。
public interface Set<E> extends Collection<E> {
//查询操作
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator<E> iterator();
Object[] toArray();
//修改操作
boolean add(E e);
boolean remove(Object o);
//批量操作
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean retainAll(Collection<?> c);
boolean removeAll(Collection<?> c);
void clear();
}Set 接口主要有3个实现：
| Set | 描述 |
|---|---|
| HashSet | 元素的排列是无序的 |
| TreeSet | 元素按照比较大小来排序 |
| LinkedHashSet | 元素按照插入顺序来排序 |
HashSet 中的元素是无序的，内部使用 HashMap实现；TreeSet 实现了 SortedSet 接口，是一个有序集合，元素通过比较大小进行排序；LinkedHashSet 继承自 HashSet ，元素按照插入顺序进行排序。
HashSet 底层使用 HashMap实现，TreeSet 底层使用 TreeMap实现，LinkedHashSet 继承自 HashSet 。因为 Map的 Key 是不可重复的，和Set 的元素要求一致，所以自然而然的使用Map作为Set接口各实现类的底层数据结构支持。
6.1 HashSet
HashSet 底层使用 HashMap实现，HashSet 的操作是由 HashMap 提供的。
public class HashSet<E> implements Set<E>{
/** HashMap提供底层操作 */
private transient HashMap<E,Object> map;
/** Map的value 统一存储同一个对象*/
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
public int size() { return map.size();}
public boolean isEmpty() { return map.isEmpty();}
public boolean contains(Object o) { return map.containsKey(o);}
public void clear() {map.clear();}
public Iterator<E> iterator() { return map.keySet().iterator();}
}6.2 TreeSet
TreeSet 实现了 SortedSet 接口，是一个有序集合。TreeSet 的各种底层操作都是由 TreeMap 提供的。
6.3 LinkedHashSet
LinkedHashSet 继承自 HashSet ，元素按照插入顺序进行排序。
7. 迭代器 Iterator
从面向对象角度来说，Java的集合属于聚合对象，迭代器提供一种思想，将顺序访问集合的遍历操作与内部的数据结构分离开来。这是一种面向对象的设计模式。
7.1 迭代器模式
提供一种方法顺序访问一个聚合对象的的每个元素，而又不暴露其内部的表示。
7.2 Iterable 和 Iterator 接口
Iterable 接口用于提供一个迭代器，代表该集合是可迭代的，Collection 接口实现了 Iterable 接口。
public interface Iterable<T> {
Iterator<T> iterator();
}Iterator 接口定义了迭代器的三个基本操作：
public interface Iterator<E> {
boolean hasNext();
E next();
void remove();
}注：其中 remove() 方法不是必须的。
7.3 fail-fast 迭代器
fail-fast 迭代器意为快速失败迭代器，该迭代器不允许在迭代的时候对集合进行新增或删除操作。
下面是 ArrayList 的内部迭代器实现，是一个 fail-fast 迭代器：
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
Itr() {}
public boolean hasNext() {
return cursor != size;
}
public E next() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
int i = cursor;
if (i >= size) throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
public void remove() {
//...
}
} 通过 iterator() 方法获取一个迭代器时，会创建一个新的迭代器对象，expectedModCount 变量的初始值就是那一刻 modCount 的值，集合的新增或删除都会修改 modCount 的值，迭代器每次迭代都会检查 expectedModCount 和 modCount 是否相等，如果不相等，说明集合的元素数量发生了变化，此时迭代器便会立即抛出 ConcurrentModificationException 异常，这便是fail-fast 迭代器；
如果想在迭代时进行删除操作，可以使用迭代器提供的 remove() 方法（如果支持的话）。
ArrayList 、LinkedList、HashMap 、TreeMap 的迭代器都是 fail-fast 迭代器。
8. 工具类
Arrays 和 Collections 工具类提供了很多常用的算法。
8.1 Arrays
Arrays 工具类提供了很多操作数组的算法封装。如二分查找、排序、并行排序、拷贝、范围拷贝、计算哈希值。
Arrays.binarySearch();
Arrays.sort();
Arrays.parallelSort();
Arrays.copyof();
Arrays.copyOfRange();
Arrays.hashCode();binarySearch 二分查找
二分查找是常用的效率很高的查找算法，二分查找的前提是数组内的元素已经排过序。
sort 排序
在JDK1.8中，Arrays.sort 的实现使用的并不是单一的排序算法，而是插入排序，快速排序，归并排序三种的组合，方法根据输入的元素数量以及结构形态动态的选择合适的排序算法。
parallelSort 并行排序
JDK1.8新增的并行排序算法，基于fork/join框架.区别于Arrays.sort() 串行排序：
Arrays.parallelSort();copyof 拷贝
注意，Arrays.copyof() 实现的是浅拷贝，不是深拷贝，即基于原数组会产生一个新数组，但如果数组内的元素是对象（引用数据类型），则元素不会复制，依然使用原来的元素，如果改变原数组中的元素的值（改变某个元素对象的属性值，而不是替换该对象），新数组中对应的元素的值也会变化！如果数组元素是值传递的基本数据类型或直接替换掉元素，改变原数组中的元素的值，新数组中对应的元素的值确实不会变化，因为对于这类数据，是直接把元素的值或新对象添加到数组中，这种情况确实算是深拷贝了。
copyOfRange 范围拷贝
只复制数组一段数据，同样也是浅拷贝。
hashCode 计算哈希值
Arrays.hashCode() 用于计算整个数组的哈希值，这个值与数组中的每个元素的内容都有关系，所以改变其中一个元素的内容，这个哈希值就有可能发生变化。
8.2 Collections
查找最值元素
前者使用元素自身的比较规则，后者使用入参的比较器 Comparator 进行比较；
T min(Collection<? extends T> coll){};
T min(Collection<? extends T> coll, Comparator<? super T> comp){};
T max(Collection<? extends T> coll){};
T max(Collection<? extends T> coll, Comparator<? super T> comp){};元素交换
//集合中交换两个位置的元素
public static void swap(List<?> list, int i, int j){};集合同步化(并发安全)
Collections 提供了两个方法将非线程安全的集合同步化，使其线程安全。
public static <T> Collection<T> synchronizedCollection(Collection<T> c) {
return new SynchronizedCollection<>(c);
}
static <T> Collection<T> synchronizedCollection(Collection<T> c, Object mutex) {
return new SynchronizedCollection<>(c, mutex);
}SynchronizedCollection 是 Collections 的静态内部类，同步化的操作被封装在其内部。
SynchronizedCollection 部分核心源码如下：
static class SynchronizedCollection<E> implements Collection<E>{
final Collection<E> c; // Backing Collection
final Object mutex; // Object on which to synchronize
SynchronizedCollection(Collection<E> c) {
this.c = Objects.requireNonNull(c);
mutex = this;
}
SynchronizedCollection(Collection<E> c, Object mutex) {
this.c = Objects.requireNonNull(c);
this.mutex = Objects.requireNonNull(mutex);
}
public boolean add(E e) {
synchronized (mutex) {return c.add(e);}
}
public boolean remove(Object o) {
synchronized (mutex) {return c.remove(o);}
}
public int size() {
synchronized (mutex) {return c.size();}
}
public boolean isEmpty() {
synchronized (mutex) {return c.isEmpty();}
}
public Iterator<E> iterator() {
return c.iterator(); // Must be manually synched by user!
}
}可以看到，SynchronizedCollection 同步化集合的逻辑非常简单，使用一把锁，把每个操作用同步代码块包起来，就达到了并发安全的目的，简单粗暴，效率一般。
注：
- 对同步化的集合进行迭代时，务必在同步块中进行；
- 在并发环境下，同步化的集合并不是首选，并发包中提供了很多效率高的并发集合可以使用；
8.3 三方类库
此外除了JDK内置的集合工具类，还有很多优秀的第三方类库可以选择，如Google的核心类库Guava、Apache的 commons-lang 等。
9. 并发安全的集合
9.1 并发容器一览表
| 接口/类 | 描述 |
|---|---|
| BlockingQueue | 阻塞队列接口 |
| LinkedBlockingQueue | 阻塞队列【链表实现】 |
| ArrayBlockingQueue | 阻塞队列【数组实现】 |
| SynchronousQueue | 同步队列（不存储元素） |
| PriorityBlockingQueue | 优先阻塞队列 |
| DelayQueue | 延迟队列（非常实用） |
| BlockingDeque | 阻塞双端队列接口 |
| LinkedBlockingDeque | 阻塞双端队列 |
| LinkedTransferQueue | 传输队列（同步传输） |
| ConcurrentLinkedQueue | 并发安全的队列（非阻塞） |
| ConcurrentLinkedDeque | 并发安全的双端队列（非阻塞） |
| ConcurrentHashMap | 并发安全的HashMap |
| ConcurrentSkipListMap | 并发安全的Map（跳表实现） |
| ConcurrentSkipListSet | 并发安全的Set（跳表实现） |
| CopyOnWriteArrayList | 并发安全的动态数组（写时复制） |
| CopyOnWriteArraySet | 并发安全的数组集合（写时复制） |
README
作者：银法王
版权声明：本文遵循知识共享许可协议3.0（CC 协议）： 署名-非商业性使用-相同方式共享 (by-nc-sa)
参考：
JDK1.8 源码
《Java编程思想》第4版
修改记录：
2020-03-22 第一次修订
2020-08-11 排版