String 与 HashMap

UTF-8 字符串的所有权模型，与哈希容器的增删查改。

`String` 与 `&str` 深入

`String` 是「拥有所有权的 UTF-8 字节缓冲区」

String ≈ Vec<u8> + 不变式：内容永远是合法 UTF-8；
&str ≈ &[u8] + 同一个不变式；
两者都可以表示任意 Unicode 文本，且长度不是字符数。

rust

fn main() {
    let s = String::from("héllo");           // 'é' 在 UTF-8 里占 2 字节
    println!("字节数 len()      = {}", s.len());              // 输出：6
    println!("字符数 chars()    = {}", s.chars().count());    // 输出：5
    println!("字节内容          = {:?}", s.bytes().collect::<Vec<u8>>());
    // 输出：字节内容 = [104, 195, 169, 108, 108, 111]

    for (i, c) in s.char_indices() {
        print!("{i}:{c} ");
    }
    println!();
    // 输出：0:h 1:é 3:l 4:l 5:o
}

   "héllo" 的 UTF-8 字节布局
   下标   0     1     2     3     4     5
        ┌────┬─────┬─────┬────┬────┬────┐
        │ h  │ 0xC3│ 0xA9│ l  │ l  │ o  │      ← 'é' = U+00E9 编码成 2 字节
        └────┴─────┴─────┴────┴────┴────┘
   字符边界： ↑     ↑           ↑    ↑    ↑      （1 在 'é' 内部，不是边界！）

为什么不能按字节索引

三个长度概念必须分清，混用是中文/emoji 场景下最常见的 bug 来源：

概念	含义	得到方式	"héllo"
字节（byte）	UTF-8 编码长度，`len()` 是它	`s.len()` / `s.bytes()`	6
标量值（Unicode scalar value）	`char`（1~4 字节），不等于「用户感知的字符」	`s.chars().count()`	5
字素簇（grapheme cluster）	用户眼里的「一个字符」，如 `é`（e + 组合符）、国旗、家庭 emoji	需 `unicode-segmentation` crate	5

rust

// ❌ 此代码无法编译
fn main() {
    let s = String::from("hello");
    let c = s[0];                 // String 根本没有实现 Index<usize>
}

error[E0277]: the type `str` cannot be indexed by `{integer}`
 --> src\main.rs:4:15
  |
4 |     let c = s[0];
  |               ^ string indices are ranges of `usize`
  |
  = help: the trait `SliceIndex<str>` is not implemented for `{integer}`
  = note: you can use `.chars().nth()` or `.bytes().nth()`
  = note: required for `String` to implement `Index<{integer}>`

Rust 干脆不提供 Index<usize> for String，理由是一个字节不是一个字符：如果允许 s[0] 返回 u8，你会写出「拿半个汉字」的代码；如果返回 char，那 s[0] 就得是 O(n) 的（要先算出第 0 个字符占几字节）—— 用索引语法做 O(n) 操作违背直觉。所以按字符取值请显式写 .chars().nth(i)，让 O(n) 的代价看得见。

`&s[0..2]` 的字节边界 panic

切片语法 &s[a..b] 是合法的（str 实现了 Index<Range<usize>>），但运行期会检查 a、b 是否落在字符边界上。

rust

// 运行期 panic 演示
fn main() {
    let s = String::from("héllo");
    let bad = &s[0..2];              // 2 落在 'é' 中间
    println!("{bad}");
}

thread 'main' panicked at src\main.rs:4:17:
end byte index 2 is not a char boundary; it is inside 'é' (bytes 1..3 of string)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

安全地按字符截取（这是「取前 N 个字符」的正确写法）：

rust

fn truncate_chars(s: &str, max_chars: usize) -> &str {
    match s.char_indices().nth(max_chars) {
        Some((idx, _)) => &s[..idx],   // 第 max_chars 个字符的起始字节一定在边界上
        None => s,                     // 字符数不足，原样返回
    }
}

fn main() {
    let s = "héllo 世界";
    println!("{}", truncate_chars(s, 3));      // 输出：hél
    println!("{}", truncate_chars(s, 99));     // 输出：héllo 世界
    println!("{}", &s[0..1]);                  // 输出：h（字节 0..1 恰好在边界上）
    println!("{:?}", s.get(0..2));             // 输出：None（不 panic，返回 Option）
}

🧠 原理：str::get(range) 是 &s[range] 的「不 panic 版本」，返回 Option<&str>；is_char_boundary(i) 可以单独查询某个字节下标是不是边界。处理用户输入、日志切片、协议解析时默认用 get，只有在你已经验证过边界时才用 []。

🚀 进阶：如果业务上「字符」指用户看到的字形（如 emoji 组合、国旗、带音标的字母），加 cargo add unicode-segmentation@1，用 .graphemes(true).count()。标准库只保证到 Unicode 标量值（char）这一层。

遍历：`chars()` / `bytes()` / `char_indices()`

rust

fn main() {
    let s = "aé中";

    let chars: Vec<char> = s.chars().collect();               // 按字符
    let bytes: Vec<u8> = s.bytes().collect();                 // 按字节
    let indexed: Vec<(usize, char)> = s.char_indices().collect();

    println!("{chars:?}");      // 输出：['a', 'é', '中']
    println!("{bytes:?}");      // 输出：[97, 195, 169, 228, 184, 173]
    println!("{indexed:?}");    // 输出：[(0, 'a'), (1, 'é'), (3, '中')]

    // 反向遍历字符：chars() 是 DoubleEndedIterator
    let reversed: String = s.chars().rev().collect();
    println!("{reversed}");     // 输出：中éa

    // 只有 ASCII 场景才可以用 bytes() 做「快路径」
    println!("{}", "abc".bytes().all(|b| b.is_ascii_lowercase()));   // 输出：true
    println!("{}", s.is_ascii());                                    // 输出：false
}

想要	用什么	复杂度
第 i 个字符	`s.chars().nth(i)`	O(n)（每次从头扫）
反复按下标取字符	先 `let v: Vec<char> = s.chars().collect();` 再 `v[i]`	一次性 O(n)，之后 O(1)
字符 + 其字节偏移	`s.char_indices()`	O(n)
按字节快速处理	`s.bytes()` / `s.as_bytes()`	O(1) 取视图，O(n) 遍历

⚠️ 陷阱：s.chars().nth(i) 是 O(n)，写在循环里就成了 O(n²)。需要按下标随机访问时，先 collect::<Vec<char>>() 一次。

拼接：`push_str` / `push` / `+` / `format!`

rust

fn main() {
    let mut s = String::from("Hello");
    s.push_str(", ");                    // 追加 &str（就地扩容，不产生新对象）
    s.push('世');                        // 追加单个 char
    println!("{s}");                     // 输出：Hello, 世

    let suffix = String::from("界");
    let joined = s + &suffix;            // 注意：s 被移动了，&suffix 被借用
    // println!("{s}");                  // E0382: borrow of moved value: `s`

    let formatted = format!("{joined} ({})", suffix.len());   // format! 只借用，不夺取
    println!("{formatted}");             // 输出：Hello, 世界 (3)
    println!("{suffix}");                // suffix 仍然可用

    // 从多个部分拼：format! 是首选，可读性最好
    let name = "Rust";
    let ver = 2024;
    let title = format!("{name} edition {ver}");
    println!("{title}");                 // 输出：Rust edition 2024
}

+ 运算符的本质是一个吃掉左操作数的方法（&str 是 Add 的右操作数类型）：

text

// std 里的真实签名（Stable 版，简化）：
fn add(self, other: &str) -> String

它带来三条限制，理解之后就不会再困惑：

写法	结果	原因
`s1 + &s2`	✅ `s1` 被移动，`&String` 通过解引用强制转换变成 `&str`	签名是 `fn add(self, other: &str) -> String`
`s1 + s2`	❌ `E0308`（expected `&str`, found `String`）	右操作数必须是 `&str`，不是 `String`
`s1 + &s2 + &s3`	✅ 左结合：`(s1 + &s2) + &s3`，第一个结果又是 `String`	每次 `+` 都产生一个新的 `String`
`&s1 + &s2`	❌ 左操作数必须是 `String`（`self` 按值）	没有 `impl Add<&str> for &String`

rust

fn main() {
    let a = String::from("a");
    let b = String::from("b");
    let c = String::from("c");

    let r1 = a + &b + &c;                // ✅ a 被移动，r1 = "abc"
    println!("{r1}");

    // let bad = b + c;                  // ❌ E0308: expected `&str`, found `String`
    // let bad2 = &b + &c;               // ❌ E0277: `&String + &String` 没有实现

    // 需要保留左操作数时：clone 一次，或用 format!
    let r2 = b.clone() + &c;
    println!("{r2} / {b}");              // 输出：bc / b
}

⚠️ 陷阱：+ 每次都会分配新 String，在循环里累加字符串是 O(n²)。循环内用 push_str，跨片段拼接用 format!。format! 不夺取所有权、可读性最好，代价是一次分配 —— 它是绝大多数场景的正确答案。

常用方法表

方法	作用	示例 → 结果
`len()` / `is_empty()`	字节数 / 是否为空	`"中".len()` → `3`
`trim()`	去掉两端空白（含 `\n`、`\t`）	`" a ".trim()` → `"a"`
`trim_start` / `trim_end`	只去一端	`" a ".trim_end()` → `" a"`
`split(pat)`	按分隔符切，保留空段，返回迭代器	`"a,,b".split(',')` → 3 段
`split_whitespace()`	按任意连续空白切，丢弃空段	`" a b ".split_whitespace()` → `["a","b"]`
`lines()`	按 `\n` 切，自动去掉行尾 `\r`	`"a\r\nb".lines()` → `["a","b"]`
`replace(from, to)`	全部替换，返回新 `String`	`"a-b".replace('-', "+")` → `"a+b"`
`starts_with` / `ends_with`	前缀 / 后缀判断	`"log.txt".ends_with(".txt")` → `true`
`contains(pat)`	是否包含子串 / 字符 / 字符集合模式	`"hello".contains(['a','e'])` → `true`
`to_uppercase` / `to_lowercase`	Unicode 感知的大小写转换（返回新 `String`）	`"ß".to_uppercase()` → `"SS"`
`to_ascii_uppercase`	仅 ASCII，原地可用的快路径	`"abc".to_ascii_uppercase()` → `"ABC"`
`parse::<T>()`	解析成其他类型，返回 `Result<T, ParseXxxError>`	`"42".parse::<i32>()` → `Ok(42)`
`find(pat)`	第一个匹配的字节下标	`"a中b".find('中')` → `Some(1)`
`chars()` / `bytes()` / `char_indices()`	三种遍历视角	见「遍历：`chars()` / `bytes()` / `char_indices()`」
`into_bytes()`	消费 `String` 拿到 `Vec<u8>`	零拷贝转换
`as_str()`	`String` → `&str`（显式化借用）	传给只要 `&str` 的函数
`to_string()` / `to_owned()`	`&str` → `String`（一次分配）	需要拥有时

rust

fn main() {
    // 典型的「解析一行配置」：trim → split → parse，一条链解决
    let line = "  timeout = 30  ";
    let (key, value) = line.split_once('=').expect("配置项必须含 '='");
    let timeout: u32 = value.trim().parse().expect("timeout 必须是整数");
    println!("{} = {}", key.trim(), timeout);        // 输出：timeout = 30

    let joined: String = ["a", "b", "c"].join("-");
    println!("{joined}");                            // 输出：a-b-c
    println!("{:?}", "42x".parse::<i32>());          // 输出：Err(ParseIntError { .. })
}

⚠️ 陷阱：讲 unwrap/expect 的规矩 —— 上面用了 expect，因为这是「输入不合法就立刻失败」的一次性脚本场景。库代码里应当返回 Result 并用 ? 传播，见错误处理。unwrap() 等价于 expect("called Option::unwrap()on aNone value")，信息量为零；至少要写 expect("timeout 字段缺失")，或者干脆用 ?。

`OsString` / `PathBuf` / `CString`：三种「另一种字符串」

标准库还有三个字符串家族，各有明确的出现场景（本章只做定位，细节在后续章节）：

类型	一句话说明	典型出现场景
`OsString` / `&OsStr`	操作系统原生字符串，不保证是合法 UTF-8（Windows 上尤其如此）	`std::env::args_os()`、可能含非法 UTF-8 的文件名；需要时才 `to_string_lossy()`
`PathBuf` / `&Path`	路径专用类型，带 `join`/`parent`/`extension`/`file_name` 等平台无关方法	`std::fs`、`std::path` 的所有 API；比手工拼 `String` 更安全（自动处理分隔符）
`CString` / `&CStr`	以 `\0` 结尾、内部无 `\0` 的字节串，用于 FFI 传给 C	`extern "C"` 函数、`libc` 调用；`CString::new("a\0b")` 会返回 `Err`（内含 NUL）

rust

use std::path::{Path, PathBuf};

fn main() {
    // 路径拼接用 PathBuf::join，而不是字符串相加
    let dir = PathBuf::from("C:/logs");
    let file = dir.join("app.log");
    println!("{}", file.display());                       // Windows 输出：C:/logs\app.log
    println!("{:?}", file.extension());                   // 输出：Some("log")
    println!("{:?}", Path::new("a/b/c.txt").file_stem()); // 输出：Some("c")

    // 参数用 &Path 而不是 &PathBuf，理由与 &[T] / &Vec<T> 完全一样
    fn size_of_name(p: &Path) -> usize {
        p.file_name().map_or(0, |n| n.to_string_lossy().len())
    }
    println!("{}", size_of_name(&file));                  // 输出：7
}

💡 对照：Python 里「字符串就是路径就是字节」混在一起，Windows 编码问题常在运行期爆炸； Rust 用三个类型把「文本」「路径」「操作系统字节」分开，编译器帮你选对 API。需要转回普通字符串：Path::to_str()（返回 Option<&str>）或 to_string_lossy()（非法字节替换成 U+FFFD）。

`HashMap<K, V>` 与 `HashSet<T>`

创建、插入、获取

HashMap<K, V> 是无序的哈希表（hash table），默认用 SipHash-1-3 + 随机种子。它与 Python dict、JS Map 定位相同，但 key 必须实现 Eq + Hash。

rust

use std::collections::HashMap;

fn main() {
    let mut scores: HashMap<String, i32> = HashMap::new();

    // 1) 插入：同 key 后插入的覆盖先插入的，insert 返回被覆盖的旧值
    assert_eq!(scores.insert(String::from("蓝队"), 10), None);
    assert_eq!(scores.insert(String::from("蓝队"), 12), Some(10));
    assert_eq!(scores.get("蓝队"), Some(&12));

    // 2) get 返回 Option<&V>；实参可以是 &str，因为 String: Borrow<str>
    assert_eq!(scores.get("红队"), None);

    // 3) 索引语法：key 不存在时 panic，等价于 get + expect
    assert_eq!(scores["蓝队"], 12);

    // 4) get_mut 拿到 &mut V 就地修改
    if let Some(v) = scores.get_mut("蓝队") {
        *v += 1;
    }
    assert_eq!(scores["蓝队"], 13);

    // 5) contains_key / remove / len
    assert!(scores.contains_key("蓝队"));
    assert_eq!(scores.remove("蓝队"), Some(13));
    assert!(scores.is_empty());
}

需求	写法	返回
插入 / 覆盖	`map.insert(k, v)`	`Option<V>`：被覆盖的旧值
只在缺失时插入	`map.entry(k).or_insert(v)`	`&mut V`
只在缺失时计算插入	`map.entry(k).or_insert_with(f)`	`&mut V`，`f` 只在缺失时调用
缺失时用 `Default`	`map.entry(k).or_default()`	`&mut V`，要求 `V: Default`
存在则改、不存在则插	`map.entry(k).and_modify(f).or_insert(v)`	`&mut V`
读取	`map.get(&k)`	`Option<&V>`
读取并修改	`map.get_mut(&k)`	`Option<&mut V>`
删除	`map.remove(&k)`	`Option<V>`
删除并取回 key+value	`map.remove_entry(&k)`	`Option<(K, V)>`
遍历	`for (k, v) in &map`	`(&K, &V)`
就地删除	`map.retain(\|k, v\| ...)`	1.18 起

更新：覆盖 / 存在才插入 / 基于旧值更新

词频统计是「基于旧值更新」的经典场景。三种写法对比：

rust

use std::collections::HashMap;

fn main() {
    let text = "the quick brown fox jumps over the lazy dog the fox";

    // 写法 A（推荐）：entry + or_insert，一次查找搞定「有则 +1，无则置 0 再 +1」
    let mut counts: HashMap<&str, usize> = HashMap::new();
    for word in text.split_whitespace() {
        *counts.entry(word).or_insert(0) += 1;
    }
    assert_eq!(counts["the"], 3);          // 注意 key 是 &str，零分配
    assert_eq!(counts["fox"], 2);

    // 写法 B：contains_key + insert —— 查找两次，且要 clone key
    let mut slow: HashMap<String, usize> = HashMap::new();
    for word in text.split_whitespace() {
        if slow.contains_key(word) {
            *slow.get_mut(word).expect("刚查过") += 1;
        } else {
            slow.insert(word.to_string(), 1);
        }
    }
    assert_eq!(slow["the"], 3);

    // 写法 C：or_insert_with —— 值的构造代价高时才值得用它而非 or_insert(默认值)
    let mut buckets: HashMap<char, Vec<&str>> = HashMap::new();
    for word in text.split_whitespace() {
        let Some(first) = word.chars().next() else { continue };
        buckets.entry(first).or_default().push(word);
    }
    println!("{}", buckets.len());          // 输出：8（t/q/b/f/j/o/l/d 八个首字母）
}

Entry API 为什么比 contains_key + insert 更高效？

   contains_key + insert（写法 B）：两次哈希 + 两次探测
   ┌──────────────────────────────────────────────────────────────┐
   │ hash(key) → 找桶 → 探测比较 → 返回 true/false                 │  ← 第 1 次
   │ hash(key) → 再找桶 → 再探测 → 插入/修改                       │  ← 第 2 次（重复劳动）
   └──────────────────────────────────────────────────────────────┘

   entry（写法 A + and_modify）：一次哈希 + 一次探测
   ┌──────────────────────────────────────────────────────────────┐
   │ hash(key) → 找桶 → 探测 → 拿到 Entry::{Occupied, Vacant}      │  ← 唯一一次
   │              ├─ Occupied(v) ⇒ 直接改 *v                      │
   │              └─ Vacant(e)   ⇒ e.insert(默认值)               │
   └──────────────────────────────────────────────────────────────┘

除了省一次哈希，entry 还避免了「为了插入而 clone() key」—— insert 要拿走 key 的所有权，所以写法 B 里必须 word.to_string()。写法 A 直接用 &str 当 key，一次分配都没有。

rust

use std::collections::HashMap;

fn main() {
    // and_modify + or_insert：一句话表达「存在的加 100，不存在的初始化为 1」
    let mut m: HashMap<&str, i32> = HashMap::new();
    m.insert("hit", 5);
    m.entry("hit").and_modify(|v| *v += 100).or_insert(1);
    m.entry("miss").and_modify(|v| *v += 100).or_insert(1);
    assert_eq!(m["hit"], 105);
    assert_eq!(m["miss"], 1);

    // or_insert_with 只在缺失时求值：适合构造代价高的默认值
    let mut graph: HashMap<&str, Vec<&str>> = HashMap::new();
    graph.entry("a").or_insert_with(Vec::new).push("b");
    println!("{:?}", graph["a"]);          // 输出：["b"]
}

⚠️ 陷阱：or_insert(expensive()) 每次调用都会先算出 expensive()，即使 key 已存在。需要「惰性默认值」时用 or_insert_with(|| expensive()) 或 or_default()。这与 Python dict.setdefault(k, compute()) 的坑完全一样。

遍历顺序不保证

rust

use std::collections::HashMap;

fn main() {
    let mut m: HashMap<&str, i32> = HashMap::new();
    for (i, k) in ["a", "b", "c", "d", "e"].iter().enumerate() {
        m.insert(k, i as i32);
    }
    let order: Vec<&str> = m.keys().copied().collect();
    println!("{order:?}");       // 每次运行都可能是不同顺序！
}

原因有三层，层层叠加：

哈希种子随机：HashMap 默认用 RandomState，每个 HashMap 实例的种子不同，且进程每次启动都变（DoS 防护，见「RandomState、哈希 DoS 与性能取舍」）；
探测顺序：开放寻址 / 桶链的实现细节决定了「同哈希值」的排列；
删除会留空位：remove 之后的插入会复用空位，进一步打乱顺序。

需要稳定顺序时：

rust

use std::collections::BTreeMap;

fn main() {
    let mut m: BTreeMap<&str, i32> = BTreeMap::new();
    m.insert("c", 3);
    m.insert("a", 1);
    m.insert("b", 2);
    let keys: Vec<&str> = m.keys().copied().collect();
    println!("{keys:?}");            // 永远输出：["a", "b", "c"]
}

自定义 key 需要 `Eq + Hash`

HashMap<K, V> 的方法签名带约束 K: Eq + Hash。用结构体当 key 必须 #[derive(PartialEq, Eq, Hash)]：

rust

use std::collections::HashMap;

#[derive(Debug, PartialEq, Eq, Hash)]
struct Point {
    x: i32,
    y: i32,
}

fn main() {
    let mut grid: HashMap<Point, &str> = HashMap::new();
    grid.insert(Point { x: 0, y: 0 }, "原点");
    grid.insert(Point { x: 1, y: 0 }, "右");
    assert_eq!(grid.get(&Point { x: 0, y: 0 }), Some(&"原点"));
    println!("{}", grid.len());      // 输出：2
}

不能当 key 的类型与替代方案：

类型	能否当 key	说明与替代
`i32` / `u64` / `bool` / `char`	✅	都实现了 `Eq + Hash`
`String` / `&str`	✅	用 `&str` key 可避免为插入而 `to_string()`
`Vec<T>` / `&[T]`	✅	`Vec` 与切片都实现了 `Hash + Eq`，适合「字节串 → 值」
`Option<T>` / `Result` / 元组	✅	当 `T` 满足时自动满足
自定义 `struct` / `enum`	✅（需 `derive`）	`#[derive(PartialEq, Eq, Hash)]`
`f64` / `f32`	❌	`f64` 不实现 `Eq`（`NaN != NaN`）也不实现 `Hash`。改用 `ordered_float` crate，或把浮点转成定点整数
`HashMap` 自身	❌	不实现 `Hash`；需要复合 key 就用元组或 `BTreeMap`

🧠 原理：Hash 是「把值映射成 u64 摘要」的能力；Eq 是「判断两个值是否相等」的能力。哈希表要求两者一致：a == b 必须推出 hash(a) == hash(b)。手写 Hash 时只 hashCode 部分字段、而 Eq 比较全部字段，就会让哈希表「查不到刚插进去的值」。用 derive 就不会犯这个错（两个宏按同一组字段生成）。

⚠️ 陷阱：HashMap::get 的实参类型是 &Q，其中 K: Borrow<Q>。所以 HashMap<String, V> 可以用 map.get("literal")（String: Borrow<str>），但 HashMap<&str, V> 只能用 &str，传 &String 需要写 map.get(s.as_str()) （或依赖解引用强制转换：map.get(&*s)）。

`RandomState`、哈希 DoS 与性能取舍

rust

use std::collections::HashMap;
use std::collections::hash_map::RandomState;

fn main() {
    let a: HashMap<u32, u32> = HashMap::new();                 // 默认：SipHash-1-3 + 随机种子
    let b: HashMap<u32, u32, RandomState> = HashMap::new();    // 完全等价，只是显式写出类型

    let mut hasher = std::hash::DefaultHasher::new();
    std::hash::Hash::hash(&"hello", &mut hasher);
    println!("{:x}", std::hash::Hasher::finish(&hasher));
    println!("{} {}", a.len(), b.len());                       // 输出：0 0
}

为什么默认哈希这么「慢」？ 因为要防 哈希 DoS（HashDoS）：如果哈希函数是确定的（例如 JS 早期、PHP 早期、Java 的 String.hashCode()），攻击者可以离线构造出成千上万个哈希值相同的 key，让每次 insert 退化成 O(n)，把一次 HTTP 请求变成 CPU 打满。RandomState 每次实例化都从系统取随机种子（并在进程内递增计数器），攻击者无法预测碰撞，于是攻击成本从「离线算一次」变成「必须先探测你的种子」。代价是 SipHash 比 FxHash/wyhash 这类非加密哈希慢数倍。

场景	建议	理由
默认（用户输入、网络数据、配置）	不写任何东西，用 `HashMap::new()`	安全优先，性能足够
大量小整数 key、纯内部计算、无攻击面	`rustc-hash` 的 `FxHashMap`（`cargo add rustc-hash@2`）	快 2~5 倍
需要稳定哈希（可复现的构建 / 跨进程一致）	`ahash`（`cargo add ahash@0.8`）或自带种子的 `RandomState`	注意：稳定 == 可被攻击
需要有序 + 范围查询	`BTreeMap`	哈希表做不到

rust

// 使用第三方哈希器的写法（需要 Cargo.toml 依赖，见上方 cargo add）
use std::collections::HashMap;
use std::hash::BuildHasherDefault;
use std::collections::hash_map::DefaultHasher;

fn main() {
    // 这里用 DefaultHasher 演示「替换哈希器」的语法形状；
    // 实际项目应换成 rustc_hash::FxHasher 或 ahash::AHasher
    type FastMap<K, V> = HashMap<K, V, BuildHasherDefault<DefaultHasher>>;
    let mut m: FastMap<u32, u32> = FastMap::default();   // 注意：不是 HashMap::new()
    m.insert(1, 2);
    println!("{}", m[&1]);                               // 输出：2
}

⚠️ 陷阱：换成自定义 BuildHasher 后不能再用 HashMap::new()（它固定返回 HashMap<K, V, RandomState>），要用 HashMap::default() / HashMap::with_hasher(...)。 HashMap::new 只在 S = RandomState 时存在。

`BTreeMap` 对照表

rust

use std::collections::BTreeMap;

fn main() {
    let mut log: BTreeMap<u64, &str> = BTreeMap::new();
    log.insert(1_700_000_003, "登录");
    log.insert(1_700_000_001, "启动");
    log.insert(1_700_000_002, "加载配置");

    for (ts, ev) in &log {                       // 按 key 升序，天然有序
        println!("{ts} {ev}");
    }
    // 输出：1700000001 启动 / 1700000002 加载配置 / 1700000003 登录

    for (_, ev) in log.range(1_700_000_002..) {   // 范围查询：O(log n) 定位 + 顺序扫描
        println!("since {ev}");
    }
    // 输出：since 加载配置 / since 登录

    println!("{:?}", log.first_key_value());      // 输出：Some((1700000001, "启动"))
    println!("{:?}", log.pop_last());             // 输出：Some((1700000003, "登录"))
}

维度	`HashMap<K, V>`	`BTreeMap<K, V>`
底层结构	哈希表（默认 SipHash + 随机种子）	B 树（B-tree，节点多路平衡）
约束	`K: Eq + Hash`	`K: Ord`
平均查找	O(1)	O(log n)
最坏查找	O(n)（哈希全碰撞时）	O(log n)（有保证）
遍历顺序	不保证（同一份数据两次遍历都可能不同）	永远按 key 升序
范围查询 `range(a..b)`	❌ 没有	✅ O(log n + k)
取最小 / 最大	❌ 要么 O(n) 扫，要么自己维护	✅ `first_key_value` / `last_key_value`（O(log n)）
内存	较省（有装载因子，通常 ≤ 87.5%）	较多（节点有填充与指针）
有序输出	要先 `collect` + `sort`	直接遍历
抗 HashDoS	✅（随机种子）	✅（结构本身不依赖哈希）
典型用途	计数、缓存、索引、去重	排行榜、时间线、区间查询、需要可复现输出

💡 对照：Python 3.7+ 的 dict 保序（插入顺序），所以「要稳定输出」在 Python 里不用换类型；Rust 的 HashMap 不保序，要稳定就得换 BTreeMap 或自己排序。 C++ 的 std::unordered_map 对应 HashMap，std::map 对应 BTreeMap； Java 的 HashMap 对应 HashMap，TreeMap 对应 BTreeMap。

`HashSet<T>`：只有 key 的哈希表

HashSet<T> ≈ HashMap<T, ()>，用于去重与集合运算。

rust

use std::collections::HashSet;

fn main() {
    let a: HashSet<i32> = [1, 2, 3, 4].into_iter().collect();
    let b: HashSet<i32> = [3, 4, 5].into_iter().collect();

    let mut inter: Vec<i32> = a.intersection(&b).copied().collect();
    inter.sort();                                    // 集合迭代顺序不定，排序后才是稳定断言
    println!("{inter:?}");                           // 输出：[3, 4]
    println!("{}", a.difference(&b).count());        // 输出：2
    println!("{}", a.is_subset(&b));                 // 输出：false
    println!("{}", a.union(&b).count());             // 输出：5

    // insert 返回 bool：true 表示「之前没有，刚刚插进去」。这是去重的惯用法
    let mut seen = HashSet::new();
    let dups: Vec<i32> = [1, 2, 2, 3, 1]
        .into_iter()
        .filter(|x| !seen.insert(*x))                // 插入失败 == 重复
        .collect();
    println!("{dups:?}");                            // 输出：[2, 1]
}

从数组构造：`HashMap::from` 与 `collect`

rust

use std::collections::HashMap;

fn main() {
    // 1) HashMap::from([...])：1.56 起，适合写死的常量映射
    let status: HashMap<u16, &str> = HashMap::from([(200, "OK"), (404, "Not Found")]);
    println!("{}", status[&404]);                    // 输出：Not Found

    // 2) collect()：从任意迭代器收集，元组 (K, V) 流
    let keys = ["x", "y", "z"];
    let vals = [10, 20, 30];
    let zipped: HashMap<&str, i32> = keys.into_iter().zip(vals).collect();
    println!("{}", zipped["y"]);                     // 输出：20

    // 3) 先 collect 成 Vec 再 collect 成 HashMap：处理「重复 key 取最后一个」的场景
    let raw = [("a", 1), ("b", 2), ("a", 3)];
    let dedup: HashMap<&str, i32> = raw.into_iter().collect();
    println!("{}", dedup["a"]);                      // 输出：3（后者覆盖前者）
}

⚠️ 陷阱：collect::<HashMap<_, _>>() 遇到重复 key 不报错，后者静默覆盖前者。如果重复是错误，要显式检查：先 collect::<Vec<_>>()，比较 len()，或用 try_fold + entry 手动检测冲突。

学习路线与环境准备

环境搭建与工具链

变量与流程控制

所有权与借用

结构体、枚举与 trait

集合与迭代器

错误处理

泛型与生命周期

智能指针与闭包

并发编程

异步编程

宏与元编程

工程化与常用 crate

测试、性能与 unsafe

String 与 HashMap

`String` 与 `&str` 深入

`String` 是「拥有所有权的 UTF-8 字节缓冲区」

为什么不能按字节索引

`&s[0..2]` 的字节边界 panic

遍历：`chars()` / `bytes()` / `char_indices()`

拼接：`push_str` / `push` / `+` / `format!`

常用方法表

`OsString` / `PathBuf` / `CString`：三种「另一种字符串」

`HashMap<K, V>` 与 `HashSet<T>`

创建、插入、获取

更新：覆盖 / 存在才插入 / 基于旧值更新

遍历顺序不保证

自定义 key 需要 `Eq + Hash`

`RandomState`、哈希 DoS 与性能取舍

`BTreeMap` 对照表

`HashSet<T>`：只有 key 的哈希表

从数组构造：`HashMap::from` 与 `collect`

String 与 HashMap ​

String 与 &str 深入 ​

String 是「拥有所有权的 UTF-8 字节缓冲区」 ​

为什么不能按字节索引 ​

&s[0..2] 的字节边界 panic ​

遍历：chars() / bytes() / char_indices() ​

拼接：push_str / push / + / format! ​

常用方法表 ​

OsString / PathBuf / CString：三种「另一种字符串」 ​

HashMap<K, V> 与 HashSet<T> ​

创建、插入、获取 ​

更新：覆盖 / 存在才插入 / 基于旧值更新 ​

遍历顺序不保证 ​

自定义 key 需要 Eq + Hash ​

RandomState、哈希 DoS 与性能取舍 ​

BTreeMap 对照表 ​

HashSet<T>：只有 key 的哈希表 ​

从数组构造：HashMap::from 与 collect ​

String 与 HashMap

`String` 与 `&str` 深入

`String` 是「拥有所有权的 UTF-8 字节缓冲区」

为什么不能按字节索引

`&s[0..2]` 的字节边界 panic

遍历：`chars()` / `bytes()` / `char_indices()`

拼接：`push_str` / `push` / `+` / `format!`

常用方法表

`OsString` / `PathBuf` / `CString`：三种「另一种字符串」

`HashMap<K, V>` 与 `HashSet<T>`

创建、插入、获取

更新：覆盖 / 存在才插入 / 基于旧值更新

遍历顺序不保证

自定义 key 需要 `Eq + Hash`

`RandomState`、哈希 DoS 与性能取舍

`BTreeMap` 对照表

`HashSet<T>`：只有 key 的哈希表

从数组构造：`HashMap::from` 与 `collect`