comprehensive-rust 课程精讲标准库 HashMap 的插入、查询与防 HashDoS 设计【免费下载链接】comprehensive-rustThis is the Rust course used by the Android team at Google. It provides you the material to quickly teach Rust.项目地址: https://gitcode.com/GitHub_Trending/co/comprehensive-rust导读本文围绕 Google Android 团队维护的开源 Rust 课程 comprehensive-rust 中「Standard Library Types」章节的HashMap一讲即 src/std-types/hashmap.md展开系统讲解std::collections::HashMap的引入方式、增删查改的常用 API、基于entry的原子式「查无则插」惯用法、以及从数组字面量与迭代器构造哈希表的高级写法。文中还结合课程配套的 Counter 练习 与 参考答案展示如何用HashMap与entry实现一个通用计数器帮助你同时掌握标准库容器的实战用法与 Rust 泛型设计思路。课程定位HashMap在 comprehensive-rust 中的位置comprehensive-rust 是 Google Android 团队用于快速教授 Rust 的课程材料见仓库根目录 README.md其标准库类型Standard Library Types章节由 src/std-types.md 统领依次覆盖std/core/alloc分层、Option、Result、String、Vec与HashMap目录结构见 src/SUMMARY.md。关于标准库分层课程在 src/std-types/std.md 中强调core最基础的类型与函数不依赖libc、分配器甚至操作系统alloc依赖全局堆分配器的类型如Vec、Box、Arcstd完整标准库。嵌入式 Rust 通常只用core有时加alloc。HashMap属于std层内部分配在堆上正因如此它默认不在预导入prelude中需要显式use std::collections::HashMap;才能使用。在课程大纲中HashMap一讲紧接Vecsrc/std-types/vec.md两者都是存储在堆上、可在运行时增长收缩的集合类型但HashMap以K - V键值对形式提供 O(1) 平均复杂度的查询能力是后续 Counter 练习 的基础。HashMap是什么带 HashDoS 防护的标准哈希表课程对HashMap的一句话定义是Standard hash map with protection against HashDoS attacks.即它是标准库提供的哈希表实现并且内置了对 HashDoS哈希碰撞拒绝服务攻击的防护。这意味着默认情况下HashMap使用带随机种子的哈希算法随机种子在每次创建哈希表时生成攻击者难以预先构造大量碰撞键来拖慢查找性能。需要确定性哈希的场景如进程内缓存、特定算法可以改用HashMap::with_hasher传入自定义Hasher但课程默认示例均使用标准默认实现。课程给出的完整示例src/std-types/hashmap.md一次覆盖了插入、查询、遍历与更新四种基本操作use std::collections::HashMap; fn main() { let mut page_counts HashMap::new(); page_counts.insert(Adventures of Huckleberry Finn, 207); page_counts.insert(Grimms Fairy Tales, 751); page_counts.insert(Pride and Prejudice, 303); if !page_counts.contains_key(Les Misérables) { println!( We know about {} books, but not Les Misérables., page_counts.len() ); } for book in [Pride and Prejudice, Alices Adventure in Wonderland] { match page_counts.get(book) { Some(count) println!({book}: {count} pages), None println!({book} is unknown.), } } // Use the .entry() method to insert a value if nothing is found. for book in [Pride and Prejudice, Alices Adventure in Wonderland] { let page_count: mut i32 page_counts.entry(book).or_insert(0); *page_count 1; } dbg!(page_counts); }关键 API 一览API作用返回值HashMap::new()创建空哈希表HashMapK, Vinsert(k, v)插入键值对若键已存在则覆盖OptionV返回旧值contains_key(k)判断键是否存在boolget(k)按键取值OptionVlen()返回键值对数量usizeentry(k)获取键的入口可查可插Entry配合or_insert/or_default使用keys()/values()迭代键 / 值Keys/Values等专用迭代器类型从 prelude 到作用域为什么必须显式use课程明确提醒src/std-types/hashmap.mdHashMapis not defined in the prelude and needs to be brought into scope.Rust 的 prelude 只预导入少数最常用的类型如Vec、String、Option、ResultHashMap不在其中因此直接写HashMap::new()会编译报错。必须通过use std::collections::HashMap;将其引入作用域或者在使用时写全路径std::collections::HashMap::new()。这一点与课程前面的VecVec也在 prelude 中但vec!宏、Vec::with_capacity等行为不同形成对照Vec无需use而HashMap必须显式引入——这也是初学标准库容器时常遇到的第一个编译错误来源。get与contains_key安全查询绝不 panic课程示例展示了两种查询方式contains_key(k)只返回bool适合仅判断存在性get(k)返回OptionV配合match可以优雅处理存在/不存在两种分支for book in [Pride and Prejudice, Alices Adventure in Wonderland] { match page_counts.get(book) { Some(count) println!({book}: {count} pages), None println!({book} is unknown.), } }与Vec使用[索引]越界会 panic 不同见 src/std-types/vec.md 的注意事项HashMap::get天然返回Option把键不存在变成可处理的状态而不是程序崩溃。这正是课程反复强调的 Rust 风格用类型系统表达失败可能性调用方必须显式处理None。如果想查不到就用一个默认值可以用unwrap_orlet pc1 page_counts .get(Harry Potter and the Sorcerers Stone) .unwrap_or(336);注意get返回的是V因此unwrap_or的参数需要传引用336。entryAPI一次查找完成「查无则插」课程给出的第二个关键技巧src/std-types/hashmap.md是entrylet pc2 page_counts .entry(The Hunger Games) .or_insert(374);语义是如果键存在entry返回对该键对应值的可变引用如果键不存在则先插入给定的默认值再返回其可变引用。因此entry(...).or_insert(default)把检查键是否存在 插入默认值合并为一次哈希查找既简洁又高效。课程示例中还展示了如何用entry做计数累加for book in [Pride and Prejudice, Alices Adventure in Wonderland] { let page_count: mut i32 page_counts.entry(book).or_insert(0); *page_count 1; }配合or_default()还能用零值自动初始化这一惯用法在 Counter 练习中会进一步发挥威力。构造哈希表hashmap!宏的缺席与替代方案课程特别指出src/std-types/hashmap.mdUnlikevec!, there is unfortunately no standardhashmap!macro.Vec有vec![...]宏但标准库并没有对应的hashmap!宏。不过自 Rust 1.56 起HashMap实现了From[(K, V); N]因此可以直接从数组字面量构造let page_counts HashMap::from([ (Harry Potter and the Sorcerers Stone.to_string(), 336), (The Hunger Games.to_string(), 374), ]);注意这里的键类型是String需要调用.to_string()转换如果直接写str字面量键的存活期与借用关系需要仔细处理。此外HashMap也可以由任意产出(K, V)元组的迭代器构造例如iter().collect()let page_counts: HashMapString, i32 some_pairs.into_iter().collect();这为从数据流聚合出映射提供了统一入口。方法专属返回类型Keys、Values等课程提醒src/std-types/hashmap.mdHashMap有若干方法专属的返回类型例如std::collections::hash_map::Keys、Values、Iter等。这些类型在 Rust 文档搜索中频繁出现例如keys()返回Keys_, K, V。它们本质上是借用哈希表内部存储的迭代器视图通常不必显式写出类型交给类型推断即可但在阅读 Rust 文档、查看函数签名时理解这类方法专属类型能显著降低困惑。实战延伸Counter 练习——把u32计数器泛型化HashMap一讲的配套练习是 src/std-types/exercise.md20 分钟中的 Counter该练习使用std::collections::HashMap记录见过哪些值、每个值出现过多少次。初始版本被硬编码为只能统计u32请把结构体与方法泛型化使其可以统计任意类型的值。如果提前完成尝试用entry方法把count方法所需的哈希查找次数减半。初始代码编译失败版本如下其count使用了先contains_key再get_mut/insert的两步写法use std::collections::HashMap; /// Counter counts the number of times each value of type T has been seen. struct Counter { values: HashMapu32, u64, } impl Counter { /// Create a new Counter. fn new() - Self { Counter { values: HashMap::new(), } } /// Count an occurrence of the given value. fn count(mut self, value: u32) { if self.values.contains_key(value) { *self.values.get_mut(value).unwrap() 1; } else { self.values.insert(value, 1); } } /// Return the number of times the given value has been seen. fn times_seen(self, value: u32) - u64 { self.values.get(value).copied().unwrap_or_default() } }课程给出的参考答案位于 src/std-types/exercise.rs核心改动有三点结构体泛型化struct CounterT { values: HashMapT, u64 }约束T: Eq HashHashMap的键必须满足Eq Hash因此impl块需要声明implT: Eq Hash CounterT用entry合并查找/// Count an occurrence of the given value. fn count(mut self, value: T) { *self.values.entry(value).or_default() 1; }一次entry调用同时完成查与插0 值再通过解引用累加把初始版本中contains_keyget_mut或insert的最多两次查找压缩为一次正是练习提示要求的优化方向。而times_seen保持get(...).copied().unwrap_or_default()未见过时返回 0/// Return the number of times the given value has been seen. fn times_seen(self, value: T) - u64 { self.values.get(value).copied().unwrap_or_default() }main中同时用整数与str两种键类型验证了泛型效果src/std-types/exercise.rsString等标准类型均已实现Eq Hash可直接作为键。本地运行与验证方式课程把HashMap讲解与练习组织在独立的 Cargo 包中src/std-types/Cargo.toml其二进制目标名为hashset入口即exercise.rs对应的 Bazel 构建配置src/std-types/BUILD.bazel同时定义了rust_binary与rust_test两个目标直接运行cargo run在该目录下或 Bazel 的bazel run //src/std-types:hashset跑测试cargo test或bazel test //src/std-types:hashset_test。需要说明的是文章正文中的HashMap示例代码块带有课程特有的editable/ignore/compile_fail标注前者可在 mdbook 环境中直接编辑运行compile_fail标注表示该版本故意无法编译用于引出泛型化改造。小结回顾 src/std-types/hashmap.md 的核心要点HashMap是标准库哈希表内置 HashDoS 防护但不在 prelude 中必须显式use std::collections::HashMap;查询使用get返回OptionV与contains_key返回bool不会因缺键而 panicentry(key).or_insert(default)/or_default()是查无则插与计数累加的标准惯用法一次哈希查找完成读写标准库没有hashmap!宏但 Rust 1.56 起可用HashMap::from([(k, v), ...])或由(K, V)元组迭代器collect得到keys()/values()等方法返回std::collections::hash_map::Keys等方法专属迭代器类型阅读文档时需留意。配合 Counter 练习 与 参考答案你就能把HashMap的 API 熟练运用并理解T: Eq Hash泛型约束与entry优化背后的设计动机。【免费下载链接】comprehensive-rustThis is the Rust course used by the Android team at Google. It provides you the material to quickly teach Rust.项目地址: https://gitcode.com/GitHub_Trending/co/comprehensive-rust创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 comprehensive-rust 课程精讲：标准库 HashMap 的插入、查询与防 HashDoS 设计
comprehensive-rust 课程精讲标准库 HashMap 的插入、查询与防 HashDoS 设计【免费下载链接】comprehensive-rustThis is the Rust course used by the Android team at Google. It provides you the material to quickly teach Rust.项目地址: https://gitcode.com/GitHub_Trending/co/comprehensive-rust导读本文围绕 Google Android 团队维护的开源 Rust 课程 comprehensive-rust 中「Standard Library Types」章节的HashMap一讲即 src/std-types/hashmap.md展开系统讲解std::collections::HashMap的引入方式、增删查改的常用 API、基于entry的原子式「查无则插」惯用法、以及从数组字面量与迭代器构造哈希表的高级写法。文中还结合课程配套的 Counter 练习 与 参考答案展示如何用HashMap与entry实现一个通用计数器帮助你同时掌握标准库容器的实战用法与 Rust 泛型设计思路。课程定位HashMap在 comprehensive-rust 中的位置comprehensive-rust 是 Google Android 团队用于快速教授 Rust 的课程材料见仓库根目录 README.md其标准库类型Standard Library Types章节由 src/std-types.md 统领依次覆盖std/core/alloc分层、Option、Result、String、Vec与HashMap目录结构见 src/SUMMARY.md。关于标准库分层课程在 src/std-types/std.md 中强调core最基础的类型与函数不依赖libc、分配器甚至操作系统alloc依赖全局堆分配器的类型如Vec、Box、Arcstd完整标准库。嵌入式 Rust 通常只用core有时加alloc。HashMap属于std层内部分配在堆上正因如此它默认不在预导入prelude中需要显式use std::collections::HashMap;才能使用。在课程大纲中HashMap一讲紧接Vecsrc/std-types/vec.md两者都是存储在堆上、可在运行时增长收缩的集合类型但HashMap以K - V键值对形式提供 O(1) 平均复杂度的查询能力是后续 Counter 练习 的基础。HashMap是什么带 HashDoS 防护的标准哈希表课程对HashMap的一句话定义是Standard hash map with protection against HashDoS attacks.即它是标准库提供的哈希表实现并且内置了对 HashDoS哈希碰撞拒绝服务攻击的防护。这意味着默认情况下HashMap使用带随机种子的哈希算法随机种子在每次创建哈希表时生成攻击者难以预先构造大量碰撞键来拖慢查找性能。需要确定性哈希的场景如进程内缓存、特定算法可以改用HashMap::with_hasher传入自定义Hasher但课程默认示例均使用标准默认实现。课程给出的完整示例src/std-types/hashmap.md一次覆盖了插入、查询、遍历与更新四种基本操作use std::collections::HashMap; fn main() { let mut page_counts HashMap::new(); page_counts.insert(Adventures of Huckleberry Finn, 207); page_counts.insert(Grimms Fairy Tales, 751); page_counts.insert(Pride and Prejudice, 303); if !page_counts.contains_key(Les Misérables) { println!( We know about {} books, but not Les Misérables., page_counts.len() ); } for book in [Pride and Prejudice, Alices Adventure in Wonderland] { match page_counts.get(book) { Some(count) println!({book}: {count} pages), None println!({book} is unknown.), } } // Use the .entry() method to insert a value if nothing is found. for book in [Pride and Prejudice, Alices Adventure in Wonderland] { let page_count: mut i32 page_counts.entry(book).or_insert(0); *page_count 1; } dbg!(page_counts); }关键 API 一览API作用返回值HashMap::new()创建空哈希表HashMapK, Vinsert(k, v)插入键值对若键已存在则覆盖OptionV返回旧值contains_key(k)判断键是否存在boolget(k)按键取值OptionVlen()返回键值对数量usizeentry(k)获取键的入口可查可插Entry配合or_insert/or_default使用keys()/values()迭代键 / 值Keys/Values等专用迭代器类型从 prelude 到作用域为什么必须显式use课程明确提醒src/std-types/hashmap.mdHashMapis not defined in the prelude and needs to be brought into scope.Rust 的 prelude 只预导入少数最常用的类型如Vec、String、Option、ResultHashMap不在其中因此直接写HashMap::new()会编译报错。必须通过use std::collections::HashMap;将其引入作用域或者在使用时写全路径std::collections::HashMap::new()。这一点与课程前面的VecVec也在 prelude 中但vec!宏、Vec::with_capacity等行为不同形成对照Vec无需use而HashMap必须显式引入——这也是初学标准库容器时常遇到的第一个编译错误来源。get与contains_key安全查询绝不 panic课程示例展示了两种查询方式contains_key(k)只返回bool适合仅判断存在性get(k)返回OptionV配合match可以优雅处理存在/不存在两种分支for book in [Pride and Prejudice, Alices Adventure in Wonderland] { match page_counts.get(book) { Some(count) println!({book}: {count} pages), None println!({book} is unknown.), } }与Vec使用[索引]越界会 panic 不同见 src/std-types/vec.md 的注意事项HashMap::get天然返回Option把键不存在变成可处理的状态而不是程序崩溃。这正是课程反复强调的 Rust 风格用类型系统表达失败可能性调用方必须显式处理None。如果想查不到就用一个默认值可以用unwrap_orlet pc1 page_counts .get(Harry Potter and the Sorcerers Stone) .unwrap_or(336);注意get返回的是V因此unwrap_or的参数需要传引用336。entryAPI一次查找完成「查无则插」课程给出的第二个关键技巧src/std-types/hashmap.md是entrylet pc2 page_counts .entry(The Hunger Games) .or_insert(374);语义是如果键存在entry返回对该键对应值的可变引用如果键不存在则先插入给定的默认值再返回其可变引用。因此entry(...).or_insert(default)把检查键是否存在 插入默认值合并为一次哈希查找既简洁又高效。课程示例中还展示了如何用entry做计数累加for book in [Pride and Prejudice, Alices Adventure in Wonderland] { let page_count: mut i32 page_counts.entry(book).or_insert(0); *page_count 1; }配合or_default()还能用零值自动初始化这一惯用法在 Counter 练习中会进一步发挥威力。构造哈希表hashmap!宏的缺席与替代方案课程特别指出src/std-types/hashmap.mdUnlikevec!, there is unfortunately no standardhashmap!macro.Vec有vec![...]宏但标准库并没有对应的hashmap!宏。不过自 Rust 1.56 起HashMap实现了From[(K, V); N]因此可以直接从数组字面量构造let page_counts HashMap::from([ (Harry Potter and the Sorcerers Stone.to_string(), 336), (The Hunger Games.to_string(), 374), ]);注意这里的键类型是String需要调用.to_string()转换如果直接写str字面量键的存活期与借用关系需要仔细处理。此外HashMap也可以由任意产出(K, V)元组的迭代器构造例如iter().collect()let page_counts: HashMapString, i32 some_pairs.into_iter().collect();这为从数据流聚合出映射提供了统一入口。方法专属返回类型Keys、Values等课程提醒src/std-types/hashmap.mdHashMap有若干方法专属的返回类型例如std::collections::hash_map::Keys、Values、Iter等。这些类型在 Rust 文档搜索中频繁出现例如keys()返回Keys_, K, V。它们本质上是借用哈希表内部存储的迭代器视图通常不必显式写出类型交给类型推断即可但在阅读 Rust 文档、查看函数签名时理解这类方法专属类型能显著降低困惑。实战延伸Counter 练习——把u32计数器泛型化HashMap一讲的配套练习是 src/std-types/exercise.md20 分钟中的 Counter该练习使用std::collections::HashMap记录见过哪些值、每个值出现过多少次。初始版本被硬编码为只能统计u32请把结构体与方法泛型化使其可以统计任意类型的值。如果提前完成尝试用entry方法把count方法所需的哈希查找次数减半。初始代码编译失败版本如下其count使用了先contains_key再get_mut/insert的两步写法use std::collections::HashMap; /// Counter counts the number of times each value of type T has been seen. struct Counter { values: HashMapu32, u64, } impl Counter { /// Create a new Counter. fn new() - Self { Counter { values: HashMap::new(), } } /// Count an occurrence of the given value. fn count(mut self, value: u32) { if self.values.contains_key(value) { *self.values.get_mut(value).unwrap() 1; } else { self.values.insert(value, 1); } } /// Return the number of times the given value has been seen. fn times_seen(self, value: u32) - u64 { self.values.get(value).copied().unwrap_or_default() } }课程给出的参考答案位于 src/std-types/exercise.rs核心改动有三点结构体泛型化struct CounterT { values: HashMapT, u64 }约束T: Eq HashHashMap的键必须满足Eq Hash因此impl块需要声明implT: Eq Hash CounterT用entry合并查找/// Count an occurrence of the given value. fn count(mut self, value: T) { *self.values.entry(value).or_default() 1; }一次entry调用同时完成查与插0 值再通过解引用累加把初始版本中contains_keyget_mut或insert的最多两次查找压缩为一次正是练习提示要求的优化方向。而times_seen保持get(...).copied().unwrap_or_default()未见过时返回 0/// Return the number of times the given value has been seen. fn times_seen(self, value: T) - u64 { self.values.get(value).copied().unwrap_or_default() }main中同时用整数与str两种键类型验证了泛型效果src/std-types/exercise.rsString等标准类型均已实现Eq Hash可直接作为键。本地运行与验证方式课程把HashMap讲解与练习组织在独立的 Cargo 包中src/std-types/Cargo.toml其二进制目标名为hashset入口即exercise.rs对应的 Bazel 构建配置src/std-types/BUILD.bazel同时定义了rust_binary与rust_test两个目标直接运行cargo run在该目录下或 Bazel 的bazel run //src/std-types:hashset跑测试cargo test或bazel test //src/std-types:hashset_test。需要说明的是文章正文中的HashMap示例代码块带有课程特有的editable/ignore/compile_fail标注前者可在 mdbook 环境中直接编辑运行compile_fail标注表示该版本故意无法编译用于引出泛型化改造。小结回顾 src/std-types/hashmap.md 的核心要点HashMap是标准库哈希表内置 HashDoS 防护但不在 prelude 中必须显式use std::collections::HashMap;查询使用get返回OptionV与contains_key返回bool不会因缺键而 panicentry(key).or_insert(default)/or_default()是查无则插与计数累加的标准惯用法一次哈希查找完成读写标准库没有hashmap!宏但 Rust 1.56 起可用HashMap::from([(k, v), ...])或由(K, V)元组迭代器collect得到keys()/values()等方法返回std::collections::hash_map::Keys等方法专属迭代器类型阅读文档时需留意。配合 Counter 练习 与 参考答案你就能把HashMap的 API 熟练运用并理解T: Eq Hash泛型约束与entry优化背后的设计动机。【免费下载链接】comprehensive-rustThis is the Rust course used by the Android team at Google. It provides you the material to quickly teach Rust.项目地址: https://gitcode.com/GitHub_Trending/co/comprehensive-rust创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考