List、Map、SET、Queue详解

List、Map、SET、Queue

1572961353557.png

Collection接口

Collection是Java中最基本的集合接口。它描述了一组有关集合操作的方法。

 int Size(); //集合大小
 boolean isEmpty(); //是否为空
 boolean contains(Object o); //是否包含某个对象
 Iterator<E> iterator(); //返回一个迭代对象，用来遍历集合中的元素
 Object[] toArray(); //将集合中的元素以数组形式然后返回
 <T> T[] toArray(T[] a); //上一个方法的泛型形式
 boolean add(E e); //将对象e添加进集合，添加成功则返回true
 boolean remove(Object o); //移除某个元素
 boolean containsAll(Collection<?> c); //传入一个集合c，如果c中的元素都存在，则返回true
 boolean addAll(Collection<? extends E> c); //将集合c中的元素全部添加进本集合
 boolean removeAll(Collection<?> c); //本集合减去c集合中的元素
 boolean retainAll(Collection<?> c); //取本集合和c集合的交集
 void clear(); //清空集合
 boolean equals(Object o); //判断相等
 int hashCode(); //获取集合当前的hash值

List接口

List接口也是继承自Collection。与Set不同的是，List可以存储重复的元素。主要有两种实现：ArrayList和LinkedList。

ArrayList没有什么好说的，就像传统的数组一样，实现了RandomAccess接口，有着很快的随机存取速度，但是插入删除的速度就很慢。

LinkedList则与ArrayList恰恰相反，因为用链表来保存数据，所以插入删除元素的速度很快，但是访问数据的速度就不如ArrayList了。LinkedList不但继承了List接口，而且继承了Deque（double-ended queue），所以既拥有List的特征（快速查询、迭代等），又有双端队列的特征（用作队列、栈等）

Set接口

Set接口直接继承自Collection接口，并且方法接口上也一模一样。 Set对添加的元素有一些要求，其不允许出现重复的元素，并且元素之间没有次序。这相当于一个不允许重复的离散的集合。 因此，添加进Set的元素类型需要定义equals方法。若是使用自定义的类，则应该重写equals方法来确保实现自己需要的功能。

Set是只有Key值，value值为NULL的一个特殊的Map。如下对应关系

HashSet——HashMap，TreeSet——TreeMap，LinkedHashSet——LinkedHashMap

Set接口主要实现类：HashSet，TreeSet，LinkedHashSet HashSet是按照哈希来存取元素的，因此速度较快。HashSet继承自抽象类AbstractSet，然后实现了Set、Cloneable、Serializable接口。 TreeSet也是继承自AbstractSet，不过不同的是其实现的是NavigableSet接口。而NavigableSet继承自SortedSet。SortedSet是一个有序的集合。其添加的元素必须实现了Comparable接口，因为其在添加一个元素的时候需要进行排序。NavigableSet则提供了更多的有关元素次序的方法，比如：

 E lower(E e); //找出小于e的元素
 E floor(E e); //找出小于等于e的元素
 E ceiling(E e); //找出大于等于e的元素
 E higher(E e); //找出大于e的元素
 E pollFirst(); //弹出第一个（最小）元素，如果集合为空则返回null
 E pollLast(); //弹出最后一个（最大）元素，如果集合为空则返回null

LinkedHashSet也是Set的一个实现。和HashSet类似，只不过内部用链表来维护，按照元素插入次序来保存。

Queue 接口

这个接口是后来高版本的JDK添加的，可以方便的实现队列和栈及其相关的数据结构。实现类之一PriorityQueue优先队列，严格意义来说，已经破坏了队列的FIFO特性，每次插入新的数据都进行排序，但是打印的时候可能会显示的不是排好序的，这是该容器toString方法的问题，如果一个个poll出来，可以发现是排好序的。 Deque双端队列比较强大，拥有两个智能指针

Collection下线程安全的实现类

CopyOnWriteArrayList：实现了List接口，相当于线程安全的ArrayList。

CopyOnWriteArraySet：继承于AbstractSet类，相当于线程安全的HashSet。CopyOnWriteArraySet内部包含一个CopyOnWriteArrayList对象，它是通过CopyOnWriteArrayList实现的。

ConcurrentSkipListSet：继承于AbstractSet类，相当于线程安全的TreeSet。ConcurrentSkipListSet是通过ConcurrentSkipListMap实现的。

ArrayBlockingQueue：继承于AbstractQueue类，是数组实现的线程安全的有界的阻塞队列。

LinkedBlockingQueue：继承于AbstractQueue类，是单向链表实现的（指定大小）阻塞队列，该队列按FIFO（先进先出）排序元素。

LinkedBlockingDeque：继承于AbstractQueue类，是双向链表实现的（指定大小）双向并发阻塞队列，该阻塞队列同时支持FIFO和FILO两种操作方式。

ConcurrentLinkedQueue：继承于AbstractQueue类，是单向链表实现的无界队列，该队列按FIFO（先进先出）排序元素。

ConcurrentLinkedDeque：继承于AbstractQueue类，是双向链表实现的无界队列，该队列同时支持FIFO和FILO两种操作方式。

1572961381691.png

Map接口

Map（映射）是一个存储键值对的容器接口。每一个元素包含一个key对象和value对象，且元素不允许重复。

Map顾名思义，映射。主要存储一组组具有映射关系的数据，映射关系主要用key:value的键值对形式表示，一组键值对构成了Map的内部类Entity，所以可以把Map当做由Entity构成的集合。在Map接口的实现类中，例如TreeMap是通过红黑树实现，而红黑树在构建过程中比大小的时候，是根据Entity的key来比较的。所以Map内部也可以人为划分为KeySet和ValuesCollections（所谓人为划分，是因为实际存储是绑定在一起的，并不是分开的，分开是逻辑层面的）

Map接口的实现有以下几个： HashMap是最常用的一个实现。HashMap使用hash映射来存取数据，这个速度是相当快，是O(1)的速度。其容量capacity，和负载因子load factor可以在一开始设定。当元素个数达到capacity*load factor的时候，就会进行扩容。 将Entity通过计算Entity.key的HashCode来存储在散列表中，通过数组实现，如果冲突，则通过挂链表来解决。

LinkedHashMap和HashMap类似，只不过内部用链表来维护次序。因此遍历时候的顺序是其插入顺序。

TreeMap是基于红黑树的Map，插入的数据被有次序保存，并且有很高的效率。因此在遍历输出的时候可以得到排序的数据。但是这要求插入的数据实现了comparable接口。

ConcurrentHashMap

JDK1.7的分段锁机制

Hashtable之所以效率低下主要是因为其实现使用了synchronized关键字对put等操作进行加锁，而synchronized关键字加锁是对整个对象进行加锁。也就是说在进行put等修改Hash表的操作时，锁住了整个Hash表，从而使得其表现的效率低下。

因此，在JDK1.5到1.7版本，Java使用了分段锁机制实现ConcurrentHashMap。

简而言之，ConcurrentHashMap在对象中保存了一个Segment数组，即将整个Hash表划分为多个分段。而每个Segment元素，即每个分段则类似于一个Hashtable。在执行put操作时首先根据hash算法定位到元素属于哪个Segment，然后使用ReentrantLock对该Segment加锁即可。因此，ConcurrentHashMap在多线程并发编程中可是实现多线程put操作。

Segment类是ConcurrentHashMap中的内部类，继承于ReentrantLock类。ConcurrentHashMap与Segment是组合关系，一个ConcurrentHashMap对象包含若干个Segment对象，ConcurrentHashMap类中存在“Segment数组”成员。

HashEntry也是ConcurrentHashMap的内部类，是单向链表节点，存储着key-value键值对。Segment与HashEntry是组合关系，Segment类中存在“HashEntry数组”成员，“HashEntry数组”中的每个HashEntry就是一个单向链表。

JDK1.8的改进

在JDK1.7的版本，ConcurrentHashMap是通过分段锁机制来实现的，所以其最大并发度受Segment的个数限制。因此，在JDK1.8中，ConcurrentHashMap的实现原理摒弃了这种设计，而是选择了与HashMap类似的数组+链表+红黑树的方式实现，而加锁则采用CAS原子更新、volatile关键字、synchronized可重入锁实现。

JDK1.8的实现降低锁的粒度，JDK1.7版本锁的粒度是基于Segment的，包含多个HashEntry，而JDK1.8锁的粒度就是HashEntry（首节点）。

JDK1.8版本的数据结构变得更加简单，使得操作也更加清晰流畅，因为已经使用synchronized来进行同步，所以不需要分段锁的概念，也就不需要Segment这种数据结构了，由于粒度的降低，实现的复杂度也增加了。

JDK1.8版本的扩容操作支持多线程并发。在之前的版本中如果Segment正在进行扩容操作，其他写线程都会被阻塞，JDK1.8改为一个写线程触发了扩容操作，其他写线程进行写入操作时，可以帮助它来完成扩容这个耗时的操作。

JDK1.8使用红黑树来优化链表，基于长度很长的链表的遍历是一个很漫长的过程，而红黑树的遍历效率是很快的，代替一定阈值的链表。