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

java hashmap详解篇

ds 2025/7/5 14:18:04

java hashmap详解篇

介绍

HashMap 是 Java 中基于哈希表实现的、用于高效存储键值对（Key-Value）的非线程安全集合类，通过计算键的哈希值快速定位数据，平均时间复杂度可达 O(1)。

用法用途

0、底层存储结构

       ┌───┬───┬───┬───┬───┐  ← 数组（桶数组）
索引： 0   | 1 | 2 | 3 | 4 |└───┴─┬─┴───┴─┬─┴───┘↓       ↓┌───┐   ┌───┐│ A │   │ B │  ← 链表头节点（JDK1.7/1.8短链表）└─┬─┘   └─┬─┘↓       ↓ ┌───┐   ┌───┐│ C │   │ X │└─┬─┘   └─┬─┘↓       ↓ ┌───┐     ││ D │     ├───────────┐└───┘     ↓           ↓┌─────┐     ┌─────┐│ 红  │     │ 黑  │  ← JDK1.8+ 红黑树│ 树  │     │ 树  │└─────┘     └─────┘

hashmap的底层数据结构由数组+链表/红黑树组成，如上。数组为HashMap的主干结构，长度总是 2 的幂（16/32/64…），每个数组元素称为一个 桶（Bucket），初始默认容量 16，负载因子 0.75（扩容阈值 = 容量 × 负载因子）。链表是用于解决hash冲突的，当不同的key通过哈希函数及数组长度根据相关位算法或者取模计算后得到相同的数组索引（即“桶”的位置），即发生了哈希冲突，数据就会放到相同链表中存储。

不同的哈希值（hash 值）也可能会被分配到同一个桶中。这并不是因为哈希值相同，而是因为在将哈希值映射到数组索引时，使用了取模运算（或等价的位运算），从而导致不同哈希值映射到相同的索引位置。所以不同的hash值是可能发生hash冲突的。

1、key的hash值如何计算

0、介绍

HashMap 的 key 通常用不可变类，为了保持其hash稳定。

因为hash值的默认实现是返回对象内存地址的整数表示（但这并非绝对，取决于JVM实现）

public class Object {public native int hashCode(); // JVM 实现
}

由于不同对象在内存地址中是不一样的，所以为了保证内容相同的对象的hash值一致。可以进行重写**equals 和 hashCode**方法，

1、字符串String作为Key时

对于两个内容相同的字符串（即使它们是不同的对象），hashCode() 会返回相同的值。这是设计上的要求，以便在哈希表（如 HashMap）中能正确工作。

String a1 = new String("a"); // 创建一个新的String对象，内容为"a"
String a2 = new String("a"); // 创建另一个新的String对象，内容为"a"System.out.println(a1.hashCode()); // 输出 97
System.out.println(a2.hashCode()); // 输出 97

因为 String 类的 hashCode() 方法进行了重写，它是基于字符串内容计算的。字符串 "a" 的Unicode值是97，所以两者都返回97。

a1 和 a2 是两个独立的对象（通过 new 创建），它们在堆内存中占用不同的地址。哈希码相同不表示内存地址相同。

//使用 System.identityHashCode()：这个方法返回 Object 类的默认 hashCode()（通常基于内存地址）。
System.out.println(System.identityHashCode(a1)); // 输出一个值（如 1452126962）
System.out.println(System.identityHashCode(a2)); // 输出另一个值（如 363771819）

如果 String 的哈希码基于内存地址，那么内容相同的字符串在哈希表（如 HashMap）中会被视为不同的键，导致逻辑错误。所以字符串String类的hashCode() 方法是基于字符串内容计算的。

2、允许null作为key

hashmap允许null作为Key，并且只能有一个null key。null key的哈希值固定为0，存储在数组索引0的位置。

可以有多个null value。

2、get和put的执行流程

get方法：计算 key 的哈希值，根据哈希值和数组长度计算数组索引 i，检查数组索引 i处的正好是对应的Key(equals为true)，直接返回，如果是链表节点，遍历链表查找key相同的节点（equals为true）,如果第一个节点是树节点，调用红黑树的查找方法。

找到则返回对应的value，否则返回null。

put方法：计算key的哈希值，根据哈希值和数组长度计算数组索引i，检查数组索引 i 处，如果为空，直接新建节点放入，如果不为空（发生哈希冲突），如果第一个节点的 key 相同（equals 为 true），则覆盖其 value。如果是链表节点的话，遍历链表，找到 key 相同的节点则覆盖 value，没找到的话在链表的尾部插入新节点，插入后检查链表长度是否 >= 8，如果是则尝试将链表转为红黑树（需满足数组长度 >= 64）。如果是树节点的话，调用红黑树的插入方法。

插入成功后超过threshold(容量*负载因子)，如果超过则进行扩容。

3、扩容和链表/红黑树转化分析

当hashmap中的数据逐渐增多少，会触发扩容、链表转化位红黑树的动作。

HashMap的主干结构数组，长度总是 2 的幂（16/32/64…），每个数组元素称为一个 桶（Bucket），初始默认容量 16，负载因子 0.75（扩容阈值 = 容量 × 负载因子），当达到扩容阈值，创建一个新的数组，扩容的新数组是原数组的两倍，这样可以使元素在新数组中分布更均匀，减少哈希冲突。

在JDK 1.8中，HashMap引入红黑树是对哈希冲突极端场景的性能优化，当大量Key的哈希值冲突，链表查询时间复杂度从O(1)退化为O(n)，红黑树的查询效率是O(log n)，而且红黑树通过旋转+变色（最长路径≤2倍最短路径）保证树高近似log₂n。1亿次查询，链表需1亿次遍历 → 红黑树仅需27次（log₂(1e8)≈26.57）。

触发转化为红黑树需要同时满足以下两个条件：

（1）单个哈希桶（Bucket）中的链表节点数 ≥ 8时

（2）HashMap的底层数组长度≥ 64时

为什么既要数组长度大于等于64又要链表长度大于等于8呢？因为需要避免数组小的表树化，数组较小时，扩容比树化更能有效解决冲突（扩容成本低于树化）。而且基于内存空间考虑，红黑树的空间开销远大于链表。

4、hashmap的线程安全问题分析

多线程并发操作导致内部数据结构（数组+链表/红黑树）被破坏，数据错乱了，具体由以下原因造成：

（1）JDK1.7版本死循环问题（环形链表）

多线程同时执行put()并触发扩容（resize）使链表迁移(transfer)，执行迁移（transfer）方法使用了头插法，但是没有用同步机制，导致不同线程对链表节点的 next 指针进行并发修改，最终可能使某个桶中的链表形成一个环形结构，后续对该桶进行 get 或 put 操作遍历链表时，就会陷入死循环，导致 CPU 使用率飙升。

在JDK1.8后将头插法换成尾插法，即将链表插入到新链表的尾部，保持住了节点的原始顺序，避免了环形依赖问题。

（2）多线程同时put()且key的hash值冲突时，在相同桶索引位置插入，导致数据被覆盖

并发 put 可能导致数据丢失、覆盖问题

（3）多线程put()触发扩容resize()，扩容时节点转移过程中出现链表断裂，部分节点丢失

线程A扩容未完成时，线程B执行put() → 触发新一轮扩容 → 节点引用关系混乱，部分数据永久丢失

5、hashmap的遍历方式效率分析

KeySet 遍历： map.keySet().forEach() 或 for (K key : map.keySet())
Values 遍历： map.values().forEach() 或 for (V value : map.values())
EntrySet 遍历： map.entrySet().forEach() 或 for (Map.Entry<K, V> entry : map.entrySet())
Iterator 遍历： 通过 keySet().iterator(), values().iterator(), entrySet().iterator()
Java 8+ forEach： map.forEach((k, v) -> { ... })
效率： EntrySet 遍历效率最高，因为它直接访问键值对，避免了通过 key 再去 get value 的额外开销（keySet 或 values 遍历需要额外的 get 操作）。forEach 方法内部通常也优化为使用 EntrySet。