HashMap在大厂面试经常问到，比如：数据结构、哈希函数…等原理机制，下面我就全面来详解HashMap@mikechen
HashMap
HashMap 是 Java 集合框架中的一个重要集合，它是一个基于哈希表的 Map 接口实现，用于存储键值对。
整体实现，如下图所示：
HashMap常用于：需要快速查找、插入、或删除…等场景，比如：缓存、索引、数据表…等。
HashMap实现原理
HashMap 的核心实现原理，在于利用哈希表(hash)，来存储键值(key-value)对。
HashMap它通过对键调用 hashCode() 方法计算哈希值，然后，通过哈希值将键值对存储在哈希表的不同位置。
整体实现，如下图所示：
HashMap 的数据结构，由数组、和链表（或：红黑树）组成。
数组
HashMap 的底层是一个 Node<K, V>[] table 数组，如下所示：
static class Node<K, V> implements Map.Entry<K, V> {
final int hash; // 哈希值，用于快速确定元素的位置
final K key; // 键
V value; // 值
Node<K, V> next; // 链表的下一个节点（用于处理哈希冲突）
Node 类
每个 Node 包含一个键值对，及其对应的哈希值、和链表的下一个节点引用，结构如下：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
// ...
}
参数说明：
hash：存储键的哈希值，用于快速定位键在HashMap中的位置；key：存储键的实际值；value：存储与键关联的值；next：用于处理哈希冲突，如果多个键通过哈希函数映射到同一个桶，这些键值对将形成一个链表，这个链表通过next引用连接在一起。
每个元素（桶）要么为空，要么是一个链表的头结点、或红黑树的根节点。
哈希冲突处理
当两个不同的键通过，哈希函数映射到同一个数组索引时，就会发生哈希冲突。
HashMap 使用链表、或红黑树来处理这种冲突：
链表
如果冲突发生，新的 Node 会被添加到链表的头部（或者在尾部），通过 next 指向下一个节点。
红黑树
在 Java 8 中，当链表长度超过一定阈值（默认是 8）时，链表会转换为红黑树，以提高查找性能。
在这种情况下，Node 会被替换为 TreeNode，TreeNode 是 Node 的一个子类，用于存储树结构。
HashMap哈希函数
HashMap哈希函数，是非常重要的HashMap实现。
HashMap 的哈希函数，通过以下步骤实现：
第一步：计算哈希值
首先，HashMap 使用键的 hashCode() 方法，获取原始哈希值。
第二步：扰动函数（hash 函数）
为了减少哈希冲突，HashMap 对原始哈希值进行扰动操作，将高位的影响混合到低位。
假设我们有一个键 key，它的 hashCode() 方法返回一个整数 h。
在 HashMap 中，这个整数 h 被称为原始哈希值，为了减少哈希冲突，HashMap 对这个原始哈希值进行了扰动处理，使得最终的哈希值更均匀地分布在数组中。
实现如下：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
参数说明：
h = key.hashCode()
调用键的 hashCode() 方法，返回 key 的原始哈希值 h。
h >>> 16
将 h 右移 16 位，用 0 填充左边的空位，这个操作将哈希值的高 16 位移到低 16 位的位置。
h ^ (h >>> 16)
将原始哈希值 h 、与其右移 16 位后的值进行按位异或（XOR）操作。
通过这种方式，哈希值的高位和低位信息混合在一起，生成一个新的哈希值。
简单地使用 hashCode() 的结果，可能会导致哈希冲突集中在数组的某些位置，特别是在数组大小是 2 的幂次时。
如果某些 hashCode() 的高位相同，低位不同，它们会集中到数组的某些特定位置。
采用这种方式，使得最终生成的哈希值更加分散，从而减少哈希冲突，提高 HashMap 的性能。
HashMap线程安全
在多线程环境中，多个线程同时访问和修改 HashMap，可能会导致数据不一致、死循环、数据丢失……..等问题。
比如：在高并发场景下，如果多个线程同时进行扩容操作，HashMap 可能会因为链表的自循环而导致死循环，从而导致 CPU 利用率飙升，程序卡死。
在并发较低的场景下，可以使用 Collections.synchronizedMap，虽然性能较低，但实现简单。
如下所示：
Map<String, Integer> map = Collections.synchronizedMap(new HashMap<>());
在高并发场景下，ConcurrentHashMap 是首选，它提供了更高的并发性能，确保线程安全的同时，最小化了性能损失。
如下所示：
import java.util.concurrent.ConcurrentHashMap;
public class ConcurrentHashMapConcurrencyExample {
public static void main(String[] args) {
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
// 启动多个线程进行并发写入
for (int i = 0; i < 10; i++) {
final int threadIndex = i;
new Thread(() -> {
for (int j = 0; j < 100; j++) {
map.put("key-" + threadIndex + "-" + j, j);
}
}).start();
}
// 启动多个线程进行并发读取
for (int i = 0; i < 10; i++) {
new Thread(() -> {
for (int j = 0; j < 100; j++) {
Integer value = map.get("key-" + i + "-" + j);
System.out.println(Thread.currentThread().getName() + " - Read: key-" + i + "-" + j + " = " + value);
}
}).start();
}
}
}
ConcurrentHashMap 采用了更细粒度的锁机制，比如：ConcurrentHashMap 使用分段锁(1.7)，Java 8 之后使用 CAS 操作，从而提高并发性。
所以，HashMap 本身并不是线程安全的，在多线程环境中需要特别小心。
为了保证线程安全，可以使用： ConcurrentHashMap、Collections.synchronizedMap 、或者手动加锁的方式。
ConcurrentHashMap 是高并发场景下的最佳选择，它通过更精细的锁机制提供了高效的并发访问能力。
mikechen睿哥
10年+大厂架构经验，资深技术专家，就职于阿里巴巴、淘宝、百度等一线互联网大厂。