Java中的各种集合类

Java中的集合主要分为以下集合类：Map、List、Set、Queue和concurrent包里面供多线程环境下使用的以上几种集合类。

Map

java.util包中提供的常见Map类包括以下几种。这里乱入了个ConcurrentHashMap，放到下面和其他concurrent包的集合一起讲。

HashMap

HashMap 是老生常谈的集合了，学习 HashMap 主要关注点是哈希算法、rehash、数据存储、扩容方式、性能区别和结合ConcurrentHashMap 了解为什么线程不安全，后者怎么解决线程安全问题。

哈希算法

先看一下JDK中 hashCode 的生成方式，JDK 1.8 以后都是如下方式：

static final int hash(Object key) {

这里可以看到，key 不是 null 的情况下，都是取key.hashCode()之后无符号右移16位，然后取异或。这里的key.hashCode()是 native 方法，直接在 JVM 中返回 int 型散列值。

无符号右移>>> ：不管正负标志位为0还是1，将该数的二进制码整体右移，左边部分总是以0填充，右边部分舍弃。

位与：第一个操作数的的第n位于第二个操作数的第n位如果都是1，那么结果的第n为也为1，否则为0

为什么要这么做？

理论上散列值是一个 int 型，如果直接拿散列值作为下标访问 HashMap 主数组的话，考虑到 2 进制 32 位带符号的 int 表值范围从-2147483648到2147483648。前后加起来大概 40 亿的映射空间。只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。

但问题是一个 40 亿长度的数组，内存是放不下的。你想，HashMap 扩容之前的数组初始大小才 16。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来访问数组下标。

顺便说一下，这也正好解释了为什么 HashMap 的数组长度要取 2 的整次幂。因为这样（数组长度 -1）正好相当于一个“低位掩码”。“与”操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。以初始长度 16 为例，16-1=15。2 进制表示是00000000 00000000 00001111。和某散列值做“与”操作如下，结果就是截取了最低的四位值。即

   10100101 11000100 00100101

但这时候问题就来了，这样就算我的散列值分布再松散，要是只取最后几位的话，碰撞也会很严重。更要命的是如果散列本身做得不好，分布上成等差数列的漏洞，恰好使最后几个低位呈现规律性重复，就无比蛋疼。

这时候“扰动函数”的价值就体现出来了，说到这里大家应该猜出来了。看下面这个图:

右位移 16 位，正好是 32bit 的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。

扩容

HashMap 两个关键的初始化参数：

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

前者是初始化容量 16，即新建一个 HashMap 的时候，如果不指定长度，则容量为 16。

后者是加载因子，即当实际长度除以容量高于该因子的时候，进行扩容操作。默认为 0.75，所以 HashMap 空间占用大于 3/4 的时候就开始扩容了。扩容后的容量是原来的两倍。

HashMap 的 resize 不是简单的把长度扩大，而是有下面两个步骤：

1. 扩容：创建一个新的 Entry 空数组，长度是原数组的2倍。
2. reash：遍历原 Entry 数组，把所有的 Entry 重新 hash 到新数组。为什么要重新 hash 呢？因为长度扩大以后，hash 的规则也随之改变。

让我们回顾一下 hash 公式：

index = hashCode(key) & (length - 1)

当原数组长度为 8 时，hash 运算是和111B做与运算；新数组长度为 16，hash 运算是和1111B做与运算。hash 结果显然不同。

那么这里为什么要用 map 容量减去 1 这个数字哪？好处有两个：

1. 分布均匀
2. 速度更快

在 HashMap 的源码中。get和put方法会根据 key 的 hash 值找到这个 entry 在 hash 表数组中的位置，源码如下：

if ((p = tab[i = (n - 1) & hash]) == null)

按照我们理想的状况，hashMap 的存取就是 O(1)，也就是直接根据 hashcode 就可以找到它，每个 bucket 只存储一个节点，链表指向都是null，这样就比较开心了，不要出现一个链表很长的情况。

所以我们希望它能分布的均匀一点，如果让我们设计的话，我们肯定是直接对长度取模：hashcode % length，但 HashMap 的设计者却不是这样写的，它写成了 2 进制运算，因为当容量一定是2^n时，h & (length - 1) == h % length，并且位运算的速度要高于取模。

另外，元素在重新计算 hash 之后，因为 n 变为 2 倍，新的 index 的二进制就是在前面多了一位，比如原来的容量为 8 的时候，元素下标为 5，扩容到 16 之后，根据多的那一位是 0 还是 1，元素下标只需要 +8 或者在原位置就可以了，也就是说 resize 操作也会更快。

存储方式

HashMap 实际是一种“数组+链表”数据结构。在 put 操作中，通过内部定义算法寻址找到数组下标，将数据直接放入此数组元素中，若通过算法得到的该数组元素已经有了元素（俗称 hash 冲突，链表结构出现的实际意义也就是为了解决 hash 冲突的问题）。将会把这个数组元素上的链表进行遍历，将新的数据放到链表末尾。

通过哈希算法从寻止上能够高效的找到对应的下标，但是随着数据的增长，哈希冲突碰撞过多。在寻找数据时，先找到链表，然后通过遍历在寻找对应数据，如此将会使得 get 数据效率越来越低。在 JDK 1.8 中，链表元素数量大于等于 8 将会重组该链表结构形成为“红黑树结构”，这种结构使得在 hash 冲突碰撞过多情况下，get效率比链表的效率高很多。

性能

在没有哈希冲突的情况下，HashMap 存取元素的时间复杂度是 O(1)，但是这只是理想情况。当冲突不多的时候，重复元素以链表形式存储，时间复杂度是 O(N)，当数据量大的时候，链表转换为红黑树，时间复杂度变成 O(LogN)

线程安全和其他局限

HashMap 不是线程安全的，另外如果 HashMap 的 key 是自定义类，需要重写hashCode()方法，并且由于 HashMap 的效率高度依赖hashCode()，需要保证散列分布尽量均匀。

都知道 HashMap 不是线程安全的，那么在哪些环节导致了他线程不安全？

1. 插入数据的时候

   tab[i] = newNode(hash, key, value, null);

   假如 A 线程和 B 线程同时添加元素，然后计算出了相同的哈希值对应了相同的数组位置，因为此时该位置还没数据，然后对同一个数组位置添加，B 的写入操作就会覆盖 A 的写入操作造成 A 的写入操作丢失。

2. 修改数据的时候

   跟上面同样，多个线程同时修改数据，可能产生错误。

3. 扩容的时候

   线程 1 执行put时，因为元素个数超出threshold而导致 rehash，线程 2 此时执行get，有可能导致这个问题。

   因为在 resize 的时候，是计算新的容量和threshold，在创建一个新 hash 表，最后将旧 hash 表中元素 rehash 到新的 hash 表中。如果在这个期间，另一个线程执行读取操作，有可能get到null。

那么 ConcurrentHashMap 如何保证线程安全？这个在另一篇文章中单独叙述。

LinkedHashMap

LinkedHashMap 是继承自 HashMap 的，跟 HashMap 最大的区别是，他是基于 Hash 表和链表的实现，并且依靠着双向链表保证了迭代顺序是插入的顺序。

来看看 HashMap 和 LinkedHashMap 的结构图，是不是秒懂了。LinkedHashMap 其实就是可以看成 HashMap 的基础上，多了一个双向链表来维持顺序。

可以用 LinkedHashMap 实现最近访问算法，即最近访问过的元素在最前面， LinkedHashMap 有这么一个构造方法。

public LinkedHashMap(int initialCapacity, float loadFactor,boolean accessOrder)

accessOrde为true的时候按照元素最后访问时间排序（LRU算法：最近最久使用），为false则是按照插入顺序排序，默认为false.

TreeMap

TreeMap 是基于红黑树的实现，具有如下特点：

• 不允许出现重复的 key；
• 可以插入null键，null值；
• 可以对元素进行排序；
• 无序集合（插入和遍历顺序不一致）；

由于是基于红黑树，TreeMap 在插入、删除、搜索的时候，时间复杂度都是 O(LogN)。红黑树的结构单独另外说明，这里就不赘述。

EnumMap

EnumMap 是专门为枚举类型量身定做的 Map 实现。虽然使用其它的 Map 实现（如 HashMap）也能完成枚举类型实例到值得映射，但是使用 EnumMap 会更加高效：它只能接收同一枚举类型的实例作为键值，并且由于枚举类型实例的数量相对固定并且有限，所以 EnumMap 使用数组来存放与枚举类型对应的值。这使得 EnumMap 的效率非常高。EnumMap 在内部使用枚举类型的ordinal()得到当前实例的声明次序，并使用这个次序维护枚举类型实例对应值在数组的位置。

在 key 是枚举类的时候，EnumMap 可以用来代替 HashMap，并且由于是数组实现，性能更好。

HashTable

Hashtable 与 HashMap 的简单比较

1. HashTable 基于 Dictionary 类，而 HashMap 是基于 AbstractMap。Dictionary 是任何可将键映射到相应值的类的抽象父类，而 AbstractMap 是基于 Map 接口的实现，它以最大限度地减少实现此接口所需的工作。

2. HashMap 的 key 和 value 都允许为null，而 Hashtable 的 key 和 value 都不允许为null（出于并发上取不到值的考虑）。HashMap 遇到 key 为null的时候，调用putForNullKey方法进行处理，而对 value 没有处理；Hashtable遇到null，直接返回NullPointerException。

3. Hashtable 方法是同步，而 HashMap 则不是。我们可以看一下源码，Hashtable 中的几乎所有的 public 的方法都是synchronized的，而有些方法也是在内部通过synchronized代码块来实现。所以有人一般都建议如果是涉及到多线程同步时采用 HashTable，没有涉及就采用 HashMap，但是在 Collections 类中存在一个静态方法：synchronizedMap()，该方法创建了一个线程安全的 Map 对象，并把它作为一个封装的对象来返回。

4. HashMap的初始容量为 16，Hashtable 初始容量为 11，两者的填充因子默认都是 0.75。

5. 两者计算 hash 的方法不同

   Hashtable 计算 hash 是直接使用 key 的 hashcode 对 table 数组的长度直接进行取模

   int hash = key.hashCode();

   HashMap 计算 hash 对 key 的 hashcode 的前后 16 位进行了异或操作，以获得更好的散列值，然后对 table 数组长度取模（实际上是位操作，增加效率）

      static final int hash(Object key) {

IdentityHashMap

IdentityHashMap 是一致性哈希表，使用引用相等，而不是equals方法来比较两个对象的相等性。因此，IdentityHashMap 中，如果存在两个键 key1 和 key2，当且仅当key1==key2时，两个键相等，而其他大部分的哈希表，当且仅当k1 == null ? k2 == null : k1.equals(k2)时，两个键才认为是相等的。

IdentityHashMap 使用System.identityHashCode来确定对象的哈希码，该方法返回对象的地址。

看下IdentityHashMap的存储原理图，和 HashMap 不同，HashMap 是通过数组+拉链法存储元素并解决哈希冲突的。IdentityHashMap 将所有的 key 和 value 都存储到Object[]数组 table 中，并且 key 和 value 相邻存储，当出现哈希冲突时，会往下遍历数组，直到找到一个空闲的位置。注意，数组第一个位置存储的是 key，第二个位置存储的是 value。因此奇数位置处存储的是 key，偶数位置处存储的是 value。

IdentityHashMap 同样允许空的键和值，但是不保证 map 中的顺序，尤其是不保证顺序会恒定不变。

WeakHashMap

和 HashMap 一样，WeakHashMap 也是一个散列表，它存储的内容也是键值对(key-value)映射，而且键和值都可以是null。不过 WeakHashMap 的键是“弱键”。

当弱引用指向的对象只能通过弱引用（没有强引用或弱引用）访问时，GC会清理掉该对象，之后，引用对象会被放到ReferenceQueue中。在 Entry 的构造函数中可以得知，通过super(key, queue)将 key 保存为弱引用，通过this.value = value将 value 保存为强引用。当 key 中的引用被 gc 掉之后，在下次访问 WeakHashMap（调用expungeStaleEntries函数）时相应的 entry 也会自动被移除。

WeakHashMap 并不是你什么也不干它就能自动释放内部不用的对象的，而是在你访问它的内容的时候释放内部不用的对象。

List

java.util包中提供的常见List类包括以下几种。

从刚学 Java 的前几天起，大概就会见到这个问题：LinkedList 和 ArrayList 有什么共同点和区别？

共同点：

1. 二者都是继承自 AbstractList 抽象类，AbstractList 实现了 List 接口中除了size()、get(int location)之外的方法。
2. 二者都是线程不安全的。

区别：

1. ArrayList 是实现了基于动态数组的数据结构，而 LinkedList 是基于链表的数据结构；
2. 数据更新和查找时，ArrayList 可以直接通过数组下标访问，所以效率更高。
3. 数据增加和删除的时候，ArrayList 需要移动其他元素的位置，而 LinkedList 只需要修改一个指针，所以后者效率更高。

Vector

Vector 是同样继承于AbstractList的一个列表，而它是线程安全的，实现方式是对所有数据操作的方法添加了 synchronized 关键字。其与 ArrayList 的差别如下：

• 构造函数，ArrayList 比 Vector 稍有深度，Vector 默认数组长度为 10，创建是设置。
• 扩容方法 grow()，ArrayList 通过位运算进行扩容，而 Vector 则通过增长系数（创建是设置，如果过为空，则增长一倍）
• Vector 方法调用是线程安全的。
• 成员变量有所不同

Stack

Stack 栈是 Vector 的一个子类，它实现了一个标准的后进先出的栈。

他的方法很简单，只有empty()、peek()、pop()、push(Object element)、search(object element)这几个。其中 peek 和 pop 的返回值都是堆栈顶部的对象，但是前者只是查看，后者是移除。

Set

java.util包中提供的常见Set类包括以下几种。

HashSet 没什么好说的，其实就是把 HashMap 封装了一层，从 HashSet 的构造方法可以看出，就是维护了一个 HashMap，数据的增删改查也是调用的 HashMap 的方法。

TreeSet 也是一样，其实就是 TreeMap 套了个皮。

EnumSet 就不一样了，跟 EnumMap 其实没有什么关系。EnumSet 是一个 Set 集合的抽象类，其有两个实现类 JumboEnumSet 和 RegularEnumSet，在使用的时候放入的必须是枚举类型，其特点是速度非常快。

EnumSet 的默认子类 RegularEnumSet 和 JumboEnumSet 实现原理都是基于位运算向量，位运算向量的原理就是用一个位表示一个元素的状态（元素的状态只有两种），用一组位表示一个集合的状态，每个位对应一个元素，譬如一个枚举类 DemoEnum 有6个枚举值，则 EnumSet 集合就可以通过一个 byte 字节从右到左（二进制低到高位）来表示，不用的位上用 0 填充，用的位上每个 bit 位代表一个枚举值，1 表示包含该枚举值，0 表示不含该枚举值。因此位向量能表示的枚举值个数与向量长度有关，上面例子中一个 byte 类型最多能表示 8 个枚举值，所以 EnumSet 抽象类的两个实现类 RegularEnumSet 和 JumboEnumSet 分别定义了不同的向量长度。RegularEnumSet 使用 64 位的 long 类型变量作为位向量，而 JumboEnumSet 使用一个 long 类型数组作为向量（数组内存连续），故当我们通过 EnumSet 的工厂方法创建 EnumSet 集合时 EnumSet 会通过判断枚举类的枚举值数量决定使用两个子类的哪一个，如果枚举值个数小于等于 64 就用 RegularEnumSet，大于 64 就用 JumboEnumSet。

简单来说 EnumSet 就是一个高效的枚举类集合。

Queue

队列(Queue)可以当做一种特殊的线性表，遵循先进先出原则。而双向队列(Deque)，是 Queue 的一个子接口，双向队列是指该队列两端的元素既能入队(offer)也能出队(poll),如果将 Deque 限制为只能从一端入队和出队，则可实现栈的数据结构。

PriorityQueue 有一种特殊的队列，叫做优先队列。优先队列的作用是能保证每次取出的元素都是队列中权值最小的（Java的优先队列每次取最小元素，C++的优先队列每次取最大元素）。这里牵涉到了大小关系，元素大小的评判可以通过元素本身的自然顺序（natural ordering），也可以通过构造时传入的比较器（Comparator，类似于C++的仿函数）。

Java 中 PriorityQueue 实现了 Queue 接口，不允许放入null元素；其通过堆实现，具体说是通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值），也就意味着可以通过数组来作为 PriorityQueue 的底层实现。

最小堆的完全二叉树有一个特性是根节点必定是最小节点，子女节点一定大于其父节点。还有一个特性是叶子节点数量 = 全部非叶子节点数量 +1。

每次增删元素都有可能对树结构进行调整，所以 PriorityQueue 队列不适合进场出队入队的频繁操作，但是他的优先级特性非常适合一些对顺序有要求的数据处理场合。

concurrent包

ConcurrentHashMap

上面 HashMap 已经说到了 HashMap 在多个线程同时存取或者触发扩容的时候，都有可能出现错误，导致操作被覆盖或者丢失，那么怎么解决这个问题呐？

第一反应当然是加锁，HashTable 就是这么做的，使用了synchronized关键字。虽然解决了并发访问的安全性问题，但是性能不怎么样。HashTable 中的增删改、甚至equals、toString方法等等都是方法级的锁，所以同时只能一个线程去操作，导致效率问题。

在 JDK 1.7 及之前版本，ConcurrentHashMap 采用的是 Segment 分段锁，即将数据分为一段一段的存储，然后给每一段数据加一把锁。当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。

在 JDK 1.8 以后，ConcurrentHashMap 取消了 Segment 分段锁，采用 CAS 和synchronized来保证并发安全。 数据结构与 HashMap 1.8 的结构类似，数组+链表/红黑二叉树(链表长度 >8 时，转换为红黑树)。

通过 JDK 的源码和官方文档看来， 他们认为的弃用分段锁的原因由以下几点：

1. 加入多个分段锁浪费内存空间。
2. 生产环境中， map 在放入时竞争同一个锁的概率非常小，分段锁反而会造成更新等操作的长时间等待。
3. 为了提高 GC 的效率。

在 JDK 11 下对 HashMap 和 ConcurrentHashMap 进行了简单测试，生成 5000 万条随机数然后插入，分别消耗 16348 毫秒和 19194 毫秒。其中包括随机数生成、插入和扩容的时间消耗，可见两者之间性能差距不大。

然后使用 HashTable 在单线程下插入，同样的数据量时间在 17 秒所有，跟 HashMap 差别不大，可以当做是误差范围内。然后使用 20 个线程插入，消耗时间在 15 秒左右，提升并不明显。奇怪的是 ConcurrentHashMap 却使用了 45 秒。然后缩小数据量，在 1000 万以下的时候，ConcurrentHashMap 的插入速度又好于 HashTable 了。这个现象很有意思，有空了详细研究一下产生这个问题的原因。

ConcurrentHashMap 的整体性能要优于 HashTable，但是某些场景不能替代 HashTable，例如强一致性的场景，ConcurrentHashMap 的get、size等方法都没有加锁，ConcurrentHashMap 是弱一致性的。更多关于 ConcurrentHashMap 的原理在另一个文章中单独分析。

ConcurrentSkipListMap

ConcurrentSkipListMap 提供了一种线程安全的并发访问的排序映射表。内部是 SkipList（跳表）结构实现，在理论上能够在 O(logN) 时间内完成查找、插入、删除操作。

ConcurrentHashMap 与 ConcurrentSkipListMap 性能测试
在4线程1.6万数据的条件下，ConcurrentHashMap 存取速度是 ConcurrentSkipListMap 的4倍左右。

但 ConcurrentSkipListMap 有几个 ConcurrentHashMap 不能比拟的优点：

1、ConcurrentSkipListMap 的 key 是有序的。

2、ConcurrentSkipListMap 支持更高的并发。ConcurrentSkipListMap 的存取时间是 log(N)，和线程数几乎无关。也就是说在数据量一定的情况下，并发的线程越多， ConcurrentSkipListMap 越能体现出他的优势。

CopyOnWriteArrayList

先讲一下什么是Copy-On-Write，通俗的理解是当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行 Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。对 CopyOnWrite 容器进行并发的读的时候，不需要加锁，因为当前容器不会添加任何元素。所以 CopyOnWrite 容器也是一种读写分离的思想，延时更新的策略是通过在写的时候针对的是不同的数据容器来实现的，放弃数据实时性达到数据的最终一致性。

public boolean add(E e) {

CopyOnWriteArrayList 的实现也不复杂，对有并发风险的操作加了锁。注意这里的内部数组是volatile修饰的，写线程对数组引用的修改对读线程是可见的。由于在写数据的时候，是在新的数组中插入数据的，从而保证读写实在两个不同的数据容器中进行操作。

参考资料：

JDK 源码中 HashMap 的 hash 方法原理是什么？

HashMap底层实现原理

【java并发】造成HashMap非线程安全的原因

IdentityHashMap源码详解

WeakHashMap实现原理及源码分析

EnumSet 原理相关

Java源码分析：HashMap 1.8 相对于1.7 到底更新了什么？（这篇非常细致）