Java集合可大致分为两大类：Collection（单列集合）以及Map（双列集合）。
先来看一下大体的关系图（并没有完全列举，仅常用）

Collection：

Map：

1 接口介绍

接下来详细介绍一下上图各个接口。

1.1 List

有序，可重复，可插入多个null值，元素都有索引。

1.1.1 Vector

动态数组，同步（线程安全）

1.1.1.1 Stack

继承自Vector，提供了5个额外方法，来实现堆栈操作

push() pop() peek() empty() search()

1.1.2 ArrayList

动态数组，线程不安全，查找效率高（O(1)时间复杂度），增加、删除效率较低。

1.1.3 LinkedList

双向循环链表，查找效率较低，增加、删除效率较高。

1.2 Set

（原则上）无序，不可重复，只允许有一个null值。

1.2.1 HashSet

基于HashMap实现

1.2.1.1 LinkedHashSet

基于LinkedHashMap实现，有序（维护各个元素插入时的顺序）。

1.2.2 SortedSet

在Set的基础上，有序（维护各个元素值的大小的顺序）。

1.2.2.1 TreeSet

在SortedSet的基础上，基于TreeMap实现。

1.2.3 EnumSet

有序，不允许有null值，性能最好

 

1.3 HashTable

线程安全，结构为 数组+链表（同HashMap）。 K、V均不能为null。

1.3.1 Properties

在HashTable的基础上，K、V均为字符串。

1.4 HashMap

线程不安全，无序，K、V均可为null，但K至多有一个可以为null。

• 在Java1.8之前：由 数组+链表 组成。其中，数组为主体用于存放数据，链表负责解决哈希冲突（“拉链法”，效率为O(n)）。
• 在Java1.8之后：当 链表节点>8 && 数组长度>64 时，结构自动转换为红黑树（效率变为O(logn)）。

1.4.1 LinkedHashMap

有序，继承自HashMap。增加了一条双链表，可以保持KV对的顺序。

1.5 SortedMap

只是一个Interface，TreeMap是其实现类。

1.5.1 TreeMap

有序，K不能为null，V可以为null。默认按Key排序，也可以在创建TreeMap时，重写Comparator实现自定义排序。基于红黑树实现。

1.6 WeakHashMap

一种改进的HashMap，对Key弱引用，若Key不再被使用则会被GC。

2 知识点补充

2.1 线程安全的集合类

1.Vector：比ArrayList多了个同步机制。效率较低，不推荐使用。
2.Stack：栈数据结构，先进后出（FILO）。
3.HashTable：比HashMap多了同步机制（线程安全）。
4.Enumeration：枚举，作用相当于迭代器。

2.2 创建只读集合

Collections.unmodifiableCollection(Collection C)

2.3 Iterator 迭代器

提供遍历任何Collection的接口，取代了Java集合框架中的Enumeration，并允许在迭代过程中删除元素（Iterator.remove()）。
其中，ListIterator在Iterator的基础上增加了 增，改 的功能，并且支持双向遍历。

遍历一个List的三种方式
1.for循环
2.Iterator
3.foreach（foreach的内部依然是Iterator。优点：简洁；缺点：只能遍历，不能删除）

2.4 fail-fast 快速失败机制

当Iterator A 在遍历集合时，某个线程 B 修改了集合的结构，此时会触发fail-fast机制。

属于java.util包

原理：Iterator使用一个名为modCount的变量，实时计算集合内容。每当Iterator调用hasNext()/next()时，就把modCount的值与当前集合内容计算的值进行比对。若一致则继续运行，反之则抛出异常。

解决：把涉及modCount的代码加上Synchronized修饰，或者使用CopyOnWriteArrayList替换ArrayList。

Iterator只能单向遍历，但是由于有了fail-fast的存在，使其比较安全。

2.5 fail-safe 安全失败机制

当对集合的结构做出改变时，fail-fast机制会抛出异常，而fail-safe不会。

属于java.util.concurrent包

原理：fail-safe机制实质上会把集合的内容做一份拷贝，在拷贝出的副本集合上进行遍历操作。

缺点：显而易见，需要另外的时空间开销，并且不能保证遍历的内容是实时（最新）的。

2.6 Random Access接口

用来标记List是否支持Random Access（随机访问）。即支持O(1)时间复杂度的查找，比如ArrayList就支持，LinkedList就不支持。

2.7 Array 与 List 转换

Array -> List:

Array.asList(arr)

List -> Array:

list.toArray()

2.8 HashSet如何保证不重复

HashSet基于HashMap实现。即把Value存入HashMap的Key中（Key若相同，则覆盖）。使用add()时，相当于对Key进行比较（先hashcode()再equals()）。

2.9 HashMap哈希冲突

直接放我的笔记吧：

2.10 自动扩容

直接放我的笔记吧：