Rust HashMap: 如何高效地查找和插入数据

如何在 Rust 的 HashMap 中高效地查找和插入数据：深入底层

你是否曾经在编写 Rust 代码时想过：“我该如何同时检查 HashMap 中是否存在某个键，如果不存在则插入一个新值？”这个问题困扰着 Stack Overflow 上的成千上万名开发者。这并非没有道理：一个天真的解决方案可能会扼杀你应用程序的性能。今天，我们不仅会给出答案——我们还将深入 Rust HashMap 的内部，看看它是如何构建的。你将了解为什么单独使用 get 和 insert 是一条痛苦之路，以及如何正确使用 entry API。

本文适合那些已经熟悉 Rust 基础，但希望更深入理解集合底层工作原理的读者。我们开始吧！

问题：两次调用，双倍工作量

设想一个典型任务：你有一个 HashMap，需要统计文本中单词出现的次数。天真的方法如下：

use std::collections::HashMap;\n\nfn count_words_naive(words: &[&str]) -> HashMap<String, u32> {\n    let mut map = HashMap::new();\n    \n    for word in words {\n        if map.contains_key(*word) {\n            let count = map.get(*word).unwrap();\n            map.insert(word.to_string(), count + 1);\n        } else {\n            map.insert(word.to_string(), 1);\n        }\n    }\n    \n    map\n}\n

这有什么问题？对于每个单词，我们访问了 HashMap 两次：先是 contains_key，然后是 get，接着还有 insert。每次调用都涉及 计算哈希、在桶中查找 和 比较键。对于短文本来说这并不明显，但对于数百万条记录来说，这就是一场灾难。

底层原理：Rust 中 HashMap 的结构

为了理解为什么这很糟糕，让我们来剖析 Rust 中 HashMap 的工作原理。其核心是 开放寻址哈希表（Robin Hood hashing）。以下是关键点：

\n
• 哈希： 键通过哈希函数（默认是 SipHash-2-4）转换为哈希码。
\n
• 桶： 哈希码决定了桶数组中的索引。在 Rust 中，每个桶是一个槽，可以是空的、被占用的或已删除的。
\n
• 冲突： 当两个不同的键落入同一个桶时，Robin Hood hashing 会尝试从更“富有”的邻居那里“偷”一个位置，以平衡查找距离。
\n
• 重新调整大小： 当表被填满时（负载因子约 0.9），它会扩大 2 倍，并且所有元素都会被重新哈希。
\n

现在想象一下：每次调用 get 或 insert 都是一个完整的周期：哈希、按索引查找、键比较（由于冲突，可能多次）。两次调用 = 双倍工作量。如果两次调用之间发生了重新调整大小呢？那就是三倍工作量！

解决方案：Entry API —— 你的救生圈

Rust 提供了一个优雅的解决方案——Entry API。这是一种机制，允许你通过一次遍历完成查找和可能的插入。以下是用于单词计数的正确代码：

use std::collections::HashMap;\n\nfn count_words_efficient(words: &[&str]) -> HashMap<String, u32> {\n    let mut map = HashMap::new();\n    \n    for word in words {\n        let entry = map.entry(word.to_string());\n        *entry.or_insert(0) += 1;\n    }\n    \n    map\n}\n

简洁、美观、高效。但它在底层是如何工作的呢？让我们逐步分解。

步骤 1：entry() 方法

调用 map.entry(key) 返回一个 Entry 枚举，它可以处于两种状态：

\n
• Entry::Occupied —— 键已存在于表中。
\n
• Entry::Vacant —— 键不存在，并且我们有一个准备好的位置用于插入。
\n

重要提示：在此