07-集合体系汇总

1. Collection体系集合

1.1 List 表

List接口
特点：有序、有下标、元素可重复
补充：继承了父接口提供的共性方法，同时定义了一些独有的与下标相关的操作方法

List实现类：ArrayList、Vector、LinkedList

① ArrayList 类（数组）

特点：
1. 数组结构实现，查询快、增删慢；
2. JDK1.2版本，运行效率快、线程不安全；

场景：注册（1次） -> 查询（n次）
注意：

• JDK7之前，无参构造方法实际创建长度为 10 的Object数组，用还是不用，数组就在那里，爱用不用(占了内存)
• JDK8之后，无参构造方法实际创建长度为 0 的Object数组，首次add元素时，才执行数组扩容操作，然后真正向数组中插入数据（Lazy懒），用的时候创建或加载，有效降低无用内存的占用。

② Vector 类（数组、线程同步）

特点：
1. 数组结构实现，查询快、增删慢；
2. JDK1.0版本，运行效率慢、线程安全。

③ LinkedList 类（链表）

特点：
1. 链表结构实现，增删快，查询慢；

④ CopyOnWriteArrayList 类（线程安全且高效的List）

public class CopyOnWriteArrayList<E>
extends Object
implements List<E>, RandomAccess, Cloneable, Serializable
说明：

• 符合List特点：有序、有下标、元素可重复
• 线程安全的ArrayList，加强版读写分离；
• 写有锁，读无锁，读写之间不阻塞，优于读写锁；
• 写入时，先copy一个容器副本、再添加新元素，最后替换引用；
• 使用方式与ArrayList无异。

List<String> alist = new CopyOnWriteArrayList<String>();

List基本API使用：【Java】集合框架之List接口和其实现类

1.2 Set 集合

Set接口与实现类
特点：
1）无序、无下标、元素不可重复（当插入新元素时，如果新元素与已有元素进行equals比较，结果为true时，则拒绝新元素插入）
2）set接口并没有提供自己独有的方法，均是继承Collection的方法

Set实现类：HashSet、LinkedHashSet、TreeSet

① HashSet 类（HashCode）

特点：

• 基于HashCode实现元素不重复 - 无序
• 当存入元素的哈希码相同时，会调用equals确认，结果为true，则拒绝后者加入
• 无参构建初始容量为16（负载因子0.75，即+75%容量扩容）
• 底层使用的HashMap类，即将所有需要存储的值，通过HashMap去重存入
• 先判断hashCode是否相同，再==比较地址是否相同，再equals内容是否相同

② LinkedHashSet 类（记录插入顺序）

特点：

• 继承自HashSet，又基于LinkedHashMap来实现的
• 底层使用LinkedHashMap（链表结构）存储，节点形式独立存储数据，并可以指向下一个节点，通过顺序访问节点，可保留元素的插入顺序 - 插入顺序
• 所有方法与HashSet相同，用法也一模一样

③ TreeSet 类（二叉树-自动排序）

特点：

• 基于排列顺序实现元素不重复 - 自动排序
• 实现了SortedSet接口，对所有插入集合的元素自动排序
• 元素对象的类型必须实现Comparable接口，指定排序规则（Integer/String类默认实现），通过重写CompareTo方法才能使用，以确定是否为重复元素

④ CopyOnWriteArraySet 类（线程安全且高效的Set）

public class CopyOnWriteArraySet<E>
extends AbstractSet<E>
implements Serializable
说明：

• 符合Set特点：无序、无下标、元素不重复
• 线程安全的Set，底层使用CopyOnWriteArrayList实现；
• 唯一不同在于，使用addIfAbsent()添加元素(查重)，会遍历数组；
• 如存在元素，则不添加（扔掉副本）；
• 使用方式与HashSet无异。

Set<String> aset = new CopyOnWriteArraySet<String>();

Set基本API使用：【Java】集合框架之Set接口、实现类、排序

>> HashSet排序的两种方法

1）遍历加入到List中使用Collections.sort(list)排序；
2）使用TreeSet的构造创建一个TreeSet对象实现自动排序。

1.3 Queue 队列

• Collection的子接口，表示队列FIFO（First In First Out）

  ① ConcurrentLinkedQueue 类（线程安全且高效的Queue）

• 线程安全、可高效读写的队列，高并发下性能最好的队列；
• 无锁、CAS比较交换算法，修改的方法包含3个核心参数(V,E,N)；
• V：要更新的变量、E：预期值、N：新值
• 只有当V==E时，V=N；否则表示已被更新过，则取消当前操作。

② ArrayBlockingQueue 类（有界阻塞队列 - BlockingQueue实现类）

• 数组结构实现，有界队列。手工固定上限

③ LinkedBlockingQueue类（无界阻塞队列 - BlockingQueue实现类）

• 链表结构实现，无界队列。默认上限Integer.MAX_VALUE

Queue基本API使用：【Java】Queue、BlockingQueue和队列实现生产者消费者模式

2. Map体系集合

特点：

• 用于存储任意键值对（Key-Value）
• 键：无序、无下标、不允许重复（唯一）
• 值：无序、无下标、允许重复

  ① HashMap 类（数组+链表+红黑树）

  特点：
• JDK1.2版本，线程不安全，运行效率快；允许用null作为key或是value
• 无参构建初始容量为16（负载因子0.75，即+75%容量扩容）
• HashMap算法：拿到任何一个对象后，通过hash(key)做运算，key>>>16(除16)，只可能得到0-15之间的一个数组，作为插入数组的下标。

② LinkedHashMap 类（记录插入顺序）

特点：HashMap 的一个子类，保存了记录的插入顺序，也可在构造时带参数，按照访问次序排序。

③ Hashtable 类（线程安全）

特点：JDK1.0版本，线程安全，运行效率慢；不允许null作为key或是value

④ Properties 类（配置文件读取）

特点：Hashtable的子类，要求key和value都是String，通常用于配置文件的读取。
用法：类似HashMap，不需要指定泛型，接口参阅api文档

⑤ TreeMap 类（自动排序）

特点：实现了SortedMap接口（Map的子接口），可以对key自动排序。

⑥ ConcurrentHashMap 类（线程安全且高效的Map）

public class ConcurrentHashMap<K,V>
extends AbstractMap<K,V>
implements ConcurrentMap<K,V>, Serializable
说明：

• 初识容量默认为16段(Segment)，使用分段锁设计；
• 不对整个Map加锁，而是为每个Segment加锁；
• 当多个对象存入同一个Segment时，才需要互斥；
• 最理想状态位16个对象分别存入16个Segment，并行线程数量16个；
• 使用方式与HashMap无异。
  // JDK1.7: 分段锁设计 Segment
  // JDK1.8: CAS交换算法（CAS比较和交换） + 同步锁（锁的是表头）

Map<String, Integer> chmap = new ConcurrentHashMap<String, Integer>();

Map基本API使用：【Java】集合框架之Map接口、实现类详解

>> Map的遍历

* keySet()  // 遍历键，可以再get(key)获取value
* values()  // 遍历值，只能遍历到值
* entrySet() // 遍历键值对，效率最高

Map遍历源码示例：【Java】Map集合遍历的5种方法和特点分析

3. Collecitons 工具类

上图！一图胜千言！

使用示例参考：【Java】线程安全的集合汇总（方法+类）