Java Collection集合介绍、fail-fast快速失败机制介绍、线程安全的容器介绍

文章目录

• 前言
• 1、集合
• • 1.1、集合是什么，为什么使用集合
  • 1.2、集合的继承关系
• 2、Collection接口与Iterator接口中的方法
• • 2.1、Collection接口的常用方法
  • 2.2、Iterator接口常用的方法
• 3、List集合
• • 3.1、List接口中的常用方法
  • 3.2、ArrayList类
  • • 3.2.1、ArrayList类介绍
    • 3.2.2、ArrayList的构造方法
    • 3.2.3、ArrayList的常用方法
  • 3.3、LinkedList类
  • • 3.3.1、LinkedList类介绍
    • 3.3.2、LinkedList的构造方法
    • 3.3.3、LinkedList的常用方法
  • 3.4、ArrayList和LinkedList的比较
• 4、Map集合
• • 4.1、Map接口
  • • 4.4.1、Map接口中的常用方法
  • 4.2、HashMap类
  • • 4.2.1、HashMap介绍
    • 4.2.2、HashMap的常用方法
    • 4.2.3、HashMap的特点
    • 4.2.4、HashMap的构造方法
  • 4.3、LinkedHashMap类
  • • 4.3.1、LinkedHashMap介绍
    • 4.3.2、LinkedHashMap的常用方法
    • 4.3.3、LinkedHashMap的特点
    • 4.2.4、LinkedHashMap的构造方法
  • 4.4、TreeMap类
  • • 4.4.1、TreeMap介绍
    • 4.3.2、TreeMap的常用方法
    • 4.3.3、TreeMap的特点
    • 4.2.4、LinkedHashMap的构造方法
  • 4.5、HashMap、LinkedHashMap、TreeMap比较
• 5、Set集合
• • 5.1、Set接口
  • • 5.1.1、Set接口中的常用方法
  • 5.2、HashSet类
  • • 5.2.1、HashSet介绍
    • 5.2.2、HashSet的常用方法
    • 5.2.3、HashSet的特点
    • 5.2.4、HashSet的构造方法
    • 5.2.5、HashSet与HashMap的区别
  • 5.3、LinkedHashSet类
  • • 5.3.1、LinkedHashSet的常用方法
    • 5.3.2、LinkedHashSet的特点
    • 5.3.3、LinkedHashSet的构造方法
    • 5.3.3、LinkedHashSet与LinkedHashMap比较
  • 5.4、TreeSet类
  • • 5.4.1、TreeSet介绍
    • 5.4.2、TreeSet的常用方法
    • 5.4.3、TreeSet的特点
    • 5.4.4、TreeSet的构造方法
  • 4.5、HashSet、LinkedHashSet、TreeSet比较
• 6、fail-fast快速失败机制
• 7、线程安全的容器
• • 7.1、CopyOnWriteArrayList的实现原理
  • 7.2、ConcurrentHashMap 的实现原理
  • 7.3、CopyOnWriteArraySet 的实现原理

---

前言

本人是刚入门java的学生。
由于水平有限，缺点和疏漏在所难免，恳请大家不吝指正，万分感激。

1、集合 1.1、集合是什么，为什么使用集合

我们在编程的时候需要对数据进行存储，数组可以存储数据。但是在创建数组时需要指定长度，我们存储的数据不可能是固定不变的，所以 Java 为我们提供了集合。

1.2、集合的继承关系

从图中可以看出，Collection 接口是集合层次结构中的根接口。

Collection 接口又有三个子接口，List Set Queue
而 Map 是 Java.util 包中的另一个接口

先介绍 Collection 接口和 Iterator 接口
List 下的 ArrayList 和 LinkedList
Set 下的 HashSet 、 LinkedHashSet 和 TreeSet
Map 下的 HashMap 、 LinkedHashMap 和 TreeMap

---

2、Collection接口与Iterator接口中的方法 2.1、Collection接口的常用方法

Collection 接口中的方法

方法（修改操作）	说明
（常用）boolean add(E e)	向集合中加入指定对象 e，增加成功返回true，失败返回false
（常用）boolean remove(Object o)	从集合中删除指定元素 o，删除成功返回true，失败返回false

方法（查询操作）	说明
int size()	返回此集合中的元素数
boolean isEmpty()	判定是否为空集合，是返回true，不是返回false
boolean contains(Object o)	判定集合内是否包含指定元素 o，是返回true，不是返回false
Iterator< E > iterator()	返回此集合中元素的迭代器
Object[] toArray()	返回一个包含此集合中所有元素的数组
toArray(T[] a)	返回一个包含此集合中所有元素的数组

方法（批量操作）	说明
boolean containsAll(Collection c)	如果此集合包含 c 集合中的所有元素，是返回 true。
（常用）void clear()	从此集合中删除所有元素
（常用）boolean addAll(Collection c)	将 c 集合中的所有元素添加到此集合，增加成功返回true，失败返回false
default Spliterator< E > spliterator()
（常用）boolean removeAll(Collection c)	移除该集合中包含集合 c 的所有元素，如果删除了1个及以上，返回true
（常用）default Stream< E > stream()	返回以此集合为源的顺序流
（常用）default boolean removeIf(Predicate filter)	删除此集合中满足条件的所有元素，如果删除了1个及以上，返回true
default Spliterator< E > spliterator()
boolean retainAll(Collection c)	仅保留此集合中包含在 c 集合中的元素，如果此集合因调用而更改，返回true

2.2、Iterator接口常用的方法

方法	说明
boolean hasNext()	还有元素可以迭代返回true
E next()	返回迭代中的下一个元素
default void remove()	移除此迭代器返回的最后一个元素

---

3、List集合 3.1、List接口中的常用方法

方法（查询操作）	说明
（常用）E get(int index)	返回此列表中指定位置的元素
（常用）int indexOf(Object o)	返回此列表中指定元素第一次出现的索引，如果此列表不包含该元素，则返回 -1
int lastIndexOf(Object o)	返回此列表中指定元素最后一次出现的索引，如果此列表不包含该元素，则返回 -1
（常用）ListIterator< E > listIterator()	返回此列表中元素的列表迭代器（以正确的顺序）
ListIterator< E > listIterator(int index)	返回此列表元素的列表迭代器(按适当顺序)，从列表的指定位置开始

方法（修改操作）	说明
void add(int index, E element)	在此列表中的指定位置插入指定元素
（常用）E remove(int index)	返回从列表中删除的元素
（常用）E set(int index, E element)	将此列表中指定位置的元素替换为指定元素，返回先前在指定位置的元素

方法（批量操作）	说明
default void sort(Comparator c)	根据指定的顺序对该列表进行排序
List< E > subList(int fromIndex, int toIndex)	返回此列表在指定之间的部分的视图
default void replaceAll(UnaryOperator< E > operator)	将此列表的每个元素替换为将运算符应用于该元素的结果
boolean addAll(int index, Collection c)	将指定集合中的所有元素插入到此列表中的指定位置，如果此列表因调用而更改，返回true

3.2、ArrayList类 3.2.1、ArrayList类介绍

ArrayList 中的变量

public class ArrayList extends AbstractList
        implements List, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;

    
    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;
}

size 和 capacity 的区别：
size 是大小，表示数组中存储元素的个数
capacity 是容量，表示数组的长度，但该属性没有在 ArrayList 中

ArrayList 数组列表，是使用数组来存储数据的， ArrayList 的特点有：

特点	说明
有序	元素存入的顺序和取出的顺序一致
可重复	存入的元素可以相同
可为null	可以存储 null 元素

优点	缺点
查询快	增删慢

在数组中只需要知道元素的索引即可立即拿到元素，所以查询快。
当数组中存储的元素满了时，数组会进行扩容，创建一个 1.5 倍原长度的新数组，再把之前元素拷贝至新数组中，删除同理。

3.2.2、ArrayList的构造方法

// 无参构造方法
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);
    }
}

// 包含 Collection 的构造方法
public ArrayList(Collection c) {
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        // replace with empty array.
        elementData = EMPTY_ELEMENTDATA;
    }
}

方法	说明
new ArrayList<>()	构造一个初始容量为10的空数组
new ArrayList(int initialCapacity)	构造一个指定初始容量的空数组
new ArrayList(Collection c)	构造一个包含Collection的元素的数组

3.2.3、ArrayList的常用方法

ArrayList 实现了 List 接口，ArrayList 可以使用 List 接口中的方法
而 List 又实现了 Collection 接口，所以也可以使用 Collection 接口中的方法。

方法（查询操作）	说明
E get(int index)	返回此列表中指定位置的元素
int indexOf(Object o)	返回此列表中指定元素第一次出现的索引，如果此列表不包含该元素，则返回 -1
int size()	返回此集合中的元素数
Iterator< E > iterator()	返回此集合中元素的迭代器
boolean isEmpty()	判定是否为空集合，是返回true，不是返回false

方法（修改操作）	说明
boolean add(E e)	向集合中加入指定对象 e，增加成功返回true，失败返回false
boolean remove(Object o)	从集合中删除指定元素 o，删除成功返回true，失败返回false
E set(int index, E element)	将此列表中指定位置的元素替换为指定元素，返回先前在指定位置的元素

方法（批量操作）	说明
void clear()	从此集合中删除所有元素
default Stream< E > stream()	返回以此集合为源的顺序流

---

3.3、LinkedList类 3.3.1、LinkedList类介绍

private static class Node {
	// 存储数据
    E item;
    // 指向后一个节点
    Node next;
    // 指向前一个节点
    Node prev;

    Node(Node prev, E element, Node next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

transient int size = 0;


transient Node first;


transient Node last;

LinkedList 链表列表，是使用双向链表来存储数据的，LinkedList 的特点有：

特点	说明
有序	元素存入的顺序和取出的顺序一致
可重复	存入的元素可以相同
可为null	可以存储 null 元素

优点	缺点
增删快	查询慢

在双向链表中，添加或者元素不需要向数组去调整数组的长度，只需要调整前后节点的指向，所以 LinkedList 的增删快。
而查询即使知道索引，也需要从头部或者从尾部挨个查找，所以查询慢。

3.3.2、LinkedList的构造方法

// 无参构造方法
public LinkedList() {
}

// 包含 Collection 的构造方法
public LinkedList(Collection c) {
    this();
    addAll(c);
}

方法	说明
new LinkedList<>()	构造一个初始容量为10的空数组
new ArrayList(Collection c)	构造一个包含Collection的元素的数组

3.3.3、LinkedList的常用方法

LinkedList 实现了 List 接口，LinkedList 可以使用 List 接口中的方法，也实现了 Deque 接口，而 Deque 实现了 Queue 接口，所以可以使用 Deque 与 Queue中的方法。
List 又实现了 Collection 接口，所以也可以使用 Collection 接口中的方法。

方法（查询操作）	说明
E getFirst()	返回此列表中第一个位置的元素
E getLast()	返回此列表中最后一个位置的元素
int size()	返回此集合中的元素数
boolean isEmpty()	判定是否为空集合，是返回true，不是返回false

方法（修改操作）	说明
boolean add(E e)	向集合中加入指定对象 e，增加成功返回true，失败返回false
void addFirst(E e)	从集合头部中删除指定元素 e

方法（批量操作）	说明
void clear()	从此集合中删除所有元素
default Stream< E > stream()	返回以此集合为源的顺序流
ListIterator< E > listIterator()	返回此列表中元素的列表迭代器（以正确的顺序）

3.4、ArrayList和LinkedList的比较

	ArrayList	LinkedList
数据结构	数组	双向链表
是否有序	是	是
线程安全	否	否
查询速度	快	慢
增删速度	慢	快
元素是否可重复	是	是
元素是否可为null	是	是
应用场景	查询较多	增删较多

---

4、Map集合 4.1、Map接口 4.4.1、Map接口中的常用方法

查询操作	说明
int size()	返回此映射中键值映射的数量
boolean isEmpty()	判断集合是否为空，是返回true
V get(Object key)	返回指定键映射到的值
boolean containsKey(Object key)	判断此集合中是否包含指定的键映射关系，是返回true
boolean containsValue(Object value)	判断此集合中是否包含指定的值映射关系，是返回true
boolean isEmpty()	判断集合是否为空，是返回true

修改操作	说明
V put(K key, V value)	向集合中添加指定的键-值映射关系
V remove(Object key)	返回此映射先前与键关联的值，如果映射不包含键的映射，则返回 null

批量操作	说明
void putAll(Map m)	向集合中添加指定集合中所有的键-值映射关系
clear()	清空集合中所有的映射关系
Set< K > keySet()	以Set集合的形式返回该集合中的所有键对象
Collection< V > values()	以Collection集合的形式返回该集合中的所有值对象
Set> entrySet()	返回这个map中各个键值对映射关系的集合

4.2、HashMap类 4.2.1、HashMap介绍

HashMap 是以 key-value(键值对) 对的形式存放数据的，这些数据保存在

transient Node[] table;

并且默认初始长度为16

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

1、HashMap 中会先根据 key 计算出哈希值，在对（数组容量-1）取余，得到的余数，就是元素的位置。

2、当存储的元素增多时这样就会有多个元素的哈希值相同。一个位置就是存储多个 key ，HashMap 就会将元素以链表的方式连接。

3、再 JDK1.8 后，当数组容量>=64且链表长度>8，就会将链表转化为红黑树的形式。红黑树的元素个数小于 6 时，红黑树转化为单向链表。

4、当 HashMap 中的元素超过临界值时，HashMap 就会扩容，临界值 = 容量 * 负载因子（0.75），扩容后的容量时之前的两倍，HashMap 会把之前的元素重新计算放到新的数组中。所以非常消耗性能。

取出时会先从数组的下标 0 开始，再从链表的头节点开始。所以 HashMap 时无序的。

4.2.2、HashMap的常用方法

查询操作	说明
int size()	返回此映射中键值映射的数量
boolean isEmpty()	判断集合是否为空，是返回true
V get(Object key)	返回指定键映射到的值
boolean containsKey(Object key)	判断此集合中是否包含指定的键映射关系，是返回true

修改操作	说明
V put(K key, V value)	向集合中添加指定的键-值映射关系
V remove(Object key)	返回此映射先前与键关联的值，如果映射不包含键的映射，则返回 null

批量操作	说明
clear()	清空集合中所有的映射关系
Set< K > keySet()	以Set集合的形式返回该集合中的所有键对象

4.2.3、HashMap的特点

特点	说明
无序	元素存入的顺序和取出的顺序不一致
key唯一	当key相同时，新值会覆盖旧值
key可为null	key为空时，哈希值为0

优点	缺点
增删改查快	无序

4.2.4、HashMap的构造方法

// 给定初始长度
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

// 无参构造方法
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

// 基于 Map 创建
public HashMap(Map m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

4.3、LinkedHashMap类 4.3.1、LinkedHashMap介绍

LinkedHashMap 使用的时双向链表来保证添加的顺序和输出的顺序一致
并且记录了头节点与尾节点

transient LinkedHashMap.Entry head;
transient LinkedHashMap.Entry tail;

4.3.2、LinkedHashMap的常用方法

查询操作	说明
int size()	返回此映射中键值映射的数量
boolean isEmpty()	判断集合是否为空，是返回true
V get(Object key)	返回指定键映射到的值
boolean containsKey(Object key)	判断此集合中是否包含指定的键映射关系，是返回true

修改操作	说明
V put(K key, V value)	向集合中添加指定的键-值映射关系
V remove(Object key)	返回此映射先前与键关联的值，如果映射不包含键的映射，则返回 null

批量操作	说明
clear()	清空集合中所有的映射关系
Set< K > keySet()	以Set集合的形式返回该集合中的所有键对象

4.3.3、LinkedHashMap的特点

特点	说明
有序	元素存入的顺序和取出的顺序一致
key唯一	当key相同时，新值会覆盖旧值
key可为null	key为空时，哈希值为0

LinkedHashMap 有两种排序方式，添加顺序和访问顺序

4.2.4、LinkedHashMap的构造方法

// 给定初始容量和负载因子
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}

// 给定初始容量
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}

// 使用默认参数
public LinkedHashMap() {
    super();
    accessOrder = false;
}

// 基于Map
public LinkedHashMap(Map m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}

// 给定初始容量、负载因子、访问或插入顺序
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

4.4、TreeMap类 4.4.1、TreeMap介绍

TreeMap 是使用红黑树进行存储数据。
遍历方式为中序遍历

4.3.2、TreeMap的常用方法

TreeMap 实现了 NavigableMap 接口，NavigableMap 又继承了 SortedMap
同时 TreeMap 实现了 Map
所以 TreeMap 有以上的方法

查询操作	说明
int size()	返回此映射中键值映射的数量
boolean isEmpty()	判断集合是否为空，是返回true
V get(Object key)	返回指定键映射到的值
boolean containsKey(Object key)	判断此集合中是否包含指定的键映射关系，是返回true

修改操作	说明
V put(K key, V value)	向集合中添加指定的键-值映射关系
V remove(Object key)	返回此映射先前与键关联的值，如果映射不包含键的映射，则返回 null

批量操作	说明
clear()	清空集合中所有的映射关系
Set< K > keySet()	以Set集合的形式返回该集合中的所有键对象
NavigableMap descendingMap()	返回此映射中包含的映射的逆序视图

4.3.3、TreeMap的特点

特点	说明
对key排序	红黑树使用compareTo对key进行排序
无序	元素存入的顺序和取出的顺序不一致
key唯一	当key相同时，新值会覆盖旧值
key可为null	key为空时，哈希值为0

优点	缺点
对key排序	无序

4.2.4、LinkedHashMap的构造方法

// 无参构造方法
public TreeMap() {
    comparator = null;
}

// 基于Comparator
public TreeMap(Comparator comparator) {
    this.comparator = comparator;
}

// 基于Map
public TreeMap(Map m) {
    comparator = null;
    putAll(m);
}

// 基于SortedMap
public TreeMap(SortedMap m) {
    comparator = m.comparator();
    try {
        buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
    } catch (java.io.IOException cannotHappen) {
    } catch (ClassNotFoundException cannotHappen) {
    }
}

4.5、HashMap、LinkedHashMap、TreeMap比较

	HashMap	LinkedHashMap	TreeMap
结构	数组+单向链表+红黑树	数组+双向链表+红黑树	红黑树
是否有序	无序	有序	无序，对key排序
线程安全	否	否	否
元素是否可重复	新值覆盖旧值	新值覆盖旧值	新值覆盖旧值
元素是否可为null	是	是	是

---

5、Set集合 5.1、Set接口 5.1.1、Set接口中的常用方法

查询操作	说明
int size()	返回此集合中的元素数
boolean isEmpty()	判定是否为空集合，是返回true，不是返回false
boolean contains(Object o)	判定集合内是否包含指定元素 o，是返回true，不是返回false

修改操作	说明
boolean add(E e)	添加此集合尚未包含指定的元素，成功返回true
boolean remove(Object o)	如果这个集合包含指定的元素，删除成功返回true

批量操作	说明
Iterator< E > iterator()	返回此集合中元素的迭代器
boolean containsAll(Collection c)	如果此集合包含指定集合的所有元素，返回 true
boolean addAll(Collection c)	添加指定集合中的所有元素，如果这个集合由于调用而改变，返回true
void clear()	从此集合中移除所有元素
boolean retainAll(Collection c)	从这个集合中移除所有不包含在指定集合中的元素，如果集合因调用这个方法改变，返回true
boolean removeAll(Collection c)	从此集合中删除指定集合中包含的所有元素，如果集合因调用这个方法改变，返回true

5.2、HashSet类 5.2.1、HashSet介绍

This class implements the Set interface, backed by a hash table (actually a HashMap instance). It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. This class permits the null element.

public class HashSet
    extends AbstractSet
    implements Set, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;

    private transient HashMap map;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
}    

从上面和 HashSet 的构造方法中可以看出，HashSet 使用的是 HashMap 存储数据，不同的是 HashSet 把 key 当作 value， 而 value 使用统一的 PRESENT 填充。

5.2.2、HashSet的常用方法

HashSet 实现 Set 接口，拥有 Set 中的方法，其中常用的有

查询操作	说明
int size()	返回此集合中的元素数
boolean isEmpty()	判定是否为空集合，是返回true，不是返回false
boolean contains(Object o)	判定集合内是否包含指定元素 o，是返回true，不是返回false

修改操作	说明
boolean add(E e)	添加此集合尚未包含指定的元素，成功返回true
boolean remove(Object o)	如果这个集合包含指定的元素，删除成功返回true

批量操作	说明
Iterator< E > iterator()	返回此集合中元素的迭代器
void clear()	从此集合中移除所有元素

5.2.3、HashSet的特点

特点	说明
无序	元素存入的顺序和取出的顺序不一致
值唯一
值可为null	key为空时，哈希值为0

优点	缺点
增删改查快	无序

5.2.4、HashSet的构造方法

public HashSet() {
    map = new HashMap<>();
}

public HashSet(Collection c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}

public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}

5.2.5、HashSet与HashMap的区别

HashSet	HashMap
key是value，而 value 使用统一的 PRESENT 填充	key是key，value是value

5.3、LinkedHashSet类 5.3.1、LinkedHashSet的常用方法

查询操作	说明
int size()	返回此集合中的元素数
boolean isEmpty()	判定是否为空集合，是返回true，不是返回false
boolean contains(Object o)	判定集合内是否包含指定元素 o，是返回true，不是返回false

修改操作	说明
boolean add(E e)	添加此集合尚未包含指定的元素，成功返回true
boolean remove(Object o)	如果这个集合包含指定的元素，删除成功返回true

批量操作	说明
Iterator< E > iterator()	返回此集合中元素的迭代器
void clear()	从此集合中移除所有元素

5.3.2、LinkedHashSet的特点

特点	说明
有序	元素存入的顺序和取出的顺序一致
值唯一
值可为null	值为空时，哈希值为0

优点	缺点
有序，增删快	查询慢

5.3.3、LinkedHashSet的构造方法

public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);
}

public LinkedHashSet(int initialCapacity) {
    super(initialCapacity, .75f, true);
}

public LinkedHashSet() {
    super(16, .75f, true);
}

public LinkedHashSet(Collection c) {
    super(Math.max(2*c.size(), 11), .75f, true);
    addAll(c);
}

5.3.3、LinkedHashSet与LinkedHashMap比较

	LinkedHashSet	LinkedHashMap
存储方式	key是value，而 value 使用统一的 PRESENT 填充	key是key，value是value
排序方式	添加顺序，访问顺序	添加顺序

---

5.4、TreeSet类 5.4.1、TreeSet介绍

A NavigableSet implementation based on a TreeMap. The elements are ordered using their natural ordering, or by a Comparator provided at set creation time, depending on which constructor is used.

public class TreeSet extends AbstractSet
    implements NavigableSet, Cloneable, java.io.Serializable
{
    
    private transient NavigableMap m;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    
    TreeSet(NavigableMap m) {
        this.m = m;
    }
}

从上面可以看出 TreeSet 使用的是 TreeMap 存储数据
会对存储的元素进行排序，默认排序为自然排序

5.4.2、TreeSet的常用方法

查询操作	说明
int size()	返回此集合中的元素数
boolean isEmpty()	判定是否为空集合，是返回true，不是返回false
boolean contains(Object o)	判定集合内是否包含指定元素 o，是返回true，不是返回false

修改操作	说明
boolean add(E e)	添加此集合尚未包含指定的元素，成功返回true
boolean remove(Object o)	如果这个集合包含指定的元素，删除成功返回true

批量操作	说明
Iterator< E > iterator()	返回此集合中元素的迭代器
void clear()	从此集合中移除所有元素
Iterator< E > descendingIterator()	按降序返回此集合中元素的迭代器

5.4.3、TreeSet的特点

特点	说明
对值排序	红黑树使用compareTo对值进行排序
无序	元素存入的顺序和取出的顺序不一致
值唯一	树中不会有两个相同的值
值不可以为null	值不可以为null

优点	缺点
对值排序	无序

5.4.4、TreeSet的构造方法

public TreeSet() {
    this(new TreeMap());
}

public TreeSet(Comparator comparator) {
    this(new TreeMap<>(comparator));
}

public TreeSet(Collection c) {
    this();
    addAll(c);
}

public TreeSet(SortedSet s) {
    this(s.comparator());
    addAll(s);
}

4.5、HashSet、LinkedHashSet、TreeSet比较

HashSet	LinkedHashSet	TreeSet
添加，查询快	添加，查询，删除快，有序	排序

---

6、fail-fast快速失败机制

快速失败是 Java 集合中的一种错误机制，当我们多线程对同一容器内的同一内容进行修改时，就会触发快速失败机制。

The number of times this list has been structurally modified. Structural modifications are those that change the size of the list, or otherwise perturb it in such a fashion that iterations in progress may yield incorrect results.
此列表在结构上被修改的次数。 结构修改是那些改变列表大小的修改，或者以其他方式扰乱它，使得正在进行的迭代可能产生不正确的结果。

protected transient int modCount = 0;

具体做法是，在容器类中定义一个 modCount 属性，记录修改次数，初始值为 0，当容器进行添加或者删除时，modCount 加1。

当获取迭代器时，会先读取 modCount 属性

迭代时进行比较。
如果数据不相等，那么说明有其他线程修改了数据，就会抛出异常。

---

7、线程安全的容器

线程不安全	线程安全
ArrayList	CopyOnWriteArrayList
LinkedList
HashMap	ConcurrentHashMap
LinkedHashMap
TreeMap
HashSet	CopyOnWriteArraySet
LinkedHashSet
TreeSet

7.1、CopyOnWriteArrayList的实现原理

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

final void setArray(Object[] a) {
    array = a;
}

以添加方法为例：
当调用 add 方法首先会加锁，然后把之前的数组拿出来，并复制一个长度为原长度 +1 的新数组。再把元素放到新的数组上，再把新数组设置给 array 属性。最后释放锁。
当多个线程进行 add 方法，只能有一个线程进行操作，其他线程会被锁阻挡在外，直至锁被释放。

7.2、ConcurrentHashMap 的实现原理

ConcurrentHashMap 对 Node 节点加锁保证数据更新的安全，而不是对整个数组加锁，这样既保证了数据的安全，也提高了效率。
例如：有两个线程对两个节点中的数据进行操作，如果对整个数组加锁，那么这两个线程需要排队进行。而对节点进行加锁，这两个线程可以同时进行。

7.3、CopyOnWriteArraySet 的实现原理

public class CopyOnWriteArraySet extends AbstractSet
        implements java.io.Serializable {
    private static final long serialVersionUID = 5457747651344034263L;

    private final CopyOnWriteArrayList al;

    
    public CopyOnWriteArraySet() {
        al = new CopyOnWriteArrayList();
    }
}

通过看 CopyOnWriteArraySet 的源码可知，CopyOnWriteArraySet 的实现原理与 CopyOnWriteArrayList 相同