1. 集合 Collection

1.1 Java 集合框架

​ ​ ​ ​ ​ ​ ​ ​ Java 集合框架位于 java.util 包中。Java 集合框架主要包括两种类型的容器，一种是集合（Collection），存储一个元素集合，另一种是图（Map），存储键/值对映射。Collection 接口又有 3 种子类型，List、Set 和 Queue，再下面是一些抽象类，最后是具体实现类，常用的有 ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap 等等。

​ ​ ​ ​ ​ ​ ​ ​ 集合框架是一个用来代表和操纵集合的统一架构。所有的集合框架都包含如下内容：

• 接口：Collection，List，Set，Map 等。用于以不同的方式操作集合对象
• 实现类：是集合接口的具体实现。如 ArrayList、LinkedList、HashSet、HashMap
• 算法：是实现集合接口的对象里的方法执行的一些有用的计算，如搜索和排序。这些算法被称为多态，那是因为相同的方法可以在相似的接口上有着不同的实现
  ​ ​ ​ ​ ​ ​ ​ ​

集合和数组的区别：

• 集合长度可变，数组长度固定
• 集合中只能是引用类型，数组中既可以是基本类型也可以是引用类型
• 集合中可以存储不同类型的元素（通常只存放同种类型），数组只能存储同一种类型
  ​ ​ ​ ​ ​ ​ ​ ​

1.2 集合接口

​ ​ ​ ​ ​ ​ ​ ​

1.3 Collection 集合的方法

​ ​ ​ ​ ​ ​ ​ ​

2. List

​ ​ ​ ​ ​ ​ ​ ​ List 接口是一个有序的 Collection，可以精确的控制每个元素的插入位置，通过索引访问元素，可以存储相同元素。List 接口存储一组不唯一，有序的对象。

​ ​ ​ ​ ​ ​ ​ ​ List 共有三个实现类，ArrayList，Vector，LinkedList。

2.1 ArrayList

​ ​ ​ ​ ​ ​ ​ ​ ArrayList 是最常用的 List 实现类，内部通过数组实现，允许堆元素进行快速随机访问。

​ ​ ​ ​ ​ ​ ​ ​ 由于数组存储需要整块内存空间，中间不能有间隔，当数组大小不足需要扩张时，需要将已有数组的数据全部复制到新存储空间中。当从 ArrayList 中间插入或删除元素时，需要对数组进行复制、移动，代价很高。因此只适合查找遍历，不适用于频繁的插入删除。

特点：

• 底层数据结构为数组
• 查询快，增删慢
• 线程不安全，效率高
• 可以存储重复元素

​ ​ ​ ​ ​ ​ ​ ​

2.1.1 常用方法

​ ​ ​ ​ ​ ​ ​ ​

2.2 LinkedList

​ ​ ​ ​ ​ ​ ​ ​ LinkedList 是一个继承于 AbstractSequentialList 的双向链表，同时也可以被当做栈、队列或双端队列操作。

​ ​ ​ ​ ​ ​ ​ ​ LinkedList 实现了 List 接口，能对它进行队列操作。

​ ​ ​ ​ ​ ​ ​ ​ LinkedList 实现了 Deque 接口，即能将LinkedList当作双端队列使用。
​ ​ ​ ​ ​ ​ ​ ​ LinkedList 实现了 Cloneable 接口，即覆盖了函数clone()，能克隆。
​ ​ ​ ​ ​ ​ ​ ​ LinkedList 实现 java.io.Serializable 接口，这意味着 LinkedList 支持序列化，能通过序列化去传输。

​ ​ ​ ​ ​ ​ ​ ​ LinkedList 包含两个重要成员 header 和 size。 header 是双向链表的表头，是双向链表节点对应的类 Entry 的实例，Entry 中包含成员变量：previous，next，element，element 是该节点中存放的数据。

特点：

• 底层数据结构是双向链表

• 查询慢，增删快

• 线程不安全，效率高

• 可以存储重复元素

​ ​ ​ ​ ​ ​ ​ ​

2.2.1 常用方法

​ ​ ​ ​ ​ ​ ​ ​

2.3 Vector

​ ​ ​ ​ ​ ​ ​ ​ 与 ArrayList 基本相同，通过数组实现，最大的区别是支持线程同步，某一时刻只有一个线程能够修改 Vector。但线程同步需要很高的消费，访问比 ArrayList 慢。

特点：

• 底层数据结构是数组
• 查询快，增删慢
• 线程安全，效率低
• 可以存储重复元素
• 使用 synchronized 方法保证线程安全
  ​ ​ ​ ​ ​ ​ ​ ​

3. Set

​ ​ ​ ​ ​ ​ ​ ​ Set 具有与 Collection 完全一样的接口，Set 中的对象不可重复，除此之外可以把 Set 当做 Collection 使用。该集合用于存储无序元素，对象是否重复根据 hashCode 判断。
​ ​ ​ ​ ​ ​ ​ ​ 如果想让两个不同的对象被视为相等，就必须覆盖 Object 的 hashCode 方法和 equals 方法。

​ ​ ​ ​ ​ ​ ​ ​

3.1 HashSet

​ ​ ​ ​ ​ ​ ​ ​ HashSet 底层数据结构采用哈希表实现。元素的唯一性通过该元素类型是否重写 hashCode() 和 equals() 方法来保证。

​ ​ ​ ​ ​ ​ ​ ​ HashSet 首先判断两个元素的哈希值，如果哈希值相同，会接着通过 equals 方法比较，如果 equals 也为 true，则视为同一个元素。

​ ​ ​ ​ ​ ​ ​ ​ HashSet 通过 hashCode 的值来确定元素在内存中的位置，一个 hashCode 位置上可以存放多个元素（多个元素存放在一个哈希桶中）。

特点：

• 底层数据结构为哈希表
• 元素无序且唯一
• 线程不安全
• 效率高
• 可存储 null 元素

​ ​ ​ ​ ​ ​ ​ ​

3.2 LinkedHashSet

​ ​ ​ ​ ​ ​ ​ ​ LinkedHashSet 继承于 HashSet，底层使用 LinkedHashMap 保存所有元素。方法操作上与 HashSet 相同。

特点：

• 底层使用 LinkedHashMap 保存元素
• 元素顺序与存储顺序一致
• 元素唯一
• 线程不安全，效率高

​ ​ ​ ​ ​ ​ ​ ​

3.3 TreeSet

​ ​ ​ ​ ​ ​ ​ ​ TreeSet 的底层数据结构为红黑树。实现了 SortedSet 接口，可以随时确保集合中的元素处于有序状态。

​ ​ ​ ​ ​ ​ ​ ​ TreeSet 每插入一个对象都会进行排序，将其插入红黑树的指定位置，Integer 和 String 对象都可以进行默认的 TreeSet 排序，但自定义对象不可以。自定义类必须实现 Comparable 接口，并重写 compareTo() 方法才能使用 TreeSet。

​ ​ ​ ​ ​ ​ ​ ​ 重写 compareTo() 方法时，比较不同的值，需要根据小于、等于、大于来返回相应的负整数，零或正整数。

特点：

• 底层数据结构为红黑树
• 元素有序且唯一
• 只能添加同种类型对象
• 不支持快速随机访问
• 不允许元素为 null

​ ​ ​ ​ ​ ​ ​ ​

3.3.1 常用方法

4. Map

​ ​ ​ ​ ​ ​ ​ ​ List 和 Set 都继承自 Collection 接口，Map 不是。Map 用于保存具有映射关系的数据 key 和 value，通过键 key 查找值 value，它们可以是任何引用类型的数据，但 key 不能重复。

​ ​ ​ ​ ​ ​ ​ ​

4.1 Map 的主要方法

​ ​ ​ ​ ​ ​ ​ ​

4.2 HashMap

​ ​ ​ ​ ​ ​ ​ ​ HashMap 的主干是一个 Entry 数组。Entry 是 HashMap 的基本组成单元，每一个 Entry 包含一个 key-value 键值对。为了解决哈希冲突 HashMap 采用了链地址法，也就是数组+链表的方式。
​ ​ ​ ​ ​ ​ ​ ​ 因此大多数情况下 HashMap 可以直接定位到值，访问速度极快，遍历顺序不确定。HashMap 只允许一个键为 null，允许多条值为 null。且 HashMap 非线程安全。
​ ​ ​ ​ ​ ​ ​ ​ JDK 8 对 HashMap 进行了修改，最大的不同是引入了红黑树提升 HashMap 的查找效率。在 JDK 8 中，为解决哈希冲突的链表中的元素超过 8 个以后，会将链表转换为红黑树，在此处查找是可以把时间复杂度降低至 O(logN)。

​ ​ ​ ​ ​ ​ ​ ​

HashMap的构造函数

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

​ initialCapacity 为 HashMap 的初始大小，loadFactor 为负载因子。

​ 如果不填入构造参数，默认初始大小为16，负载因子为0.75。

特点：

• 底层数据结构：数组代表一对映射，链表/红黑树解决哈希冲突
• 访问速度快，效率极高
• 遍历顺序不确定
• 非线程安全

​ ​ ​ ​ ​ ​ ​ ​

4.3 LinkedHashMap

​ ​ ​ ​ ​ ​ ​ ​ LinkedHashMap 是 HashMap 的一个子类，底层数据结构是用双向链表连接起来的 HashMap，可以保留插入顺序，其存取过程基本与 HashMap 相同。
​ ​ ​ ​ ​ ​ ​ ​ LinkedHashMap 通过维护一个额外的双向链表保证了迭代顺序。该迭代顺序可以是插入顺序，也可以是访问顺序。因此，根据链表中元素的顺序可以将其分为：保持插入顺序的 LinkedHashMap 和 保持访问顺序的 LinkedHashMap，其中 LinkedHashMap 的默认按插入顺序排序。
​ ​ ​ ​ ​ ​ ​ ​ 因此 LinkedHashMap 可以很好的支持 LRU 算法。

特点：

• 底层数据结构：双向链表连接 HashMap 中的 Entry 数组
• 可按插入顺序或访问顺序存储
• 可以很好的支持 LRU 算法
• 非线程安全

​ ​ ​ ​ ​ ​ ​ ​

4.4 ConcurrentHashMap

​ ​ ​ ​ ​ ​ ​ ​ ConcurrentHashMap 支持并发操作，是安全高效的 Map 集合，广泛应用于多线程开发。并发控制使⽤ synchronized 和 CAS 来操作，synchronized 只锁定当前链表或红⿊⼆叉树的首节点，这样只要 hash 不冲突，就不会产⽣并发，效率极大的提升。
​ ​ ​ ​ ​ ​ ​ ​ JDK 8 后 ConcurrentHashMap 的数据结构改为 Node 数组+链表/红黑树的结构。
​ ​ ​ ​ ​ ​ ​ ​ 红黑树结构略有不同，HashMap 的红黑树中的节点叫做 TreeNode，TreeNode 不仅仅有属性，还维护着红黑树的结构，比如说查找，新增等等。ConcurrentHashMap 中红黑树被拆分成两块，TreeNode 仅仅维护的属性和查找功能，新增了 TreeBin，来维护红黑树结构，并负责根节点的加锁和解锁。

• Node：Node 对象是链表上的一个节点，内部存储 key、value，以及下一个节点的引用。节点中的 value 和 next 都用 volatile 修饰，保证并发的可见性

• ForwardingNode：当扩容时，要把链表迁移到新的哈希表，在做这个操作时，会在把数组中的头节点替换为 ForwardingNode 对象。ForwardingNode 中不保存 key 和 value，只保存扩容后哈希表（nextTable）的引用。此时查找相应 node 时，需要去 nextTable 中查找

• TreeBin：当链表转为红黑树后，数组中保存的引用为 TreeBin，TreeBin 内部不保存 key 或 value，它保存了 TreeNode 的 list 以及红黑树 root

  ​ ​ ​ ​ ​ ​ ​ ​

ConcurrentHashMap 中添加映射的过程（put 方法）

public V put(K key, V value) {
        return putVal(key, value, false);
    }

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key, value, null);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

具体流程：

• 给输入的 key 分配 hashcode，分配好后依次判断
• 判断是否需要初始化
• 判断 key 对应的 Node 数组是否为空，如果为空则用 CAS 写入数据
• 判断是否需要扩容
• 如果都不满足，则利用 synchronized 锁写入数据
• 如果链表长度大于 TREEIFY_THRESHOLD，则将链表改为红黑树
  ​ ​ ​ ​ ​ ​ ​ ​

特点：

• 底层数据结构：Node数组+链表/红黑树
• 线程安全高效，多线程使用
• 并发控制使用 synchronized 和 CAS，synchronized 只锁定当前链表或红⿊⼆叉树的首节点

​ ​ ​ ​ ​ ​ ​ ​

4.5 HashTable

​ ​ ​ ​ ​ ​ ​ ​ 线程安全的 HashMap，同一时间只有一个线程能够修改 HashTable，并发性远远不如 ConcurrentHashMap，效率低下，不建议在代码中使用。

4.6 TreeMap

​ ​ ​ ​ ​ ​ ​ ​ TreeMap 实现了 SortedMap 接口。能够把保存的记录根据键排序，默认为键值升序，也可以指定排序的比较器。如果使用排序的映射，建议使用 TreeMap。
​ ​ ​ ​ ​ ​ ​ ​ TreeMap 底层为红黑树，将代表一对对映射的 Entry 数组作为节点连接成红黑树，不需要调优，红黑树自动平衡。
​ ​ ​ ​ ​ ​ ​ ​ 在使用 TreeMap 来保存自定义对象时，与 TreeSet 相同必须让自定义对象的类实现 Comparable 接口，并重写 compareTo() 方法。

​

特点：

• 底层数据结构为红黑树
• 存入映射按键值排序，默认升序
• 非线程安全
  ​ ​ ​ ​ ​ ​ ​ ​

4.6.1 常用方法