【搞定Java集合框架】第11篇：Java 集合类总结篇

我不是女神ヾ 2022-03-26 12:44 276阅读 0赞

## **本文目录：** ##

**一、List 总结篇**

1、List 接口描述

2、使用场景

3、区别

**二、Map 总结篇**

2.1、Map 概述

2.2、内部哈希：哈希映射技术

2.3  Map 优化

**三、Set 总结篇**

**四、对集合的选择**

4.1  对 List 的选择

4.2  对 Set 的选择

4.3  对 Map 的选择

**五、Comparable 和 Comparator**

--------------------

> **Collection**（单列集合）
> 
> |--- **List ** 【特点：有序（存取有序）、有索引、可重复】
> 
> |         |--- ArrayList：底层数组实现，查找快、增删慢，线程不安全
> 
> |         |--- LinkedList：底层链表实现，查找慢、增删快，线程安全
> 
> |         |--- Vector：底层数组实现，线程安全，已被 ArrayList 取代
> 
> |                    |--- Stack：继承 Vector ，先进后出的特点
> 
> |--- **Set ** 【底层都是采用 相关 Map 结构存储数据、无序、无索引、不可重复】
> 
>           |--- HashSet：底层使用 HashMap 存储数据，去重
> 
>                       |--- LinkedHashSet：内部使用 LinkedHashMap 来存储元素和操作元素，额外维护了一个双向链表                                                                     用于保持迭代顺序，实现 LRU（最近最少使用）
> 
>           |--- TreeSet：底层使用 TreeMap 存储数据（红黑树实现），去重并排序
> 
> **Map**（双列集合）     
> 
> |--- HashMap ：基于“拉链法”实现的散列表、线程不安全、可以存储 null，但 key 不能重复
> 
> |--- HashTable：基于“拉链法”实现的散列表、线程安全、key 和 value 都不能存 null，已被 HashMap 取代
> 
> |--- TreeMap：底层“红黑树”实现，实现了 SortedMap 接口、线程不安全

# 一、List 总结篇 #

前面已经充分介绍了有关于 List 接口的大部分知识，如 ArrayList、LinkedList、Vector、Stack，通过这几个知识点可以对List 接口有了比较深的了解了。只有通过归纳总结的知识才是你的知识。所以下面就List接口做一个总结。推荐阅读：

**[1、【搞定Java集合框架】第2篇：ArrayList、Vector、Stack ][1_Java_2_ArrayList_Vector_Stack]**

**[2、【搞定Java集合框架】第3篇：LinkedList、Queue][2_Java_3_LinkedList_Queue]**

##  1、List 接口描述 ##

List 接口，称为有序的 Collection，也就是序列。该接口可以对列表中的每一个元素的插入位置进行精确的控制，同时用户可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。 下图是 List 接口的框架图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70][]

通过上面的框架图，可以对 List 的结构了然于心，其各个类. 接口如下：

> **Collection**：Collection 层次结构中的根接口。它表示一组对象，这些对象也称为 Collection 的元素。对于 Collection 而言，它不提供任何直接的实现，所有的实现全部由它的子类负责；
> 
> **AbstractCollection：** 提供 Collection 接口的骨干实现，以最大限度地减少了实现此接口所需的工作。对于我们而言要实现一个不可修改的 Collection，只需扩展此类，并提供 iterator 和 size 方法的实现。但要实现可修改的 Collection，就必须另外重写此类的 add 方法（否则，会抛出 UnsupportedOperationException），iterator 方法返回的迭代器还必须另外实现其 remove 方法；
> 
> **Iterator：** 迭代器；
> 
> **ListIterator：** 系列表迭代器，允许程序员按任一方向遍历列表. 迭代期间可修改列表，并获得迭代器在列表中的当前位置；
> 
> **List：** 继承于Collection的接口。它代表着有序的队列；
> 
> **AbstractList：** List 接口的骨干实现，以最大限度地减少实现“随机访问”数据存储（如数组）支持的该接口所需的工作；
> 
> **Queue：** 队列。提供队列基本的插入、获取、检查操作；
> 
> **Deque：** 一个线性 Collection，支持在两端插入和移除元素。大多数 Deque 实现对于它们能够包含的元素数没有固定限制，但此接口既支持有容量限制的双端队列，也支持没有固定大小限制的双端队列；
> 
> **AbstractSequentialList：** 提供了 List 接口的骨干实现，从而最大限度地减少了实现受“连续访问”数据存储（如链接列表）支持的此接口所需的工作。从某种意义上说，此类与在列表的列表迭代器上实现“随机访问”方法；
> 
> **LinkedList：** List 接口的链接列表实现。它实现所有可选的列表操作；
> 
> **ArrayList：** List 接口的大小可变数组的实现。它实现了所有可选列表操作，并允许包括 null 在内的所有元素。除了实现 List 接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小；
> 
> **Vector：** 实现可增长的对象数组。与数组一样，它包含可以使用整数索引进行访问的组件；
> 
> **Stack：** 后进先出（LIFO）的对象堆栈。它通过五个操作对类 Vector 进行了扩展 ，允许将向量视为堆栈；
> 
> **Enumeration：** 枚举，实现了该接口的对象，它生成一系列元素，一次生成一个。连续调用 nextElement 方法将返回一系列的连续元素；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1][]

## 2、使用场景 ##

**学习知识的根本目的就是使用它。**每个知识点都有它的使用范围。集合也是如此，在 Java 中集合的家族非常庞大，每个成员都有最适合的使用场景。在刚刚接触 List 时，LZ就说过**如果涉及到“栈”、“队列”、“链表”等操作，请优先考虑用List。** 至于是那个 List 则分如下：

> 1、对于需要快速插入. 删除元素，则需使用 LinkedList；
> 
> 2、对于需要快速访问元素，则需使用 ArrayList；
> 
> 3、对于 “单线程环境” 或者 “多线程环境，但是 List 仅被一个线程操作”，需要考虑使用非同步的类，如果是“多线程环境，且 List 可能同时被多个线程操作”，考虑使用同步的类（如 Vector）。

## 3、区别 ##

### 3.1  A**arraylist 和 Linkedlist** ###

> 1、ArrayList 是实现了基于动态数组的数据结构，LinkedList 基于链表的数据结构；
> 
> 2、对于随机访问 get 和 set，ArrayList 绝对优于LinkedList，因为 LinkedList 要移动指针；
> 
> 3、对于新增和删除操作 add 和 remove，LinedList 比较占优势，因为 ArrayList 要移动数据。这一点要看实际情况的。若只对单条数据插入或删除，ArrayList 的速度反而优于 LinkedList。但若是批量随机的插入删除数据，LinkedList 的速度大大优于 ArrayList。因为 ArrayList 每插入一条数据，要移动插入点及之后的所有数据。

### 3.2  Vector 和 ArrayList 的区别 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 2][]

--------------------

# 二、Map 总结篇 #

在前面文章中已经详细介绍了 [HashMap][]、[HashTable][]、[TreeMap][] 的实现方法，从数据结构、实现原理、源码分析三个方面进行阐述，对这个三个类应该有了比较清晰的了解，下面就对 Map 做一个简单的总结。

推荐阅读：

**[1、【搞定Java集合框架】第5篇：HashMap JDK1.7 && JDK 1.8 【面试重点】][1_Java_5_HashMap JDK1.7 _ JDK 1.8]**

**[2、【搞定Java集合框架】第6篇：HashTable 的详解][2_Java_6_HashTable]**

**[3、【搞定Java集合框架】第7篇：深入理解 LinkedHashMap 和 LRU 缓存][3_Java_7_ LinkedHashMap _ LRU]**

**[4、【搞定Java集合框架】第8篇：TreeMap 和红黑树][4_Java_8_TreeMap]**

## 2.1、Map 概述 ##

首先先看 Map 的结构示意图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 3][]

> **Map：** “键值对” 映射的抽象接口。该映射不包括重复的键，一个键对应一个值；
> 
> **SortedMap：** 有序的键值对接口，继承 Map 接口；
> 
> **NavigableMap：** 继承 SortedMap，具有了针对给定搜索目标返回最接近匹配项的导航方法的接口；
> 
> **AbstractMap：** 实现了 Map 中的绝大部分函数接口。它减少了 “Map的实现类” 的重复编码；
> 
> **Dictionary：** 任何可将键映射到相应值的类的抽象父类。目前被 Map 接口取代；
> 
> **TreeMap：** 有序散列表，实现 SortedMap 接口，底层通过红黑树实现；
> 
> **HashMap：** 是基于“拉链法”实现的散列表。底层采用 “数组+链表” 实现；
> 
> **WeakHashMap：** 基于“拉链法”实现的散列表；
> 
> **HashTable：** 基于“拉链法”实现的散列表。

总结如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 4][]

它们之间的区别：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 5][]

## 2.2、内部哈希：哈希映射技术 ##

几乎所有通用 Map 都使用哈希映射技术。对于我们程序员来说我们必须要对其有所了解。

哈希映射技术是一种将元素映射到数组的非常简单的技术。由于哈希映射采用的是数组结构，那么必然存在一种用于确定任意键访问数组的索引机制，该机制能够提供一个小于数组大小的整数，我们将该机制称之为**哈希函数**。在 Java 中我们不必为寻找这样的整数而大伤脑筋，因为**每个对象都必定存在一个返回整数值的 hashCode 方法，而我们需要做的就是将其转换为整数，然后再将该值除以数组大小取余即可**。如下

int hashValue = Maths.abs(obj.hashCode()) % size;

下面是 HashMap、HashTable 的：

----------HashMap------------
    // 计算hash值
    static int hash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
    // 计算key的索引位置
    static int indexFor(int h, int length) {
            return h & (length-1);
    }
    -----HashTable--------------
    int index = (hash & 0x7FFFFFFF) % tab.length;     // 确认该key的索引位置

位置的索引就代表了该节点在数组中的位置。下图是哈希映射的基本原理图：

![20190117115848573.gif][]

在该图中 1-4 步骤是找到该元素在数组中位置，5-8 步骤是将该元素插入数组中。在插入的过程中会遇到一点点小挫折。可能存在多个元素的 hash 值是一样的，这样就会得到相同的索引位置，也就说多个元素会映射到相同的位置，这个过程我们称之为**“冲突”**。

解决冲突的办法就是在索引位置处插入一个链表，并简单地将元素添加到此链表。当然也不是简单的插入，在HashMap 中的处理过程如下：获取索引位置的链表，如果该链表为 null，则将该元素直接插入，否则通过比较是否存在与该key 相同的 key，若存在则覆盖原来 key 的 value 并返回旧值，否则将该元素保存在链头（最先保存的元素放在链尾）。下面是 HashMap 的 put 方法，该方法详细展示了计算索引位置，将元素插入到适当的位置的全部过程：

public V put(K key, V value) {
    	// 当key为null，调用putForNullKey方法，保存null与table第一个位置中，这是HashMap允许为null的原因
    	if (key == null)
    		return putForNullKey(value);
    	// 计算key的hash值
    	int hash = hash(key.hashCode());                 
    	// 计算key hash 值在 table 数组中的位置
    	int i = indexFor(hash, table.length);            
    	// 从i出开始迭代 e,判断是否存在相同的key
    	for (Entry<K, V> e = table[i]; e != null; e = e.next) {
    		Object k;
    		// 判断该条链上是否有hash值相同的(key相同)
    		// 若存在相同，则直接覆盖value，返回旧value
    		if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
    			V oldValue = e.value;    //旧值 = 新值
    			e.value = value;
    			e.recordAccess(this);
    			return oldValue;     //返回旧值
    		}
    	}
    	// 修改次数增加1
    	modCount++;
    	// 将key、value添加至i位置处
    	addEntry(hash, key, value, i);
    	return null;
    }

HashMap 的 put 方法展示了哈希映射的基本思想，其实如果我们查看其它的 Map，发现其原理都差不多。

## 2.3  Map 优化 ##

首先我们这样假设，假设哈希映射的内部数组的大小只有1，所有的元素都将映射该位置（0），从而构成一条较长的链表。由于我们更新、访问都要对这条链表进行线性搜索，这样势必会降低效率。我们假设，如果存在一个非常大数组，每个位置链表处都只有一个元素，在进行访问时计算其 index 值就会获得该对象，这样做虽然会提高我们搜索的效率，但是它浪费了空间。诚然，虽然这两种方式都是极端的，但是它给我们提供了一种优化思路：**使用一个较大的数组让元素能够均匀分布。** **在 Map 有两个会影响到其效率，一是容器的初始化大小、二是负载因子**。

### 2.3.1  调整容器初始化的大小 ###

在哈希映射表中，内部数组中的每个位置称作 “存储桶” (bucket)，而可用的存储桶数（即内部数组的大小）称作**容量** (capacity)。我们为了使 Map 对象能够有效地处理任意数的元素，将 Map 设计成可以调整自身的大小。我们知道当 Map 中的元素达到一定量的时候就会调整容器自身的大小，但是这个调整大小的过程其开销是非常大的。调整大小需要将原来所有的元素插入到新数组中。我们知道 index = hash(key) % length。这样可能会导致原先冲突的键不在冲突，不冲突的键现在冲突的，重新计算、调整、插入的过程开销是非常大的，效率也比较低下。所以，**如果我们开始知道 Map 的预期大小值，将 Map调整的足够大，则可以大大减少甚至不需要重新调整大小，这很有可能会提高速度。** 下面是 HashMap 调整容器大小的过程，通过下面的代码我们可以看到其扩容过程的复杂性：

void resize(int newCapacity) {
    	Entry[] oldTable = table;                  // 原始容器
    	int oldCapacity = oldTable.length;         // 原始容器大小
    	if (oldCapacity == MAXIMUM_CAPACITY) {     // 是否超过最大值：1073741824
    		threshold = Integer.MAX_VALUE;
    		return;
    	}
    
    	// 新的数组：大小为 oldCapacity * 2
    	Entry[] newTable = new Entry[newCapacity];    
    	transfer(newTable, initHashSeedAsNeeded(newCapacity));
    	table = newTable;
       /*
    	* 重新计算阀值 =  newCapacity * loadFactor >  MAXIMUM_CAPACITY + 1 ?
    	*                         newCapacity * loadFactor :MAXIMUM_CAPACITY + 1
    	*/
    	threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);   
    }
    
    // 将元素插入到新数组中
    void transfer(Entry[] newTable, boolean rehash) {
    	int newCapacity = newTable.length;
    	for (Entry<K,V> e : table) {
    		while(null != e) {
    			Entry<K,V> next = e.next;
    			if (rehash) {
    				e.hash = null == e.key ? 0 : hash(e.key);
    			}
    			int i = indexFor(e.hash, newCapacity);
    			e.next = newTable[i];
    			newTable[i] = e;
    			e = next;
    		}
    	}
    }

### 2.3.2  调整负载因子 ###

为了确认何时需要调整 Map 容器，Map 使用了一个额外的参数并且粗略计算存储容器的密度。在 Map 调整大小之前，使用”负载因子”来指示 Map 将会承担的“负载量”，也就是它的负载程度，当容器中元素的数量达到了这个“负载量”，则 Map 将会进行扩容操作。负载因子、容量、Map 大小之间的关系如下：负载因子 \* 容量 > map大小  —–>调整Map大小。

例如：如果负载因子大小为 0.75（HashMap 的默认值），默认容量为11，则 11 \* 0.75 = 8.25 = 8，所以当我们容器中插入第 8 个元素的时候，Map 就会调整容器的大小。

**负载因子本身就是在空间和时间之间的折衷：**

> 当我使用较小的负载因子时，虽然降低了冲突的可能性，使得单个链表的长度减小了，加快了访问和更新的速度，但是它占用了更多的空间，使得数组中的大部分空间没有得到利用，元素分布比较稀疏，同时由于 Map 频繁的调整大小，可能会降低性能。
> 
> 但是如果负载因子过大，会使得元素分布比较紧凑，导致产生冲突的可能性加大，从而访问、更新速度较慢。所以我们一般推荐不更改负载因子的值，采用默认值 0.75。

--------------------

# 三、Set 总结篇 #

Set 就是 HashMap 将 value 固定为一个object，只存 key 元素包装成一个 entry 即可，其他和 Map 基本一样。

**所有 Set 几乎都是内部用一个 Map 来实现，因为 Map 里的 KeySet 就是一个Set，而 value 是假值，全部使用同一个Object 即可。**

Set 的特征也继承了那些内部的 Map 实现的特征。

> **HashSet：**内部使用 HashMap 来存储元素和操作元素。
> 
> **LinkedHashSet：**内部使用 LinkedHashMap 来存储元素和操作元素。
> 
> **TreeSet：**内部是TreeMap 的 SortedSet。
> 
> **ConcurrentSkipListSet：**内部是 ConcurrentSkipListMap 的并发优化的 SortedSet。
> 
> **CopyOnWriteArraySet：**内部是 CopyOnWriteArrayList 的并发优化的 Set，利用其 addIfAbsent() 方法实现元素去重，如前所述该方法的性能很一般。

好像少了个 ConcurrentHashSet，本来也该有一个内部用 ConcurrentHashMap 的简单实现，但JDK偏偏没提供。Jetty就自己简单封了一个，Guava 则直接用 java.util.Collections.newSetFromMap(new ConcurrentHashMap())  实现。

--------------------

# 四、对集合的选择 #

## 4.1  对 List 的选择 ##

> 1、对于随机查询与迭代遍历操作，数组比所有的容器都要快。所以在随机访问中一般使用 ArrayList
> 
> 2、LinkedList 使用双向链表对元素的增加和删除提供了非常好的支持，而 ArrayList 执行增加和删除元素需要进行元素位移。
> 
> 3、对于 Vector 而已，我们一般都是避免使用。
> 
> 4、将 ArrayList 当做首选，毕竟对于集合元素而已我们都是进行遍历，只有当程序的性能因为List的频繁插入和删除而降低时，再考虑 LinkedList。

## 4.2  对 Set 的选择 ##

> 1、HashSet 由于使用 HashCode 实现，所以在某种程度上来说它的性能永远比 TreeSet 要好，尤其是进行增加和查找操作。
> 
> 2、虽然 TreeSet 没有 HashSet 性能好，但是由于它可以维持元素的排序，所以它还是存在用武之地的。

## 4.3  对 Map 的选择 ##

> 1、HashMap 与 HashSet 同样，支持快速查询。虽然 HashTable 速度的速度也不慢，但是在 HashMap 面前还是稍微慢了些，所以 HashMap 在查询方面可以取代 HashTable。
> 
> 2、由于TreeMap 需要维持内部元素的顺序，所以它通常要比 HashMap 和 HashTable 慢。

--------------------

# 五、Comparable 和 Comparator #

实现 Comparable 接口可以让一个类的实例互相使用 compareTo 方法进行比较大小，可以自定义比较规则;

Comparator 则是一个通用的比较器，比较指定类型的两个元素之间的大小关系。

[1_Java_2_ArrayList_Vector_Stack]: https://blog.csdn.net/pcwl1206/article/details/86483208
[2_Java_3_LinkedList_Queue]: https://blog.csdn.net/pcwl1206/article/details/86487247
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70]: /images/20220326/1f169ccdd06f4c4a85b23e2c0397cdbe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1]: /images/20220326/9621fe2f6cbd4804abdc3c8beb03cfe5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 2]: /images/20220326/8a048ef897104e46bca4d85979dd50e7.png
[HashMap]: http://www.cnblogs.com/chenssy/p/3521565.html
[HashTable]: http://www.cnblogs.com/chenssy/p/3643886.html
[TreeMap]: http://www.cnblogs.com/chenssy/p/3746600.html
[1_Java_5_HashMap JDK1.7 _ JDK 1.8]: https://blog.csdn.net/pcwl1206/article/details/86497373
[2_Java_6_HashTable]: https://blog.csdn.net/pcwl1206/article/details/86502731
[3_Java_7_ LinkedHashMap _ LRU]: https://blog.csdn.net/pcwl1206/article/details/86504801
[4_Java_8_TreeMap]: https://blog.csdn.net/pcwl1206/article/details/86509957
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 3]: /images/20220326/b69498007be049a488318da2675dd099.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 4]: /images/20220326/faaab451fd0142588ca16543fd3913c2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 5]: /images/20220326/b1f94a2cae904b06a59662dbc16dab72.png
[20190117115848573.gif]: /images/20220326/e2f5848cd18f43bb92c5b8260e9f7309.png