当前位置：首页 > article >正文

【常用集合】深入浅出Map集合

article 2024/11/13 14:50:47

HashMap

HashMap 主要用来存放键值对，它基于哈希表的 Map 接口实现，是常用的 Java 集合之一，是非线程安全的。

HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个。

底层实现

通过 key 的 hashCode 经扰动函数处理得到 hash 值，并通过 hash & (length - 1) 确定存储位置（length为数组的长度）。若位置已有元素，比较 hash 值和 key，相同则覆盖，不同则用链表解决冲突。扰动函数用于优化 hashCode() 实现，减少哈希碰撞。

存储结构

在 JDK 1.8 之前，HashMap 采用 链地址法 来解决哈希冲突，即将数组与链表结合使用。当多个元素的哈希值映射到同一个桶位时，HashMap 会在该桶位置创建一个链表，所有冲突的元素都以链表的形式存储。在插入新元素时，HashMap 使用 头插法，将新元素插入链表的开头位置，以此处理哈希冲突。
在 JDK 1.8 之后，HashMap 解决哈希冲突的方式进行了优化，仍然采用 数组+链表 的结构，但引入了 红黑树 来提高性能。当某个桶位上的链表长度超过阈值（默认 8），并且哈希表桶的长度大于64时，链表会转换为红黑树，从而将链表的查询元素的时间复杂度由 O(n) 降低为 O(log n)。这样，当哈希冲突较多时，HashMap 仍然能够保持较高的查询和插入效率。

数据插入方式

在 JDK 1.7 及之前的版本中，HashMap 在多线程环境下进行扩容时，由于使用头插法重排链表，多个线程同时操作同一桶位的链表可能导致节点指向错误，形成环形链表，从而引发死循环。

为了解决这个问题，JDK1.8 版本的 HashMap 采用了尾插法来避免链表倒置，使得插入的节点永远都是放在链表的末尾，避免了链表中的环形结构。

长度取值

HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。并且， HashMap 总是使用 2 的幂作为哈希表的大小。长度采用 2 的幂，是因为二进制位操作&相对于取模运算%能够提高效率。位运算直接对内存数据操作，不需要转换成10进制进行取模运算。

公式（hash % length == hash & (length - 1)成立的前提是Hash表的长度是 2 的 n 次方。

并发安全问题

死锁问题

为了解决这个问题，JDK1.8 版本的 HashMap 采用了尾插法来避免链表倒置，使得插入的节点永远都是放在链表的末尾，避免了链表中的环形结构。

其他问题

多线程put的时候，size的个数和真正的个数不一样
多线程put的时候，可能会把上一个put的值覆盖掉
当既有get操作，又有扩容操作的时候，有可能数据刚好被扩容换了桶，导致get不到数据
和其他不支持并发的集合一样，HashMap也采用了fail-fast操作，当多个线程同时put和get的时候，会抛出并发异常

扩容机制

触发扩容

HashMap 中的容量阈值（threshold）是由当前数组容量与负载因子相乘得到的capacity * loadFactor。当 HashMap 中的元素数量超过这个阈值时，会触发扩容操作。默认的负载因子为 0.75，数组的初始容量为 16。

扩容过程

在扩容过程中，HashMap 会创建一个新的数组，容量是原数组的两倍。所有原数组的元素都会被重新分配到这个新数组中。

节点迁移

桶元素重新映射： 如果桶中只有一个元素，没有形成链表，则将原来的桶引用置为null，同时，将该元素进行rehash即可。
链表重新链接： 扩容后的数据迁移实际上是部分的，一些元素保持原位置，而另一些元素则会被迁移到新的位置。这种优化减少了不必要的数据移动，提升了扩容操作的效率。
1. 保持原位置：对于某个元素，如果 hash & oldLength == 0，那么该元素在扩容后的新数组中仍然保留在原位置。
2. 移动到新位置：如果 hash & oldLength != 0，那么该元素在扩容后的新数组中的位置将从 index 变为 index + oldLength。
取消树化： 类似于上述链表的重新链接，当重新链接操作完毕后，会判断两个哈希桶上的链表长度是否小于等于6，如果满足条件，会将红黑树取消树化，退化成链表。

示例：旧哈希桶长度为8，有a、b、c、d四个元素，存储在下标为3的哈希桶上。

hash(a)=3;  hash(a)&7=3;
hash(b)=11; hash(b)&7=3;
hash(c)=27; hash(c)&7=3;
hash(d)=59; hash(d)&7=3;

如果扩容为16，由于hash(a)&8=0;无需移动，其他的不为零的元素移动到index + oldLength = 3 + 8 = 11

hash(a)=3;  hash(a)&8=0; hash(a)&15=3;
hash(b)=11; hash(b)&8=8; hash(b)&15=11
hash(c)=27; hash(c)&8=8; hash(c)&15=11
hash(d)=59; hash(d)&8=8; hash(d)&15=11

为什么HashMap的负载因子设置为0.75？

性能和空间的平衡：
负载因子过低（例如 0.5），意味着更频繁地扩容，虽然哈希冲突会减少，但空间利用率较低，增加了内存消耗。
负载因子过高（例如 1.0），虽然提高了空间利用率，但增加了哈希冲突的概率，降低了查找和插入的效率。

数学依据：
负载因子选择为0.75（3/4），可以保证临界值 threshold = loacFactor * capacity为整数。

ConcurrentHashMap

底层实现

同HashMap

线程安全

JDK1.8之前：
- 使用分段锁：在 JDK 1.7 及之前，ConcurrentHashMap 通过分段锁机制来实现线程安全。它将整个哈希表分为多个段（Segment），每个段内部维护一个独立的哈希表和锁。当对 ConcurrentHashMap 进行并发操作时，不同的线程可以同时操作不同的段，从而提高并发性。
- Segment 是继承了 ReentrantLock 的子类：每个段都有自己独立的可重入锁，而操作的同步性依赖于 Segment 的锁机制。
JDK1.8之后：
- 移除了分段锁：在 JDK 1.8 中，ConcurrentHashMap 不再使用分段锁。相反，它直接使用了一个Node<K, V>[]数组来存储键值对，并且通过更细粒度的锁和无锁操作来实现线程安全。
- CAS 操作：在插入和删除节点时，ConcurrentHashMap 使用 CAS（Compare-And-Swap）来确保并发安全。例如，当向一个空桶中插入第一个节点时，ConcurrentHashMap 会使用 CAS 操作直接插入，这样可以避免锁的使用。
- Synchronized 锁：在一些复杂操作（如链表或红黑树的插入或删除）中，ConcurrentHashMap 使用 synchronized 来锁定特定的桶（Node），而不是整个段或整个哈希表。这种方式虽然引入了锁，但锁的粒度非常小，只会锁定冲突的桶，因此可以大大减少锁竞争。
并发度：
- JDK1.8之前，最大并发度是Segment的个数，默认是 16。
- JDK1.8之后，最大并发度是Node<K, V>[]数组的大小，并发度更大。

为什么key和value都不能为null?

null是一个特殊的值，表示没有对象或没有引用。

key为null：
- 防止异常：如果键为 null，哈希计算过程中会抛出 NullPointerException。
value为null：
- 简化实现：在并发条件下无需对null值进行特殊处理，减少条件分支，提高可维护性。
- 避免二义性：如果使用get(key)方法获取的value为null，则可能该 key 存在，但其对应的值是 null；或者该 key 不存在。

保证复合操作的原子性

ConcurrentHashMap 是线程安全的，这意味着它能够保证在多线程环境下对其进行并发读写操作时，不会出现数据不一致的情况。此外，它也避免了 JDK 1.7 及之前版本的 HashMap 中，在多线程操作时可能导致的 死循环问题。然而，线程安全 不等于 原子性，尤其是在涉及多个操作的情况下，ConcurrentHashMap 并不能确保所有的复合操作都是原子性的。

复合操作： 是指由多个基本操作（如 put、get、remove、containsKey 等）组合而成的操作。

例如：如果多个线程同时调用 containsKey 进行检查并随后调用 put，在第一个线程判断某个键不存在时，另一个线程可能已经插入了该键，这样第一个线程的操作就会覆盖另一个线程的结果，导致数据不一致。

为了解决复合操作的原子性问题，ConcurrentHashMap 提供了一些内置的原子复合操作方法。这些方法能够确保整个操作过程在并发环境下是原子性的，即要么全部成功，要么全部失败，不会出现中间状态。

putIfAbsent(K key, V value)
- 如果指定的键 key 尚未存在于 ConcurrentHashMap 中，则将其对应的值设置为 value。该操作是原子性的，能够确保在并发情况下，只有第一个插入的线程成功，后续插入将被忽略。
- 这种操作特别适合用于避免重复插入。
computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)
- 只有当指定的键 key 存在时，才会根据提供的 remappingFunction 计算新值并更新。如果键不存在，则不执行任何操作。该方法同样确保了计算和更新的原子性。

Map对比

HashMap和Hashtable的区别

线程是否安全： HashMap 是非线程安全的，Hashtable 是线程安全的,因为 Hashtable 内部的方法基本都经过synchronized 修饰。
效率： 因为线程安全的问题，HashMap 要比 Hashtable 效率高一点。另外，Hashtable 基本被淘汰，不要在代码中使用它；
对 Null key 和 Null value 的支持： HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；Hashtable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。
初始容量大小和每次扩充容量大小的不同： ① 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小。
底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树），以减少搜索时间（后文中我会结合源码对这一过程进行分析）。Hashtable 没有这样的机制。

HashMap和HashSet的区别

HashSet 底层就是基于 HashMap 实现的。

`HashMap`	`HashSet`
实现了 `Map` 接口	实现 `Set` 接口
存储键值对	仅存储对象
调用 `put()`向 map 中添加元素	调用 `add()`方法向 `Set` 中添加元素
`HashMap` 使用键（Key）计算 `hashcode`	`HashSet` 使用成员对象来计算 `hashcode` 值，对于两个对象来说 `hashcode` 可能相同，所以`equals()`方法用来判断对象的相等性

HashMap和TreeMap的区别

TreeMap 和HashMap 都继承自AbstractMap ，但是需要注意的是TreeMap它还实现了NavigableMap接口和SortedMap 接口。

实现 NavigableMap 接口让 TreeMap 有了对集合内元素的搜索的能力。

实现SortedMap接口让 TreeMap 有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序，不过我们也可以指定排序的比较器。

ConcurrentHashMap 和 Hashtable 的区别

底层数据结构

JDK1.7 的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样采用数组+链表/红黑二叉树。
Hashtable 一直采用的是 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；

实现线程安全的方式（重要）

ConcurrentHashMap：
- 移除了分段锁：在 JDK 1.8 中，ConcurrentHashMap 不再使用分段锁。相反，它直接使用了一个Node数组来存储键值对，并且通过更细粒度的锁和无锁操作来实现线程安全。
- CAS 操作：在插入和删除节点时，ConcurrentHashMap 使用 CAS（Compare-And-Swap）来确保并发安全。例如，当向一个空桶中插入第一个节点时，ConcurrentHashMap 会使用 CAS 操作直接插入，这样可以避免锁的使用。
- Synchronized 锁：在一些复杂操作（如链表或红黑树的插入或删除）中，ConcurrentHashMap 使用 synchronized 来锁定特定的桶（Node），而不是整个段或整个哈希表。这种方式虽然引入了锁，但锁的粒度非常小，只会锁定冲突的桶，因此可以大大减少锁竞争。
Hashtable：
- 使用全表锁（Synchronized）：Hashtable 通过对每个操作（如 put、get、remove 等）加上 synchronized 来保证线程安全，但它使用的是全表锁，导致每次操作都必须锁住整个对象。这会导致多个线程在访问不同元素时也会被阻塞，增加锁竞争，降低并发性能。
- 性能瓶颈：全表锁机制使得即使线程操作不同的键，仍会被串行化。在高并发场景中，锁的竞争严重影响吞吐量，导致性能大幅下降。