【Java】HashMap的简单教程

HashMap 是 Java 中最常用的数据结构之一，属于 java.util 包，主要用于以键值对（key-value）形式存储数据。

基本用法

1.创建

HashMap 使用泛型，存储键值对。

import java.util.HashMap;

HashMap<KeyType, ValueType> map = new HashMap<>();

默认构造方法

HashMap<String, Integer> map = new HashMap<>();

指定初始容量

指定初始容量可以避免频繁扩容。

HashMap<String, Integer> map = new HashMap<>(32);

指定初始容量和负载因子

加载因子默认是0.75，当元素个数达到 容量 * 负载因子 时，HashMap 会触发扩容

意思是：默认数组长度16，当元素个数超过 16 x 0.75 = 12时，就会成倍扩容 16 x 2 = 32

HashMap<String, Integer> map = new HashMap<>(32, 0.75f);

通过另一个Map构造

HashMap<String, Integer> map = new HashMap<>(anotherMap);

2.常用方法

添加键值对

插入一个键值对，一个键值对一般称为一个Entity（实体）

如果键已存在，则更新其对应的值

HashMap<String, String> hm = new HashMap<>();
hm.put("王心妍", "是林逸来到松山市见到的第一个女孩");
hm.put("黄小桃", "是林逸在天阶岛遇到的第二个的青云阁女孩");
hm.put("王心妍", "林逸的后宫团中大老婆的有力竞争者之一");

获取值

根据键获取值。如果键不存在，则返回 null。

HashMap<String, String> hm = new HashMap<>();
        hm.put("王心妍", "是林逸来到松山市见到的第一个女孩");
        hm.put("黄小桃", "是林逸在天阶岛遇到的第二个的青云阁女孩");
        hm.put("王心妍", "林逸的后宫团中大老婆的有力竞争者之一");
        System.out.println(hm.get("王心妍"));
        System.out.println(hm.get("唐韵"));

检查键是否存在

判断是否包含指定键。

        HashMap<String, String> hm = new HashMap<>();
        hm.put("王心妍", "是林逸来到松山市见到的第一个女孩");
        hm.put("黄小桃", "是林逸在天阶岛遇到的第二个的青云阁女孩");
        hm.put("王心妍", "林逸的后宫团中大老婆的有力竞争者之一");
        System.out.println(hm.containsKey("黄小桃"));
        System.out.println(hm.containsValue("与林逸能打出合击技：狂火合击八卦掌，在金丹初期层面合力击杀过元婴老怪"));

删除键值对

删除指定键对应的键值对

        HashMap<String, String> hm = new HashMap<>();
        hm.put("王心妍", "是林逸来到松山市见到的第一个女孩");
        hm.put("黄小桃", "是林逸在天阶岛遇到的第二个的青云阁女孩");
        hm.put("王心妍", "林逸的后宫团中大老婆的有力竞争者之一");
        System.out.println(hm);
        hm.remove("王心妍");
        System.out.println(hm);

获取大小

        HashMap<String, String> hm = new HashMap<>();
        hm.put("王心妍", "是林逸来到松山市见到的第一个女孩");
        hm.put("黄小桃", "是林逸在天阶岛遇到的第二个的青云阁女孩");
        hm.put("王心妍", "林逸的后宫团中大老婆的有力竞争者之一");
        System.out.println(hm.size());

清空所有数据

清空 HashMap 中的所有键值对。

        HashMap<String, String> hm = new HashMap<>();
        hm.put("王心妍", "是林逸来到松山市见到的第一个女孩");
        hm.put("黄小桃", "是林逸在天阶岛遇到的第二个的青云阁女孩");
        hm.put("王心妍", "林逸的后宫团中大老婆的有力竞争者之一");
        System.out.println(hm.size());
        hm.clear();
        System.out.println(hm.size());

获取所有键

        HashMap<String, String> hm = new HashMap<>();
        hm.put("王心妍", "是林逸来到松山市见到的第一个女孩");
        hm.put("黄小桃", "是林逸在天阶岛遇到的第二个的青云阁女孩");
        hm.put("王心妍", "林逸的后宫团中大老婆的有力竞争者之一");
        System.out.println(hm.keySet());

遍历

        HashMap<String, String> hm = new HashMap<>();
        hm.put("王心妍", "是林逸来到松山市见到的第一个女孩");
        hm.put("黄小桃", "是林逸在天阶岛遇到的第二个的青云阁女孩");
        hm.put("王心妍", "是林逸的后宫团中大老婆的有力竞争者之一");
        Set<String> keys = hm.keySet();
        Iterator<String> iterator = keys.iterator();
        while (iterator.hasNext()){
            String item = iterator.next();
            System.out.println(item + hm.get(item));
        }

底层实现

在Java8，HashMap 的底层数据结构是一个数组 + 链表 + 红黑树的组合，主要目的是实现快速的存储和查找。

补充知识点可以我另一篇博客：【JavaSE】基础知识复习（四）-CSDN博客

HashMap 的核心组成部分

数组（table）：
- HashMap 的核心是一个数组，称为 桶数组，用于存储数据。
- 每个数组元素称为一个桶，存储链表或红黑树的头结点。
链表：
- 当多个键的哈希值冲突（计算出相同的索引）时，会将这些键值对存储在一个链表中。
- 链表长度过长会降低性能（查找时间复杂度为 O(n)）。
红黑树：
- 当链表长度超过某个阈值（默认是 8）时，链表会转化为红黑树。
- 红黑树的查找时间复杂度为 O(log n)，大幅提高了性能。

HashMap 的核心操作流程

1. 插入数据

步骤：
1. 根据 key 的 hashCode() 计算出哈希值。
2. 通过 (哈希值 % 数组长度) 计算出数组索引。
3. 如果桶（数组位置）为空，则直接插入键值对。
4. 如果桶中有数据（哈希冲突），将新数据追加到链表末尾。如果链表长度超过阈值，则转换为红黑树。

int hash = key.hashCode(); // 计算哈希值
int index = hash % table.length; // 计算数组索引
if (table[index] == null) {
    table[index] = new Node<>(key, value);
} else {
    // 处理哈希冲突，追加到链表或转化为红黑树
}

2. 查询数据

步骤：
1. 根据 key 的 hashCode() 计算哈希值。
2. 通过 (哈希值 % 数组长度) 定位到具体的桶。
3. 遍历桶中的链表或红黑树，查找与 key 匹配的节点。
4. 返回节点的值。

3. 删除数据

步骤：
1. 根据 key 定位到对应桶。
2. 遍历链表或红黑树，找到匹配的节点并删除。

扩容机制

1. 扩容条件

当 HashMap 中的元素个数超过 容量 * 负载因子 时，触发扩容。

默认容量：16。
默认负载因子：0.75。
默认扩容阈值：16 * 0.75 = 12。

2. 扩容过程

数组容量变为原来的 2 倍。
重新计算每个键值对的哈希值，移动到新的桶中。

扩容代价较高，因为需要重新计算每个键的哈希值，并将其重新分配到新数组中。

哈希冲突

1. 哈希冲突的原因

不同的键可能会计算出相同的哈希值，导致它们被分配到同一个桶中。

小概率时间，比如下图，就有8亿多个对象的哈希值出现相同现象

2. 解决方法

链表法：冲突的键值对存储在链表中。
红黑树法：当冲突较多时，链表转换为红黑树，提高查找效率。

优缺点

优点

快速查找：
- 理论时间复杂度接近 O(1)。虽然HashMap没有数组那种的直接索引，但是通过计算键的hashCode()，所以理论上查询时间复杂度勉强能赶上数组
灵活存储：
- 支持键值对存储，可以存储任意类型。
高效扩容：
- 动态扩容机制提高性能。

缺点

非线程安全：
- HashMap 不是线程安全的，多个线程同时操作可能导致数据不一致。
- 解决方案：使用 ConcurrentHashMap 或 Collections.synchronizedMap。
扩容代价高：
- 扩容会导致性能短暂下降，适合频繁读取但写入次数较少的场景。