0Pricing
Java Academy · 课时

HashMap 的工作原理

桶、哈希与冲突

HashMap 的工作原理 是 CoddyKit 上的免费 Java Academy 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Java Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Java Academy 课程共包含 4 节课。

HashMap 存储什么

HashMap 存储键值对，并为查找、插入和删除提供平均 O(1) 的时间复杂度。

它的内部维护着一个名为数组的 table。数组中的每个位置称为一个桶。

  • 键决定条目落入哪个桶。
  • 通过键进行查找时，返回的就是值。
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> ages = new HashMap<>();
        ages.put("Alice", 30);
        ages.put("Bob", 25);
        System.out.println(ages.get("Alice"));
    }
}

对键进行哈希

调用 put(key, value) 时，映射会调用 key.hashCode() 来获取一个 int。

然后，HashMap 会通过内部函数扩散这些位，使得即使哈希码质量较差，也能将条目分布到各个桶中。

  • 最终的数值会通过 hash & (table.length - 1) 缩减为桶索引。
  • 表的长度始终是 2 的幂，因此这个掩码可以正常工作。
public class Main {
    public static void main(String[] args) {
        String key = "Alice";
        int h = key.hashCode();
        int spread = h ^ (h >>> 16);
        int index = spread & (16 - 1);
        System.out.println("hashCode: " + h);
        System.out.println("bucket index: " + index);
    }
}

桶的实际运作

每个桶可以容纳多个条目。当两个键映射到同一个桶时，就发生了冲突。

冲突是正常且意料之中的情况。HashMap 会将桶中的条目链接起来，以此处理冲突。

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, String> m = new HashMap<>();
        for (int i = 0; i < 5; i++) {
            m.put(i, "v" + i);
        }
        System.out.println(m.size() + " entries stored");
    }
}

冲突与链接

在 Java 8 之前，所有发生冲突的条目都存放在桶内的单向链表中。

查找时会遍历链表，并调用 equals()，直到找到匹配的键。

  • 冲突较少时，实际性能仍接近 O(1)。
  • 同一个桶中冲突较多时，该桶的性能会逐渐下降到 O(n)。
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("FB", 1);
        m.put("Ea", 2);
        System.out.println("FB hash: " + "FB".hashCode());
        System.out.println("Ea hash: " + "Ea".hashCode());
        System.out.println(m.get("FB") + ", " + m.get("Ea"));
    }
}

为什么 FB 和 Ea 会冲突

字符串 "FB" 和 "Ea" 在 Java 中具有相同的 hashCode()。这是一个经典的冲突示例。

即使哈希码相同，映射仍会将它们分开存储，因为 equals() 会在桶内区分它们。

public class Main {
    public static void main(String[] args) {
        System.out.println("FB".hashCode() == "Ea".hashCode());
        System.out.println("FB".equals("Ea"));
    }
}

负载因子

负载因子控制表在扩容前可以达到的满载程度。默认值为 0.75。

  • 容量为 16、负载因子为 0.75 时，达到 12 个条目就会触发扩容。
  • 较低的负载因子会浪费内存，但能减少冲突。
  • 较高的负载因子可以节省内存，但会增加冲突。
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(16, 0.75f);
        for (int i = 0; i < 12; i++) m.put(i, i);
        System.out.println("Stored " + m.size() + " entries");
    }
}

扩容表

当条目数量超过 capacity * loadFactor 时，表的大小会翻倍。

每个已有条目都会被重新哈希到新的、更大的表中。这是一项开销较大的操作，因此对于大型映射，提前设置容量很重要。

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        // Pre-size to avoid repeated resizes
        Map<Integer, Integer> m = new HashMap<>(1024);
        for (int i = 0; i < 800; i++) m.put(i, i * 2);
        System.out.println("size = " + m.size());
    }
}

预设容量以提升性能

如果您大致知道要存储多少个条目，请设置初始容量，以避免反复扩容。

经验法则：初始容量 = expectedSize / 0.75 + 1。

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        int expected = 1000;
        int capacity = (int) (expected / 0.75) + 1;
        Map<Integer, String> m = new HashMap<>(capacity);
        System.out.println("Initial capacity hint: " + capacity);
        m.put(1, "ok");
        System.out.println(m.get(1));
    }
}

空键和空值

HashMap 允许一个空键和多个空值。

  • 空键始终会进入 0 号桶（其哈希值按 0 处理）。
  • 使用 getOrDefault，可以避免无法区分键不存在和键对应空值的情况。
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, String> m = new HashMap<>();
        m.put(null, "nullKeyValue");
        m.put("a", null);
        System.out.println(m.get(null));
        System.out.println(m.getOrDefault("missing", "default"));
    }
}

不保证迭代顺序

HashMap不保证迭代顺序。顺序取决于哈希码和桶的布局。

如果需要可预测的顺序，请使用 LinkedHashMap（插入顺序）或 TreeMap（排序顺序）。

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("one", 1);
        m.put("two", 2);
        m.put("three", 3);
        for (Map.Entry<String, Integer> e : m.entrySet()) {
            System.out.println(e.getKey() + "=" + e.getValue());
        }
    }
}

get() 路径概览

一次查找遵循以下步骤：

  • 计算 hashCode() 并扩散各个位。
  • 使用掩码找到桶索引。
  • 遍历桶，并使用 equals() 比较键。
  • 返回匹配的值，否则返回空值。

良好的 hashCode 加上正确的 equals 可以让每一步都保持快速。

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> stock = new HashMap<>();
        stock.put("apple", 50);
        stock.put("pear", 20);
        String key = "apple";
        Integer qty = stock.get(key);
        System.out.println(key + " -> " + qty);
    }
}

快速检查

请测试您对 HashMap 如何找到桶的理解。

回顾

您已了解 HashMap 的底层工作原理：

  • 键会经过哈希处理并映射到桶。
  • 冲突通过在桶中链接条目来处理。
  • 负载因子（0.75）会触发容量翻倍和重新哈希。
  • 预先设置容量可以避免代价高昂的扩容，而且不保证迭代顺序。

接下来，您将看到为什么仅有 hashCode、没有正确的 equals 还不够。

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>(64);
        m.put("recap", 1);
        System.out.println("HashMap basics complete: " + m.get("recap"));
    }
}

常见问题解答

「HashMap 的工作原理」课时是免费的吗？

是的 — 「HashMap 的工作原理」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Java Academy 课程的其余内容，请升级到 CoddyKit PRO。 Java Academy 课程共包含 4 节课。

「HashMap 的工作原理」这节课中我会学到什么？

桶、哈希与冲突 你通过在浏览器中直接运行的动手代码来练习 Java Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Java Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Java Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。

「HashMap 的工作原理」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Java Academy 课中编写并运行代码吗？

能。每节 Java Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

  1. HashMap 的工作原理
  2. equals/hashCode 契约
  3. 实现 hashCode
  4. 树化与性能
← 返回 Java Academy