-
集合框架提供了两个遍历接口：Iterator 和 ListIterator，其中后者是前者的优化版，支持在任意一个位置进行前后双向遍历。注意图中的 Collection 应当继承的是 Iterable 而不是 Iterator，后面会解释 Iterable 和 Iterator 的区别。 -
整个集合框架分为两个门派（类型）：Collection 和 Map，前者是一个容器，存储一系列的对象；后者是键值对 <key, value>，存储一系列的键值对。 -
在集合框架体系下，衍生出四种具体的集合类型：Map、Set、List、Queue。 -
Map 存储 <key,value> 键值对，查找元素时通过 key 查找 value。 -
Set 内部存储一系列不可重复的对象，且是一个无序集合，对象排列顺序不一。 -
List 内部存储一系列可重复的对象，是一个有序集合，对象按插入顺序排列。 -
Queue 是一个队列容器，其特性与 List 相同，但只能从队头和队尾操作元素。 -
JDK 为集合的各种操作提供了两个工具类 Collections 和 Arrays，之后会讲解工具类的常用方法。 -
四种抽象集合类型内部也会衍生出许多具有不同特性的集合类，不同场景下择优使用，没有最佳的集合。
学习Set前，最好最好要先学习 Map，因为 Set 的操作本质上是对 Map 的操作，往下看准没错
Iterator Iterable ListIterator
public interface Iterator<E> {
boolean hasNext();
E next();
void remove();
}提供的 API 接口含义如下：
-
hasNext()：判断集合中是否存在下一个对象 -
next()：返回集合中的下一个对象，并将访问指针移动一位 -
remove()：删除集合中调用 next() 方法返回的对象
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
Iterator iter = list.iterator();
while (iter.hasNext()) {
Integer next = iter.next();
System.out.println(next);
if (next == 2) { iter.remove(); }
}
再来看 Iterable 接口：
public interface Iterable<T> {
Iterator<T> iterator();
// JDK 1.8
default void forEach(Consumer<? super T> action) {
Objects.requireNonNull(action);
for (T t : this) {
action.accept(t);
}
}
}
List<Integer> list = new ArrayList<>();
for (Integer num : list) {
System.out.println(num);
}我们通过命令：javap -c 反编译上面的这段代码后，发现它只是 Java 中的一个语法糖，本质上还是调用 Iterator 去遍历。
Iterator iter = list.iterator();
while (iter.hasNext()) {
Integer num = iter.next();
System.out.println(num);
}
还有更深层次的探讨：为什么要设计两个接口 Iterable 和 Iterator，而不是保留其中一个就可以了。 简单讲解：Iterator 的保留可以让子类去实现自己的迭代器，而 Iterable 接口更加关注于 for-each 的增强语法。具体可参考：Java 中的 Iterable 与 Iterator 详解
-
Iterator 是提供集合操作内部对象的一个迭代器，它可以遍历、移除对象，且只能够单向移动。 -
Iterable 是对 Iterator 的封装，在 JDK 1.8 时，实现了 Iterable 接口的集合可以使用增强 for 循环遍历集合对象，我们通过反编译后发现底层还是使用 Iterator 迭代器进行遍历。
List<Integer> list = new ArrayList<>();
// 返回下标为0的迭代器
ListIterator<Integer> listIter1 = list.listIterator();
// 返回下标为5的迭代器
ListIterator<Integer> listIter2 = list.listIterator(5); ListIterator 中有几个重要方法，大多数方法与 Iterator 中定义的含义相同，但是比 Iterator 强大的地方是可以在任意一个下标位置返回该迭代器，且可以实现双向遍历。
public interface ListIterator<E> extends Iterator<E> {
boolean hasNext();
E next();
boolean hasPrevious();
E previous();
int nextIndex();
int previousIndex();
void remove();
// 替换当前下标的元素,即访问过的最后一个元素
void set(E e);
void add(E e);
}Map 和 Collection 接口
-
SortedMap 接口：该类映射可以对 <key, value> 按照自己的规则进行排序，具体实现有 TreeMap -
AbsractMap：它为子类提供好一些通用的 API 实现，所有的具体 Map 如 HashMap 都会继承它
-
添加方法：add(E e) / addAll(Collection<? extends E> var1) -
删除方法：remove(Object var1) / removeAll(Collection<?> var1) -
查找方法：contains(Object var1) / containsAll(Collection<?> var1); -
查询集合自身信息：size() / isEmpty() -
···
-
Set 接口：一个不允许存储重复元素的无序集合，具体实现有 HashSet / TreeSet··· -
List 接口：一个可存储重复元素的有序集合，具体实现有 ArrayList / LinkedList··· -
Queue 接口：一个可存储重复元素的队列，具体实现有 PriorityQueue / ArrayDeque···
Map 集合体系详解
HashMap
发送哈希冲突时，HashMap 的解决方法是将相同映射地址的元素连成一条链表，如果链表的长度大于 8 时，且数组的长度大于 64 则会转换成红黑树数据结构。
-
它是集合中最常用的 Map 集合类型，底层由数组 + 链表 + 红黑树组成。 -
HashMap 不是线程安全的。 -
插入元素时，通过计算元素的哈希值，通过哈希映射函数转换为数组下标；查找元素时，同样通过哈希映射函数得到数组下标定位元素的位置。
LinkedHashMap
// 头节点
transient LinkedHashMap.Entry<K, V> head;
// 尾结点
transient LinkedHashMap.Entry<K, V> tail;
利用 LinkedHashMap 可以实现 LRU 缓存淘汰策略，因为它提供了一个方法：
protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
return false;
}
该方法可以移除最靠近链表头部的一个节点，而在 get() 方法中可以看到下面这段代码，其作用是挪动结点的位置：
if (this.accessOrder) {
this.afterNodeAccess(e);
}- 指定 accessOrder = true 可以设定链表按照访问顺序排列，通过提供的构造器可以设定 accessOrder
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}-
重写 removeEldestEntry() 方法，内部定义逻辑，通常是判断容量是否达到上限，若是则执行淘汰。
-
它底层维护了一条双向链表，因为继承了 HashMap，所以它也不是线程安全的 -
LinkedHashMap 可实现LRU缓存淘汰策略，其原理是通过设置 accessOrder 为 true 并重写 removeEldestEntry 方法定义淘汰元素时需满足的条件
TreeMap
// 按照 key 自然排序，Integer 的自然排序是升序
TreeMap<Integer, Object> naturalSort = new TreeMap<>();
// 定制排序，按照 key 降序排序
TreeMap<Integer, Object> customSort = new TreeMap<>((o1, o2) -> Integer.compare(o2, o1));
-
自然排序：要求 key 必须实现 Comparable 接口。
TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(2, "TWO");
treeMap.put(1, "ONE");
System.out.print(treeMap);
// {1=ONE, 2=TWO}- 定制排序：在初始化 TreeMap 时传入新的 Comparator，不要求 key实现 Comparable 接口
TreeMap<Integer, String> treeMap = new TreeMap<>((o1, o2) -> Integer.compare(o2, o1));
treeMap.put(1, "ONE");
treeMap.put(2, "TWO");
treeMap.put(4, "FOUR");
treeMap.put(3, "THREE");
System.out.println(treeMap);
// {4=FOUR, 3=THREE, 2=TWO, 1=ONE}
通过传入新的 Comparator 比较器，可以覆盖默认的排序规则，上面的代码按
照key降序排序，在实际应用中还可以按照其它规则自定义排序。
-
它底层是由红黑树这种数据结构实现的，所以操作的时间复杂度恒为O(logN) -
TreeMap 可以对 key 进行自然排序或者自定义排序，自定义排序时需要传入 Comparator，而自然排序要求key实现了 Comparable 接口 -
TreeMap 不是线程安全的。
WeakHashMap
private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
这个 queue 里包含了所有被 GC 掉的键，当 JVM 开启 GC 后，如果回收掉
WeakHashMap 中的 key，会将 key 放入 queue 中，在 expungeStaleEntr
ies() 中遍历 queue，把 queue 中的所有 key 拿出来，并在 WeakHashMap
删除掉，以达到同步。
private void expungeStaleEntries() {
for (Object x; (x = queue.poll()) != null; ) {
synchronized (queue) {
// 去 WeakHashMap 中删除该键值对
}
}
}
再者，需要注意 WeakHashMap 底层存储的元素的数据结构是数组 + 链表，没
有红黑树哦，可以换一个角度想，如果还有红黑树，那干脆直接继承 HashMap，
然后再扩展就完事了嘛，然而它并没有这样做：
public class WeakHashMap<K, V> extends AbstractMap<K, V> implements Map<K, V> {
}
所以，WeakHashMap 的数据结构图我也为你准备好啦。
图中被虚线标识的元素将会在下一次访问 WeakHashMap 时被删除掉，WeakHashMap 内部会做好一系列的调整工作，所以记住队列的作用就是标志那些已经被 GC 回收掉的元素。
-
它的键是一种弱键，放入 WeakHashMap 时，随时会被回收掉，所以不能确保某次访问元素一定存在 -
它依赖普通的 Map 进行实现，是一个非线程安全的集合 -
WeakHashMap 通常作为缓存使用，适合存储那些只需访问一次、或只需保存短暂时间的键值对
Hashtable
这幅图是否有点眼熟哈哈哈哈，本质上就是 WeakHashMap 的底层存储结构了。你千万别问为什么 WeakHashMap 不继承 Hashtable 哦，Hashtable 的性能在并发环境下非常差，在非并发环境下可以用 HashMap 更优。
Set 接口
在 Set 集合体系中，我们需要着重关注两点：
-
存入可变元素时，必须非常小心，因为任意时候元素状态的改变都有可能使得 Set 内部出现两个相等的元素，即 o1.equals(o2) = true，所以一般不要更改存入 Set 中的元素，否则将会破坏了 equals() 的作用！ -
Set 的最大作用就是判重，在项目中最大的作用也是判重！
AbstractSet 抽象类
public abstract class AbstractSet<E> implements Set<E> {
// 判断两个 set 是否相等
public boolean equals(Object o) {
if (o == this) { // 集合本身
return true;
} else if (!(o instanceof Set)) { // 集合不是 set
return false;
} else {
// 比较两个集合的元素是否全部相同
}
}
// 计算所有元素的 hashcode 总和
public int hashCode() {
int h = 0;
Iterator i = this.iterator();
while(i.hasNext()) {
E obj = i.next();
if (obj != null) {
h += obj.hashCode();
}
}
return h;
}
}
SortedSet 接口
public interface SortedSet<E> extends Set<E> {
// 元素的比较器,决定元素的排列顺序
Comparator<? super E> comparator();
// 获取 [var1, var2] 之间的 set
SortedSet<E> subSet(E var1, E var2);
// 获取以 var1 开头的 Set
SortedSet<E> headSet(E var1);
// 获取以 var1 结尾的 Set
SortedSet<E> tailSet(E var1);
// 获取首个元素
E first();
// 获取最后一个元素
E last();
}
HashSet
这也是这篇文章为什么先讲解 Map 再讲解 Set 的原因！先学习 Map，有助于理解 Set
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, Serializable {
public HashSet() {
this.map = new HashMap();
}
public HashSet(int initialCapacity, float loadFactor) {
this.map = new HashMap(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
this.map = new HashMap(initialCapacity);
}
}
private static final Object PRESENT = new Object();
public boolean add(E e) {
return this.map.put(e, PRESENT) == null;
}
public boolean remove(Object o) {
return this.map.remove(o) == PRESENT;
}
上图可以观察到每个 Entry 的 value 都是 PRESENT 空对象，我们就不用再理会它了。
-
底层数据结构：HashSet 也是采用数组 + 链表 + 红黑树实现 -
线程安全性：由于采用 HashMap 实现，而 HashMap 本身线程不安全，在HashSet 中没有添加额外的同步策略，所以 HashSet 也线程不安全 -
存入 HashSet 的对象的状态最好不要发生变化，因为有可能改变状态后，在集合内部出现两个元素 o1.equals(o2)，破坏了 equals() 的语义。
LinkedHashSet
少归少，还是不能闹，LinkedHashSet 继承了 HashSet，我们跟随到父类 HashSet 的构造方法看看
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
this.map = new LinkedHashMap(initialCapacity, loadFactor);
}
LinkedHashSet -> LinkedHashMap -> HashMap + 双向链表
-
它继承了 HashSet，而 HashSet 默认是采用 HashMap 存储数据的，但是 LinkedHashSet 调用父类构造方法初始化 map 时是 LinkedHashMap 而不是 HashMap，这个要额外注意一下 -
由于 LinkedHashMap 不是线程安全的，且在 LinkedHashSet 中没有添加额外的同步策略，所以 LinkedHashSet 集合也不是线程安全的
TreeSet
而元素的排列顺序有2种，和 TreeMap 相同：自然排序和定制排序，常用的构造方法已经在下面展示出来了，TreeSet 默认按照自然排序，如果需要定制排序，需要传入 Comparator。
public TreeSet() {
this(new TreeMap<E,Object>());
}
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}
TreeSet 应用场景有很多，像在游戏里的玩家战斗力排行榜
public class Player implements Comparable<Integer> {
public String name;
public int score;
@Override
public int compareTo(Student o) {
return Integer.compareTo(this.score, o.score);
}
}
public static void main(String[] args) {
Player s1 = new Player("张三", 100);
Player s2 = new Player("李四", 90);
Player s3 = new Player("王五", 80);
TreeSet<Player> set = new TreeSet();
set.add(s2); set.add(s1); set.add(s3);
System.out.println(set);
}
// [Student{name='王五', score=80}, Student{name='李四', score=90}, Student{name='张三', score=100}]
对 TreeSet 介绍了它的主要实现方式和应用场景，有几个值得注意的点。
-
TreeSet 的所有操作都会转换为对 TreeMap 的操作，TreeMap 采用红黑树实现，任意操作的平均时间复杂度为 O(logN) -
TreeSet 是一个线程不安全的集合 -
TreeSet 常应用于对不重复的元素定制排序，例如玩家战力排行榜
注意:TreeSet 判断元素是否重复的方法是判断 compareTo() 方法是否返回0，而不是调用 hashcode() 和 equals() 方法，如果返回 0 则认为集合内已经存在相同的元素，不会再加入到集合当中。
List 接口直接继承 Collection 接口，它定义为可以存储重复元素的集合，并且元素按照插入顺序有序排列，且可以通过索引访问指定位置的元素。常见的实现有：ArrayList、LinkedList、Vector 和 Stack
AbstractList 和 AbstractSequentialList
// 查找元素 o 第一次出现的索引位置
public int indexOf(Object o)
// 查找元素 o 最后一次出现的索引位置
public int lastIndexOf(Object o)
//···
Vector
JDK 1.0 时代，ArrayList 还没诞生，大家都是使用 Vector 集合，但由于 Vector 的每个操作都被 synchronized 关键字修饰，即使在线程安全的情况下，仍然进行无意义的加锁与释放锁，造成额外的性能开销，做了无用功。
public synchronized boolean add(E e);
public synchronized E get(int index);
现在，在线程安全的情况下，不需要选用 Vector 集合，取而代之的是 ArrayList 集合；在并发环境下，出现了 CopyOnWriteArrayList，Vector 完全被弃用了。
Stack
Deque<Integer> stack = new ArrayDeque<Integer>();
ArrayDeque 的数据结构是：数组，并提供头尾指针下标对数组元素进行操作。本文也会讲到哦，客官请继续往看，莫着急！
-
具备随机访问特点，访问元素的效率较高，ArrayList 在频繁插入、删除集合元素的场景下效率较低。 -
底层数据结构：ArrayList 底层使用数组作为存储结构，具备查找快、增删慢的特点 -
线程安全性：ArrayList 是线程不安全的集合 -
ArrayList 首次扩容后的长度为 10，调用 add() 时需要计算容器的最小容量。可以看到如果数组 elementData 为空数组，会将最小容量设置为 10 ，之后会将数组长度完成首次扩容到 10。
// new ArrayList 时的默认空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 默认容量
private static final int DEFAULT_CAPACITY = 10;
// 计算该容器应该满足的最小容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}- 集合从第二次扩容开始，数组长度将扩容为原来的 1.5 倍，即：newLength = oldLength * 1.5
LinkedList
-
优势：LinkedList 底层没有扩容机制，使用双向链表存储元素，所以插入和删除元素效率较高，适用于频繁操作元素的场景 -
劣势：LinkedList 不具备随机访问的特点，查找某个元素只能从 head 或 tail 指针一个一个比较，所以查找中间的元素时效率很低 -
查找优化：LinkedList 查找某个下标 index 的元素时做了优化，若 index > (size / 2)，则从 head 往后查找，否则从 tail 开始往前查找，代码如下所示：
LinkedList.Node<E> node(int index) {
LinkedList.Node x;
int i;
if (index < this.size >> 1) { // 查找的下标处于链表前半部分则从头找
x = this.first;
for(i = 0; i < index; ++i) { x = x.next; }
return x;
} else { // 查找的下标处于数组的后半部分则从尾开始找
x = this.last;
for(i = this.size - 1; i > index; --i) { x = x.prev; }
return x;
}
}-
双端队列：使用双端链表实现，并且实现了 Deque 接口，使得 LinkedList 可以用作双端队列。下图可以看到 Node 是集合中的元素，提供了前驱指针和后继指针，还提供了一系列操作头结点和尾结点的方法，具有双端队列的特性。
Deque<Object> deque = new LinkedList<>();
Deque 接口
AbstractQueue 抽象类
LinkedList
ArrayDeque
在文档中作者写到：ArrayDeque 作为栈时比 Stack 性能好，作为队列时比 LinkedList 性能好
个人观点：链表的插入、删除操作涉及到指针的操作，我个人认为作者是觉得数组下标的移动要比指针的操作要廉价，而且数组采用连续的内存地址空间，而链表元素的内存地址是不连续的，所以数组操作元素的效率在寻址上会比链表要快。请批判看待观点。
PriorityQueue
-
例如游戏中的VIP玩家与普通玩家，VIP 等级越高的玩家越先安排进入服务器玩耍，减少玩家流失。
public static void main(String[] args) {
Student vip1 = new Student("张三", 1);
Student vip3 = new Student("洪七", 2);
Student vip4 = new Student("老八", 4);
Student vip2 = new Student("李四", 1);
Student normal1 = new Student("王五", 0);
Student normal2 = new Student("赵六", 0);
// 根据玩家的 VIP 等级进行降序排序
PriorityQueue<Student> queue = new PriorityQueue<>((o1, o2) -> o2.getScore().compareTo(o1.getScore()));
queue.add(vip1);queue.add(vip4);queue.add(vip3);
queue.add(normal1);queue.add(normal2);queue.add(vip2);
while (!queue.isEmpty()) {
Student s1 = queue.poll();
System.out.println(s1.getName() + "进入游戏; " + "VIP等级: " + s1.getScore());
}
}
public static class Student implements Comparable<Student> {
private String name;
private Integer score;
public Student(String name, Integer score) {
this.name = name;
this.score = score;
}
@Override
public int compareTo(Student o) {
return this.score.compareTo(o.getScore());
}
}
执行上面的代码可以得到下面这种有趣的结果，可以看到氪金使人带来快乐。
-
PriorityQueue 是基于优先级堆实现的优先级队列，而堆是用数组维护的 -
PriorityQueue 适用于元素按优先级处理的业务场景，例如用户在请求人工客服需要排队时，根据用户的VIP等级进行 插队 处理，等级越高，越先安排客服。
-
Collection 接口提供了整个集合框架最通用的增删改查以及集合自身操作的抽象方法，让子类去实现 -
Set 接口决定了它的子类都是无序、无重复元素的集合，其主要实现有HashSet、TreeSet、LinkedHashSet。 -
HashSet 底层采用 HashMap 实现，而 TreeSet 底层使用 TreeMap 实现，大部分 Set 集合的操作都会转换为 Map 的操作，TreeSet 可以将元素按照规则进行排序。
-
-
List 接口决定了它的子类都是有序、可存储重复元素的集合，常见的实现有 ArrayList，LinkedList，Vector -
ArrayList 使用数组实现，而 LinkedList 使用链表实现，所以它们两个的使用场景几乎是相反的，频繁查询的场景使用 ArrayList，而频繁插入删除的场景最好使用 LinkedList -
LinkedList 和 ArrayDeque 都可用于双端队列，而 Josh Bloch and Doug Lea 认为 ArrayDeque 具有比 LinkedList 更好的性能，ArrayDeque 使用数组实现双端队列，LinkedList 使用链表实现双端队列。
-
-
Queue 接口定义了队列的基本操作，子类集合都会拥有队列的特性：先进先出，主要实现有：LinkedList ，ArrayDeque -
PriorityQueue 底层使用二叉堆维护的优先级队列，而二叉堆是由数组实现的，它可以按照元素的优先级进行排序，优先级越高的元素，排在队列前面，优先被弹出处理。
-
-
Map 接口定义了该种集合类型是以 <key,value> 键值对形式保存，其主要实现有：HashMap，TreeMap，LinkedHashMap，Hashtable -
LinkedHashMap 底层多加了一条双向链表，设置 accessOrder 为 true 并重写方法则可以实现LRU缓存 -
TreeMap 底层采用数组+红黑树实现，集合内的元素默认按照自然排序，也可以传入 Comparator 定制排序
-
最后有些话想说：这篇文章花了我半个月去写，也是意义重大，多谢 cxuan 哥一直指导我写文章，一步一步地去打磨出一篇好的文章真的非常不容易，写下的每一个字都能够让别人看得懂是一件非常难的事情，总结出最精华的知识分享给你们也是非常难的一件事情，希望能够一直进步下去！不忘初心，热爱分享，喜爱写作。
转载请注明：XAMPP中文组官网 » 历经5次打磨java集合类详解和使用