目录
十 . HashMap,ConcurrentHashMap源码解析
10.1 HashMap 的源码解析:
10.1.1数据结构:
10.1.2哈希算法:
10.1.3解决哈希冲突:
10.1.4扩容机制:
10.1.5如何使用 HashMap:
10.2 HashMap 关注以下几个方面:
10.2.1 初始容量和负载因子:
10.2.2 put() 方法:
10.2.3 get() 方法:
10.2.4 remove() 方法:
10.2.5 扩容机制:
10.2.6 并发安全性:
10.3 ConcurrentHashMap解析:
10.3.1 描述:
10.3.2 ConcurrentHashMap 的一些关键特点和实现原理:
十 . HashMap,ConcurrentHashMap源码解析
HashMap 是 Java 中常用的散列表(哈希表)实现,它提供了快速的插入、查找和删除操作。
10.1 HashMap 的源码解析:
-
10.1.1数据结构:
- HashMap 内部通过数组和链表(或红黑树)实现。数组被称为桶(bucket),每个桶存储一个链表(或红黑树)的头节点。
- 每个元素通过哈希值确定它在数组中的位置,具有相同哈希值的元素以链表(或红黑树)的形式存储在同一个桶中。
-
10.1.2哈希算法:
- 在 HashMap 中,通过 key 的 hashCode() 方法获取键的哈希值。
- 通过哈希值与数组长度取模得到元素在数组中的索引位置。
-
10.1.3解决哈希冲突:
- 当两个不同的 key 对应的哈希值相同时,发生了哈希冲突。
- HashMap 采用开放寻址法(拉链法)来解决哈希冲突,即将冲突的元素以链表(或红黑树)的形式存储在同一个桶中。
-
10.1.4扩容机制:
- 当 HashMap 中的元素数量超过负载因子乘以数组长度时,会触发扩容操作。
- 扩容会创建一个更大的数组,并将所有元素重新插入到新的数组中,这个过程可能比较耗时。
-
10.1.5如何使用 HashMap:
- 使用 put(key, value) 方法将键值对存储到 HashMap 中。
- 使用 get(key) 方法通过键获取对应的值。
- 使用 remove(key) 方法删除指定键的映射关系。
- 使用 containsKey(key) 方法检查 HashMap 是否包含指定的键。
- 迭代 HashMap 可以使用 entrySet() 方法来获取键值对的集合,然后进行遍历操作。
HashMap 在实际开发中被广泛使用,具有高效的插入和查找性能。但需要注意的是,HashMap 不是线程安全的,如果在多线程环境下使用,需要进行适当的同步处理或选择线程安全的替代类(如 ConcurrentHashMap)。
10.2 HashMap 关注以下几个方面:
-
10.2.1 初始容量和负载因子:
- HashMap 的初始容量是指创建 HashMap 时底层数组的大小,默认为 16。
- 负载因子是指 HashMap 在进行扩容操作之前可以达到的填充比例,默认为 0.75。
- 当 HashMap 中元素数量达到负载因子乘以当前容量时,会触发扩容操作。
-
10.2.2 put() 方法:
- 当调用 put(key, value) 方法向 HashMap 中插入一个键值对时,首先会计算 key 的哈希值。
- 然后根据哈希值找到对应的桶(数组索引),如果该桶为空,则直接将键值对插入到桶中。
- 如果桶不为空,则遍历链表(或红黑树):
- 如果链表中已存在相同的 key,则更新对应的值。
- 如果链表中不存在相同的 key,则将新的键值对插入到链表末尾(或红黑树中)。
- 如果链表长度大于阈值(默认为 8),则将链表转换为红黑树来提高查找效率。
- 插入完成后,检查是否需要触发扩容操作。
-
10.2.3 get() 方法:
- 当调用 get(key) 方法获取指定 key 对应的值时,首先计算 key 的哈希值。
- 根据哈希值找到对应的桶,然后遍历链表(或红黑树):
- 如果链表中存在相同的 key,则返回对应的值。
- 如果链表中不存在相同的 key,则返回 null。
-
10.2.4 remove() 方法:
- 当调用 remove(key) 方法删除指定 key 对应的键值对时,首先计算 key 的哈希值。
- 根据哈希值找到对应的桶,然后遍历链表(或红黑树):
- 如果链表中存在相同的 key,则将该节点从链表(或红黑树)中移除。
- 如果链表中不存在相同的 key,则不执行任何操作。
-
10.2.5 扩容机制:
- 当 HashMap 中元素数量达到负载因子乘以当前容量时,会触发扩容操作。
- 扩容会创建一个新的数组,并将所有元素重新插入到新的数组中。
- 扩容时需要重新计算每个元素在新数组中的位置并重新分配桶。
-
10.2.6 并发安全性:
- HashMap 不是线程安全的,如果在多线程环境下使用,需要进行适当的同步处理或选择线程安全的替代类,如 ConcurrentHashMap。
10.3 ConcurrentHashMap解析:
10.3.1 描述:
ConcurrentHashMap 是 JDK 提供的线程安全的哈希表实现,它是在多线程环境下使用的一种高效的并发容器。相对于传统的 HashMap,ConcurrentHashMap 在并发场景下提供了更好的性能和线程安全性。