Java HashMap全面解析-平芜编程栈

HashMap 是 Java 集合框架中最常用的键值对（Key-Value）存储容器；同时在安卓开发中，HashMap 是本地数据存储、临时缓存的核心工具。接下来我们来看看 HashMap 的定义、底层结构、核心算法、扩容机制、线程安全问题。

一、HashMap定义

HashMap 是java.util包下的实现类，实现了Map<K,V>接口，基于哈希表实现键值对存储，核心特征：

存储规则：键（Key）唯一，值（Value）可重复；键和值都允许为null；
无序性：不保证插入顺序与遍历顺序一致；
非线程安全：HashMap 为了机制的性能，所有核心操作都没有任何同步或原子性保障，多线程并发时应使用 ConcurrentHashMap 或 synchronizedMap；
性能：增删改查平均时间复杂度为O(1)，哈希冲突严重时退化为O(n)（JDK1.8 后优化为O(logn)）

二、HashMap 底层数据结构

在JDK1.8之后 HashMap 的底层结构经历了关键优化，目的是解决“哈希冲突导致链表过长”的性能问题。

JDK1.7：数组（桶）+ 链表

JDK1.8之前 HashMap 底层是数组和链表结合在一起使用的。HashMap 通过 key 的 hashcode 经过扰动函数（用来优化哈希值的分布，减少碰撞）处理后得到 hash值，然后通过寻址算法判断当前元素存放的位置（前提是数组长度 n 必须是 2 的幂次）。

数组（Hash 桶）：核心存储结构，数组的每个元素是一个链表的头节点，数组下标通过 Key 的哈希值计算得到；
链表：解决哈希冲突（不同 Key 计算出相同下标），冲突的键值对以链表形式挂在同一个数组下标下。
缺点：当链表过长时，查询效率从O(1)退化为O(n)。

JDK1.8：数组（桶）+ 链表 + 红黑树

JDK1.8之后在解决哈希冲突时有了较大的变化，当链表长度大于8且数组总长度大于64时，链表转化为红黑树，查询复杂度从O(n)降至O(logn)。

当红黑树节点数减少到6时，会重新退化为链表。

三、HashMap 的基本使用

HashMap 的 API 简单易用，核心操作包括「增、删、改、查、遍历」，简单示例如下：

import java.util.HashMap; import java.util.Iterator; import java.util.Map; public class HashMapBasicUsage { public static void main(String[] args) { // 创建HashMap：指定键值类型，默认初始容量16，负载因子0.75 HashMap<String, Integer> userScore = new HashMap<>(); // 也可指定初始容量和负载因子：HashMap<String, Integer> map = new HashMap<>(32, 0.75f); // 新增元素（put） userScore.put("张三", 90); userScore.put("李四", 85); userScore.put("王五", 95); userScore.put(null, 0); // 键允许为null userScore.put("赵六", null); // 值允许为null // 修改元素（重复put同一键，覆盖值） userScore.put("李四", 88); // 查询元素 // get(key)：存在返回值，不存在返回null Integer zhangSanScore = userScore.get("张三"); System.out.println("张三的分数：" + zhangSanScore); // 输出：90 // containsKey(key)：判断键是否存在 boolean hasWangWu = userScore.containsKey("王五"); System.out.println("是否包含王五：" + hasWangWu); // 输出：true // containsValue(value)：判断值是否存在（效率低，需遍历） boolean hasScore95 = userScore.containsValue(95); System.out.println("是否有95分：" + hasScore95); // 输出：true // 删除元素 userScore.remove(null); // 删除键为null的元素 userScore.remove("赵六"); // 删除键为赵六的元素 // 遍历HashMap（三种常用方式） System.out.println("\n=== 遍历方式1：entrySet（推荐，效率最高）==="); for (Map.Entry<String, Integer> entry : userScore.entrySet()) { System.out.println("键：" + entry.getKey() + "，值：" + entry.getValue()); } System.out.println("\n=== 遍历方式2：keySet + get（效率低，需二次哈希）==="); for (String key : userScore.keySet()) { System.out.println("键：" + key + "，值：" + userScore.get(key)); } System.out.println("\n=== 遍历方式3：迭代器（支持删除）==="); Iterator<Map.Entry<String, Integer>> iterator = userScore.entrySet().iterator(); while (iterator.hasNext()) { Map.Entry<String, Integer> entry = iterator.next(); if (entry.getValue() >= 90) { System.out.println("高分用户：" + entry.getKey()); // 遍历中删除元素，只能用迭代器的remove（否则抛ConcurrentModificationException） // iterator.remove(); } } // 其他常用方法 System.out.println("\nHashMap大小：" + userScore.size()); // 输出：3 userScore.clear(); // 清空所有元素 System.out.println("清空后是否为空：" + userScore.isEmpty()); // 输出：true } }

四、HashMap的核心算法

哈希算法

我们只看JDK1.8的 hash 算法：

static final int hash(Object key) { int h; // 1. key为null时，哈希值为0；2. 非null时，取hashCode()并与高16位异或 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

将 Key 的 hashCode 高 16 位与低 16 位异或，让高位特征融入低位 —— 因为数组下标计算只用到低位，这样能减少哈希冲突。

数组下标计算

就是之前提到的寻址算法，实现如下：

index = hash & (length - 1);

hash & (length - 1)在length为 2 的幂时，等价于对length的取模运算，但位运算比取模快得多（CPU 原生支持）；
length是 2 的幂保证length - 1的二进制全为 1，这样hash & (length - 1)能充分利用哈希值的低位，分散元素分布，减少冲突。