前言

在 Java 中，Map 是一种非常重要的数据结构，用于存储 键值对（key-value），它提供了根据 key 快速查找对应 value 的能力。常见的 Map 实现类有 HashMap、Hashtable、TreeMap 等。与 List、Set 等集合不同，Map 不关注元素的顺序，而是关注 通过 key 高效访问数据。

在日常开发和面试中，HashMap 几乎是不可回避的核心考点。本篇文章将从模拟一次HashMap中put和get操作来引入：HashMap1.7和1.8版本不同的底层数据结构；扩容机制；线程安全

HashMap基础与原理

HashMap内部结构

在JDK1.7之前，HashMap的底层是数组+链表。

HashMap通过哈希算法将元素的键（key）映射到数组中的槽位（Bucket）。如果多个键映射到同一个槽位，会以链表的形式存储的同一给槽位上

这就是1.7版本的映射流程
这带来的后果是：

当一个索引上的链表很长时，效率就特别低了。因为链表的查询效率时O（n）

于是1.8版本时候就进行了改进。
当某个桶的链表长度>=8且哈希表数组长度>=64时自动转换为红黑树

结果就是：时间复杂度降低成了O(log n);

put/get流程

get
作用：传入我们需要获取的节点key，返回value

public V get(Object key) {  
Node<K,V> e;  
return (e = getNode(hash(key), key)) == null ? null : e.value;
}

---

put：用于向HashMap中添加键值对，具体调用流程如下

1. 根据要添加的键的哈希码计算在数组中的位置
2. 检查给位置是否为空
   若为空，在该位置创建一个新的Node对象来存储键值对。将要添加的键值对作为该Node的键和值
3. 如果改位置已经存了其他键值对，检查该位置的第一个键值对的哈希码和键是否与要添加的键值对相同
   若相同，直接替换掉旧值，完成更新
4. 如果不同，则需遍历链表或红黑树来查找是否有相同的键
   如果是链表，从表头逐个比较键的哈希码和equal()方法，直到找到或达到链表末尾
   如果是红黑树，在红黑树中使用哈希码和equal()方法进行查找。添加方法如上
5. 检查链表长度是否达到阈值（8）
   如果链表长度超过阈值，且数组长度超过64，自动将链表转化为红黑树
6. 检查负载因子是否超过阈值（0.75）
   如果键值对的数量与数组的长度的比值>阈值，则触发扩容
7. 扩容操作：

创建一个新的两倍大小的数组
遍历就数组中的每一个键值对，将遍历到的结果重新分配到新数组的位置（要么原位置，要么 原位置 + oldCap），无需重新计算hash（这一点在下面会具体讲解）

8. 完成添加操作

总结

put流程需要注意的点一共有两种：
链表切换成红黑树以及扩容的触发时机，两者时机要进行区分：一个是链表长度，一个是数组长度。以及扩容逻辑与具体操作

上面我们了解了put/get的具体流程，接下来讲述的是上述流程的一些具体细节

key的要求

我们在上面了解了get操作流程，通过key值定位，找到value。那么有哪些类型适合作为key呢

一般用string作为key，因为String对象是不可变的，一旦创建旧不能被修改，这确保了key的稳定性
key可以为null
当使用hash（）方法时且key为null。直接令key的哈希值为0，不走key.hashCode()方法
hashmap虽然支持key和value为null，但null作为key只能有一个，null作为value可以有多个。

总结：key可以为null，但是只能由一个；一般用String类型作为key，因为String是不可变类型

扩容逻辑

回到put流程扩容操作的问题，在这里，我们具体聊聊触发扩容有哪些因素

hashMap默认的负载因子是0.75，即如果hashmap中的元素个数超过了总容量75%（负载因子太低会导致大量的空桶浪费空间，负载因子太高会导致大量的碰撞，降低性能。0.75 的负载因子在这两个因素之间取得了良好的平衡。），则会触发扩容，扩容分为两个步骤：

1. 对哈希表长度的扩展（2倍）
2. 将旧哈希表中的数据放到新的哈希表中

因为扩容是2倍扩容，所以元素的位置不是在原位就是在原位再次移动2次幂的位置
例如：将16位扩容至32位时

因此，我们在扩充HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”

HashMap在多线程下的问题

1.7中的HashMap使用头插法插入元素，在多线程环境下，扩容的时候可能导致环形链表，形成死循环。所以1.8使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表问题。
但是：多线程同时put操作，如果计算出来的索引位置相同（又叫哈希冲突），会造成前一个key被后一个key覆盖，从而导致元素丢失

解决方式：

• 多线程环境可以使用Collections.synchronizedMap同步加锁的方式，还可以使用Hashtable，但是同步的方式显然性能不达标，而ConurrentHashMap更适合高并发场景使用。
• ConcurrentHashmap在JDK1.7和1.8的版本改动比较大，1.7使用Segment+HashEntry分段锁的方式实现，1.8则抛弃了Segment，改为使用CAS+synchronized+Node实现，同样也加入了红黑树，避免链表过长导致性能的问题。

HashMap的优缺点

优点：

• 快速查找： 平均时间复杂度为O(1)。
• 灵活： 可以存储不同类型的对象，允许null键和值。

缺点：

• 非线程安全： 多线程情况下需要手动同步。
• 不保证顺序： 插入顺序和遍历顺序可能不同。