HashMap数据结构-平芜编程栈

一、HashMap 概述

作用：以键值对（key-value）形式存储数据，允许快速插入、查找和删除。
特点：
- 键唯一，值可以重复
- 允许 null 键和 null 值（但只能有一个 null 键）
- 元素无序（不是按照插入顺序排列）

二、内部数据结构

1. 基本结构

HashMap 本质上是一个数组 + 链表 + 红黑树的组合结构。

数组：主结构，存储桶（Node[] table）
链表：解决哈希冲突，当多个键的哈希值相同，放在同一个桶里形成链表
红黑树：当链表长度超过阈值（8），自动转为红黑树，提高查找效率

2. Node 节点结构

每个桶数组元素是一个 Node，Node 定义如下：

static class Node<K,V> implements Map.Entry<K,V> { final int hash; // 哈希值 final K key; // 键 V value; // 值 Node<K,V> next; // 下一个节点（链表指针） }

三、核心原理

1. 存储过程

计算 key 的 hashCode
通过扰动函数和数组长度取模，定位到桶的下标
如果该桶为空，直接插入
如果不为空（有冲突），遍历链表/树，找到相同 key 就覆盖，否则插入链表尾部或树中

2. 取值过程

通过 key 的 hashCode 定位桶
遍历链表/树，找到相同 key 返回 value

3. 扩容机制

默认初始容量 16，负载因子 0.75
当实际元素数量超过容量 × 负载因子时，自动扩容为原来的两倍（重新分散所有节点）
扩容时会重新计算所有节点的桶下标

四、常用方法

put(K key, V value)：插入/更新键值对
get(Object key)：根据键查找值
remove(Object key)：删除指定键
containsKey(Object key)：判断是否包含某个键
containsValue(Object value)：判断是否包含某个值
size()：元素个数
isEmpty()：是否为空
clear()：清空所有元素

五、性能分析

查找/插入/删除：理想情况下 O(1)，但哈希冲突严重时变成 O(n)，红黑树优化后变为 O(log n)
扩容代价：扩容时需要重新分配和迁移所有元素，代价较高

六、线程安全性

HashMap不是线程安全的，多个线程同时操作可能导致数据错乱
如果需要线程安全，可以用Collections.synchronizedMap(new HashMap<>())或ConcurrentHashMap

七、示例代码

Map<String, Integer> map = new HashMap<>(); map.put("apple", 1); map.put("banana", 2); map.put("orange", 3); System.out.println(map.get("banana")); // 输出 2 map.remove("apple"); System.out.println(map.containsKey("apple")); // 输出 false

八、常见面试问题

HashMap 的底层结构？
如何解决哈希冲突？
为什么要有红黑树？什么时候转换？
为什么不是线程安全？怎么保证线程安全？
HashMap 的扩容机制和负载因子作用？

九、HashMap 的哈希算法细节

1. hashCode 与扰动函数

每个 key 都有自己的hashCode()方法，HashMap 先调用 key 的hashCode()，然后再用扰动函数进一步处理，以减少哈希冲突。

典型扰动函数（JDK8）：

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

这个操作将高位和低位混合，提高随机性，减少碰撞。

2. 数组下标定位

下标定位公式：index = (n - 1) & hash，n 为数组长度，& 是位运算，比取模更快。

十、红黑树转化条件

当某个桶中的链表长度超过8（JDK8），并且数组长度大于64时，链表会转化为红黑树，提高查询效率。
如果扩容后链表长度小于 6，会退回链表结构。

十一、扩容时机与过程

1. 扩容时机

当元素个数size超过capacity * loadFactor时触发扩容。
默认初始容量 16，负载因子 0.75，即超过 12 个元素时扩容。

2. 扩容过程

新建一个容量为原来的两倍的数组。
重新分配所有节点到新数组（重新计算哈希下标）。
红黑树节点也会被拆分。

扩容是一个耗时操作，频繁扩容会影响性能，建议初始化时合理设置容量。

十二、常见问题与面试陷阱

1. HashMap 为什么不是线程安全？

多线程同时 put/remove，可能导致数据丢失、死循环（JDK7）、链表丢失等问题。

2. HashMap 的死循环问题（JDK7）

JDK7 的扩容采用头插法，极端情况下可能链表反转成环，导致死循环。JDK8 改为尾插法解决此问题。

3. 为什么建议设置初始容量？

如果预计元素较多，建议设置初始容量，减少扩容次数，提升性能。

4. null 键和 null 值的处理

允许一个 null 键，多个 null 值。
但在实际开发中，建议避免使用 null 键，以免潜在异常。

十三、与其他 Map 的对比

Map 实现类	线程安全	有序性	底层结构	是否允许 null
HashMap	否	无序	数组+链表+红黑树	允许
LinkedHashMap	否	插入顺序	HashMap+双向链表	允许
TreeMap	否	按 key 排序	红黑树	不允许 null key
Hashtable	是	无序	数组+链表	不允许
ConcurrentHashMap	是	无序	分段锁+数组+链表	不允许 null

十四、HashMap 源码简要解析（JDK8）

1. put 方法核心流程

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }

计算 hash
判断是否需要扩容
找到桶下标
遍历链表/树，插入或覆盖

2. get 方法核心流程

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

计算 hash
定位桶
遍历链表/树查找 key

十五、HashMap 使用建议

预计数据量大时，指定初始容量，如new HashMap<>(1000)。
尽量避免使用 null 作为 key。
多线程场景用ConcurrentHashMap替代。
不要在 key 的equals或hashCode方法中依赖可变属性。
不要频繁扩容，合理设置负载因子。

十六、典型应用场景

缓存（如本地缓存、LRU 缓存）
数据索引（如数据库索引、分组统计）
配置映射（如配置项存储、参数映射）

十七、总结

HashMap 是高效、灵活的键值对存储结构，广泛用于缓存、数据索引等场景。掌握其原理有助于编写高效且健壮的 Java 代码。

HashMap 是 Java 集合中最常用、最重要的 Map 实现之一。理解其底层原理、扩容机制、冲突处理、红黑树优化等，有助于写出高效且健壮的代码。面试、工作中常考，建议多结合源码和实际场景理解其设计哲学。

HashMap数据结构