|
|
|
|
|
<!DOCTYPE HTML>
|
|
|
|
|
|
<html lang="zh-CN" class="light sidebar-visible" dir="ltr">
|
|
|
|
|
|
<head>
|
|
|
|
|
|
<!-- Book generated using mdBook -->
|
|
|
|
|
|
<meta charset="UTF-8">
|
|
|
|
|
|
<title>KV 存储 HashMap - Rust语言圣经(Rust Course)</title>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
<!-- Custom HTML head -->
|
|
|
|
|
|
|
|
|
|
|
|
<meta name="description" content="">
|
|
|
|
|
|
<meta name="viewport" content="width=device-width, initial-scale=1">
|
|
|
|
|
|
<meta name="theme-color" content="#ffffff">
|
|
|
|
|
|
|
|
|
|
|
|
<link rel="icon" href="../../favicon.svg">
|
|
|
|
|
|
<link rel="shortcut icon" href="../../favicon.png">
|
|
|
|
|
|
<link rel="stylesheet" href="../../css/variables.css">
|
|
|
|
|
|
<link rel="stylesheet" href="../../css/general.css">
|
|
|
|
|
|
<link rel="stylesheet" href="../../css/chrome.css">
|
|
|
|
|
|
<link rel="stylesheet" href="../../css/print.css" media="print">
|
|
|
|
|
|
|
|
|
|
|
|
<!-- Fonts -->
|
|
|
|
|
|
<link rel="stylesheet" href="../../FontAwesome/css/font-awesome.css">
|
|
|
|
|
|
<link rel="stylesheet" href="../../fonts/fonts.css">
|
|
|
|
|
|
|
|
|
|
|
|
<!-- Highlight.js Stylesheets -->
|
|
|
|
|
|
<link rel="stylesheet" id="highlight-css" href="../../highlight.css">
|
|
|
|
|
|
<link rel="stylesheet" id="tomorrow-night-css" href="../../tomorrow-night.css">
|
|
|
|
|
|
<link rel="stylesheet" id="ayu-highlight-css" href="../../ayu-highlight.css">
|
|
|
|
|
|
|
|
|
|
|
|
<!-- Custom theme stylesheets -->
|
|
|
|
|
|
<link rel="stylesheet" href="../../theme/style.css">
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
<!-- Provide site root and default themes to javascript -->
|
|
|
|
|
|
<script>
|
|
|
|
|
|
const path_to_root = "../../";
|
|
|
|
|
|
const default_light_theme = "light";
|
|
|
|
|
|
const default_dark_theme = "navy";
|
|
|
|
|
|
</script>
|
|
|
|
|
|
<!-- Start loading toc.js asap -->
|
|
|
|
|
|
<script src="../../toc.js"></script>
|
|
|
|
|
|
</head>
|
|
|
|
|
|
<body>
|
|
|
|
|
|
<div id="body-container">
|
|
|
|
|
|
<!-- Work around some values being stored in localStorage wrapped in quotes -->
|
|
|
|
|
|
<script>
|
|
|
|
|
|
try {
|
|
|
|
|
|
let theme = localStorage.getItem('mdbook-theme');
|
|
|
|
|
|
let sidebar = localStorage.getItem('mdbook-sidebar');
|
|
|
|
|
|
|
|
|
|
|
|
if (theme.startsWith('"') && theme.endsWith('"')) {
|
|
|
|
|
|
localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
|
|
|
|
|
|
localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
|
|
|
|
|
|
}
|
|
|
|
|
|
} catch (e) { }
|
|
|
|
|
|
</script>
|
|
|
|
|
|
|
|
|
|
|
|
<!-- Set the theme before any content is loaded, prevents flash -->
|
|
|
|
|
|
<script>
|
|
|
|
|
|
const default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? default_dark_theme : default_light_theme;
|
|
|
|
|
|
let theme;
|
|
|
|
|
|
try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
|
|
|
|
|
|
if (theme === null || theme === undefined) { theme = default_theme; }
|
|
|
|
|
|
const html = document.documentElement;
|
|
|
|
|
|
html.classList.remove('light')
|
|
|
|
|
|
html.classList.add(theme);
|
|
|
|
|
|
html.classList.add("js");
|
|
|
|
|
|
</script>
|
|
|
|
|
|
|
|
|
|
|
|
<input type="checkbox" id="sidebar-toggle-anchor" class="hidden">
|
|
|
|
|
|
|
|
|
|
|
|
<!-- Hide / unhide sidebar before it is displayed -->
|
|
|
|
|
|
<script>
|
|
|
|
|
|
let sidebar = null;
|
|
|
|
|
|
const sidebar_toggle = document.getElementById("sidebar-toggle-anchor");
|
|
|
|
|
|
if (document.body.clientWidth >= 1080) {
|
|
|
|
|
|
try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
|
|
|
|
|
|
sidebar = sidebar || 'visible';
|
|
|
|
|
|
} else {
|
|
|
|
|
|
sidebar = 'hidden';
|
|
|
|
|
|
}
|
|
|
|
|
|
sidebar_toggle.checked = sidebar === 'visible';
|
|
|
|
|
|
html.classList.remove('sidebar-visible');
|
|
|
|
|
|
html.classList.add("sidebar-" + sidebar);
|
|
|
|
|
|
</script>
|
|
|
|
|
|
|
|
|
|
|
|
<nav id="sidebar" class="sidebar" aria-label="Table of contents">
|
|
|
|
|
|
<!-- populated by js -->
|
|
|
|
|
|
<mdbook-sidebar-scrollbox class="sidebar-scrollbox"></mdbook-sidebar-scrollbox>
|
|
|
|
|
|
<noscript>
|
|
|
|
|
|
<iframe class="sidebar-iframe-outer" src="../../toc.html"></iframe>
|
|
|
|
|
|
</noscript>
|
|
|
|
|
|
<div id="sidebar-resize-handle" class="sidebar-resize-handle">
|
|
|
|
|
|
<div class="sidebar-resize-indicator"></div>
|
|
|
|
|
|
</div>
|
|
|
|
|
|
</nav>
|
|
|
|
|
|
|
|
|
|
|
|
<div id="page-wrapper" class="page-wrapper">
|
|
|
|
|
|
|
|
|
|
|
|
<div class="page">
|
|
|
|
|
|
<div id="menu-bar-hover-placeholder"></div>
|
|
|
|
|
|
<div id="menu-bar" class="menu-bar sticky">
|
|
|
|
|
|
<div class="left-buttons">
|
|
|
|
|
|
<label id="sidebar-toggle" class="icon-button" for="sidebar-toggle-anchor" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
|
|
|
|
|
|
<i class="fa fa-bars"></i>
|
|
|
|
|
|
</label>
|
|
|
|
|
|
<button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
|
|
|
|
|
|
<i class="fa fa-paint-brush"></i>
|
|
|
|
|
|
</button>
|
|
|
|
|
|
<ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
|
|
|
|
|
|
<li role="none"><button role="menuitem" class="theme" id="default_theme">Auto</button></li>
|
|
|
|
|
|
<li role="none"><button role="menuitem" class="theme" id="light">Light</button></li>
|
|
|
|
|
|
<li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
|
|
|
|
|
|
<li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
|
|
|
|
|
|
<li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
|
|
|
|
|
|
<li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
|
|
|
|
|
|
</ul>
|
|
|
|
|
|
<button id="search-toggle" class="icon-button" type="button" title="Search. (Shortkey: s)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="S" aria-controls="searchbar">
|
|
|
|
|
|
<i class="fa fa-search"></i>
|
|
|
|
|
|
</button>
|
|
|
|
|
|
</div>
|
|
|
|
|
|
|
|
|
|
|
|
<h1 class="menu-title">Rust语言圣经(Rust Course)</h1>
|
|
|
|
|
|
|
|
|
|
|
|
<div class="right-buttons">
|
|
|
|
|
|
<a href="../../print.html" title="Print this book" aria-label="Print this book">
|
|
|
|
|
|
<i id="print-button" class="fa fa-print"></i>
|
|
|
|
|
|
</a>
|
|
|
|
|
|
<a href="https://github.com/sunface/rust-course" title="Git repository" aria-label="Git repository">
|
|
|
|
|
|
<i id="git-repository-button" class="fa fa-github"></i>
|
|
|
|
|
|
</a>
|
|
|
|
|
|
<a href="https://github.com/sunface/rust-course/edit/main/src/basic/collections/hashmap.md" title="Suggest an edit" aria-label="Suggest an edit">
|
|
|
|
|
|
<i id="git-edit-button" class="fa fa-edit"></i>
|
|
|
|
|
|
</a>
|
|
|
|
|
|
|
|
|
|
|
|
</div>
|
|
|
|
|
|
</div>
|
|
|
|
|
|
|
|
|
|
|
|
<div id="search-wrapper" class="hidden">
|
|
|
|
|
|
<form id="searchbar-outer" class="searchbar-outer">
|
|
|
|
|
|
<input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
|
|
|
|
|
|
</form>
|
|
|
|
|
|
<div id="searchresults-outer" class="searchresults-outer hidden">
|
|
|
|
|
|
<div id="searchresults-header" class="searchresults-header"></div>
|
|
|
|
|
|
<ul id="searchresults">
|
|
|
|
|
|
</ul>
|
|
|
|
|
|
</div>
|
|
|
|
|
|
</div>
|
|
|
|
|
|
|
|
|
|
|
|
<!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
|
|
|
|
|
|
<script>
|
|
|
|
|
|
document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
|
|
|
|
|
|
document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
|
|
|
|
|
|
Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
|
|
|
|
|
|
link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
|
|
|
|
|
|
});
|
|
|
|
|
|
</script>
|
|
|
|
|
|
|
|
|
|
|
|
<div id="content" class="content">
|
|
|
|
|
|
<main>
|
|
|
|
|
|
<h1 id="kv-存储-hashmap"><a class="header" href="#kv-存储-hashmap">KV 存储 HashMap</a></h1>
|
|
|
|
|
|
<p>和动态数组一样，<code>HashMap</code> 也是 Rust 标准库中提供的集合类型，但是又与动态数组不同，<code>HashMap</code> 中存储的是一一映射的 <code>KV</code> 键值对，并提供了平均复杂度为 <code>O(1)</code> 的查询方法，当我们希望通过一个 <code>Key</code> 去查询值时，该类型非常有用，以致于 Go 语言将该类型设置成了语言级别的内置特性。</p>
|
|
|
|
|
|
<p>Rust 中哈希类型（哈希映射）为 <code>HashMap<K,V></code>，在其它语言中，也有类似的数据结构，例如 <code>hash map</code>，<code>map</code>，<code>object</code>，<code>hash table</code>，<code>字典</code> 等等，引用小品演员孙涛的一句台词：大家都是本地狐狸，别搁那装貂 :)。</p>
|
|
|
|
|
|
<h2 id="创建-hashmap"><a class="header" href="#创建-hashmap">创建 HashMap</a></h2>
|
|
|
|
|
|
<p>跟创建动态数组 <code>Vec</code> 的方法类似，可以使用 <code>new</code> 方法来创建 <code>HashMap</code>，然后通过 <code>insert</code> 方法插入键值对。</p>
|
|
|
|
|
|
<h3 id="使用-new-方法创建"><a class="header" href="#使用-new-方法创建">使用 new 方法创建</a></h3>
|
|
|
|
|
|
<pre><pre class="playground"><code class="language-rust edition2021"><span class="boring">#![allow(unused)]
|
|
|
|
|
|
</span><span class="boring">fn main() {
|
|
|
|
|
|
</span>use std::collections::HashMap;
|
|
|
|
|
|
|
|
|
|
|
|
// 创建一个HashMap，用于存储宝石种类和对应的数量
|
|
|
|
|
|
let mut my_gems = HashMap::new();
|
|
|
|
|
|
|
|
|
|
|
|
// 将宝石类型和对应的数量写入表中
|
|
|
|
|
|
my_gems.insert("红宝石", 1);
|
|
|
|
|
|
my_gems.insert("蓝宝石", 2);
|
|
|
|
|
|
my_gems.insert("河边捡的误以为是宝石的破石头", 18);
|
|
|
|
|
|
<span class="boring">}</span></code></pre></pre>
|
|
|
|
|
|
<p>很简单对吧？跟其它语言没有区别，聪明的同学甚至能够猜到该 <code>HashMap</code> 的类型：<code>HashMap<&str,i32></code>。</p>
|
|
|
|
|
|
<p>但是还有一点，你可能没有注意，那就是使用 <code>HashMap</code> 需要手动通过 <code>use ...</code> 从标准库中引入到我们当前的作用域中来，仔细回忆下，之前使用另外两个集合类型 <code>String</code> 和 <code>Vec</code> 时，我们是否有手动引用过？答案是 <strong>No</strong>，因为 <code>HashMap</code> 并没有包含在 Rust 的 <a href="https://course.rs/appendix/prelude.html"><code>prelude</code></a> 中（Rust 为了简化用户使用，提前将最常用的类型自动引入到作用域中）。</p>
|
|
|
|
|
|
<p>所有的集合类型都是动态的，意味着它们没有固定的内存大小，因此它们底层的数据都存储在内存堆上，然后通过一个存储在栈中的引用类型来访问。同时，跟其它集合类型一致，<code>HashMap</code> 也是内聚性的，即所有的 <code>K</code> 必须拥有同样的类型，<code>V</code> 也是如此。</p>
|
|
|
|
|
|
<blockquote>
|
|
|
|
|
|
<p>跟 <code>Vec</code> 一样，如果预先知道要存储的 <code>KV</code> 对个数，可以使用 <code>HashMap::with_capacity(capacity)</code> 创建指定大小的 <code>HashMap</code>，避免频繁的内存分配和拷贝，提升性能。</p>
|
|
|
|
|
|
</blockquote>
|
|
|
|
|
|
<h3 id="使用迭代器和-collect-方法创建"><a class="header" href="#使用迭代器和-collect-方法创建">使用迭代器和 collect 方法创建</a></h3>
|
|
|
|
|
|
<p>在实际使用中，不是所有的场景都能 <code>new</code> 一个哈希表后，然后悠哉悠哉的依次插入对应的键值对，而是可能会从另外一个数据结构中，获取到对应的数据，最终生成 <code>HashMap</code>。</p>
|
|
|
|
|
|
<p>例如考虑一个场景，有一张表格中记录了足球联赛中各队伍名称和积分的信息，这张表如果被导入到 Rust 项目中，一个合理的数据结构是 <code>Vec<(String, u32)></code> 类型，该数组中的元素是一个个元组，该数据结构跟表格数据非常契合：表格中的数据都是逐行存储，每一个行都存有一个 <code>(队伍名称, 积分)</code> 的信息。</p>
|
|
|
|
|
|
<p>但是在很多时候，又需要通过队伍名称来查询对应的积分，此时动态数组就不适用了，因此可以用 <code>HashMap</code> 来保存相关的<strong>队伍名称 -> 积分</strong>映射关系。 理想很丰满，现实很骨感，如何将 <code>Vec<(String, u32)></code> 中的数据快速写入到 <code>HashMap<String, u32></code> 中？</p>
|
|
|
|
|
|
<p>一个动动脚趾头就能想到的笨方法如下：</p>
|
|
|
|
|
|
<pre><pre class="playground"><code class="language-rust edition2021">fn main() {
|
|
|
|
|
|
use std::collections::HashMap;
|
|
|
|
|
|
|
|
|
|
|
|
let teams_list = vec![
|
|
|
|
|
|
("中国队".to_string(), 100),
|
|
|
|
|
|
("美国队".to_string(), 10),
|
|
|
|
|
|
("日本队".to_string(), 50),
|
|
|
|
|
|
];
|
|
|
|
|
|
|
|
|
|
|
|
let mut teams_map = HashMap::new();
|
|
|
|
|
|
for team in &teams_list {
|
|
|
|
|
|
teams_map.insert(&team.0, team.1);
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
println!("{:?}",teams_map)
|
|
|
|
|
|
}</code></pre></pre>
|
|
|
|
|
|
<p>遍历列表，将每一个元组作为一对 <code>KV </code>插入到 <code>HashMap</code> 中，很简单，但是……也不太聪明的样子，换个词说就是 —— 不够 rusty。</p>
|
|
|
|
|
|
<p>好在，Rust 为我们提供了一个非常精妙的解决办法：先将 <code>Vec</code> 转为迭代器，接着通过 <code>collect</code> 方法，将迭代器中的元素收集后，转成 <code>HashMap</code>：</p>
|
|
|
|
|
|
<pre><pre class="playground"><code class="language-rust edition2021">fn main() {
|
|
|
|
|
|
use std::collections::HashMap;
|
|
|
|
|
|
|
|
|
|
|
|
let teams_list = vec![
|
|
|
|
|
|
("中国队".to_string(), 100),
|
|
|
|
|
|
("美国队".to_string(), 10),
|
|
|
|
|
|
("日本队".to_string(), 50),
|
|
|
|
|
|
];
|
|
|
|
|
|
|
|
|
|
|
|
let teams_map: HashMap<_,_> = teams_list.into_iter().collect();
|
|
|
|
|
|
|
|
|
|
|
|
println!("{:?}",teams_map)
|
|
|
|
|
|
}</code></pre></pre>
|
|
|
|
|
|
<p>代码很简单，<code>into_iter</code> 方法将列表转为迭代器，接着通过 <code>collect</code> 进行收集，不过需要注意的是，<code>collect</code> 方法在内部实际上支持生成多种类型的目标集合，因此我们需要通过类型标注 <code>HashMap<_,_></code> 来告诉编译器：请帮我们收集为 <code>HashMap</code> 集合类型，具体的 <code>KV</code> 类型，麻烦编译器您老人家帮我们推导。</p>
|
|
|
|
|
|
<p>由此可见，Rust 中的编译器时而小聪明，时而大聪明，不过好在，它大聪明的时候，会自家人知道自家事，总归会通知你一声：</p>
|
|
|
|
|
|
<pre><code class="language-console">error[E0282]: type annotations needed // 需要类型标注
|
|
|
|
|
|
--> src/main.rs:10:9
|
|
|
|
|
|
|
|
|
|
|
|
|
10 | let teams_map = teams_list.into_iter().collect();
|
|
|
|
|
|
| ^^^^^^^^^ consider giving `teams_map` a type // 给予 `teams_map` 一个具体的类型
|
|
|
|
|
|
</code></pre>
|
|
|
|
|
|
<h2 id="所有权转移"><a class="header" href="#所有权转移">所有权转移</a></h2>
|
|
|
|
|
|
<p><code>HashMap</code> 的所有权规则与其它 Rust 类型没有区别：</p>
|
|
|
|
|
|
<ul>
|
|
|
|
|
|
<li>若类型实现 <code>Copy</code> 特征，该类型会被复制进 <code>HashMap</code>，因此无所谓所有权</li>
|
|
|
|
|
|
<li>若没实现 <code>Copy</code> 特征，所有权将被转移给 <code>HashMap</code> 中</li>
|
|
|
|
|
|
</ul>
|
|
|
|
|
|
<p>例如我参选帅气男孩时的场景再现：</p>
|
|
|
|
|
|
<pre><pre class="playground"><code class="language-rust edition2021">fn main() {
|
|
|
|
|
|
use std::collections::HashMap;
|
|
|
|
|
|
|
|
|
|
|
|
let name = String::from("Sunface");
|
|
|
|
|
|
let age = 18;
|
|
|
|
|
|
|
|
|
|
|
|
let mut handsome_boys = HashMap::new();
|
|
|
|
|
|
handsome_boys.insert(name, age);
|
|
|
|
|
|
|
|
|
|
|
|
println!("因为过于无耻，{}已经被从帅气男孩名单中除名", name);
|
|
|
|
|
|
println!("还有，他的真实年龄远远不止{}岁", age);
|
|
|
|
|
|
}</code></pre></pre>
|
|
|
|
|
|
<p>运行代码，报错如下：</p>
|
|
|
|
|
|
<pre><code class="language-console">error[E0382]: borrow of moved value: `name`
|
|
|
|
|
|
--> src/main.rs:10:32
|
|
|
|
|
|
|
|
|
|
|
|
|
4 | let name = String::from("Sunface");
|
|
|
|
|
|
| ---- move occurs because `name` has type `String`, which does not implement the `Copy` trait
|
|
|
|
|
|
...
|
|
|
|
|
|
8 | handsome_boys.insert(name, age);
|
|
|
|
|
|
| ---- value moved here
|
|
|
|
|
|
9 |
|
|
|
|
|
|
10 | println!("因为过于无耻，{}已经被除名", name);
|
|
|
|
|
|
| ^^^^ value borrowed here after move
|
|
|
|
|
|
</code></pre>
|
|
|
|
|
|
<p>提示很清晰，<code>name</code> 是 <code>String</code> 类型，因此它受到所有权的限制，在 <code>insert</code> 时，它的所有权被转移给 <code>handsome_boys</code>，所以最后在使用时，会遇到这个无情但是意料之中的报错。</p>
|
|
|
|
|
|
<p><strong>如果你使用引用类型放入 HashMap 中</strong>，请确保该引用的生命周期至少跟 <code>HashMap</code> 活得一样久：</p>
|
|
|
|
|
|
<pre><pre class="playground"><code class="language-rust edition2021">fn main() {
|
|
|
|
|
|
use std::collections::HashMap;
|
|
|
|
|
|
|
|
|
|
|
|
let name = String::from("Sunface");
|
|
|
|
|
|
let age = 18;
|
|
|
|
|
|
|
|
|
|
|
|
let mut handsome_boys = HashMap::new();
|
|
|
|
|
|
handsome_boys.insert(&name, age);
|
|
|
|
|
|
|
|
|
|
|
|
std::mem::drop(name);
|
|
|
|
|
|
println!("因为过于无耻，{:?}已经被除名", handsome_boys);
|
|
|
|
|
|
println!("还有，他的真实年龄远远不止{}岁", age);
|
|
|
|
|
|
}</code></pre></pre>
|
|
|
|
|
|
<p>上面代码，我们借用 <code>name</code> 获取了它的引用，然后插入到 <code>handsome_boys</code> 中，至此一切都很完美。但是紧接着，就通过 <code>drop</code> 函数手动将 <code>name</code> 字符串从内存中移除，再然后就报错了：</p>
|
|
|
|
|
|
<pre><code class="language-console"> handsome_boys.insert(&name, age);
|
|
|
|
|
|
| ----- borrow of `name` occurs here // name借用发生在此处
|
|
|
|
|
|
9 |
|
|
|
|
|
|
10 | std::mem::drop(name);
|
|
|
|
|
|
| ^^^^ move out of `name` occurs here // name的所有权被转移走
|
|
|
|
|
|
11 | println!("因为过于无耻，{:?}已经被除名", handsome_boys);
|
|
|
|
|
|
| ------------- borrow later used here // 所有权转移后，还试图使用name
|
|
|
|
|
|
</code></pre>
|
|
|
|
|
|
<p>最终，某人因为过于无耻，真正的被除名了 :)</p>
|
|
|
|
|
|
<h2 id="查询-hashmap"><a class="header" href="#查询-hashmap">查询 HashMap</a></h2>
|
|
|
|
|
|
<p>通过 <code>get</code> 方法可以获取元素：</p>
|
|
|
|
|
|
<pre><pre class="playground"><code class="language-rust edition2021"><span class="boring">#![allow(unused)]
|
|
|
|
|
|
</span><span class="boring">fn main() {
|
|
|
|
|
|
</span>use std::collections::HashMap;
|
|
|
|
|
|
|
|
|
|
|
|
let mut scores = HashMap::new();
|
|
|
|
|
|
|
|
|
|
|
|
scores.insert(String::from("Blue"), 10);
|
|
|
|
|
|
scores.insert(String::from("Yellow"), 50);
|
|
|
|
|
|
|
|
|
|
|
|
let team_name = String::from("Blue");
|
|
|
|
|
|
let score: Option<&i32> = scores.get(&team_name);
|
|
|
|
|
|
<span class="boring">}</span></code></pre></pre>
|
|
|
|
|
|
<p>上面有几点需要注意：</p>
|
|
|
|
|
|
<ul>
|
|
|
|
|
|
<li><code>get</code> 方法返回一个 <code>Option<&i32></code> 类型：当查询不到时，会返回一个 <code>None</code>，查询到时返回 <code>Some(&i32)</code></li>
|
|
|
|
|
|
<li><code>&i32</code> 是对 <code>HashMap</code> 中值的借用，如果不使用借用，可能会发生所有权的转移</li>
|
|
|
|
|
|
<li><code>get</code> 方法的 <code>key</code> 参数必须是一个引用，如这里的 <code>scores.get(&team_name)</code>，这是因为 <code>HashMap<K, V></code> 的 <code>get</code> 方法的签名如下：</li>
|
|
|
|
|
|
</ul>
|
|
|
|
|
|
<pre><pre class="playground"><code class="language-rust edition2021"><span class="boring">#![allow(unused)]
|
|
|
|
|
|
</span><span class="boring">fn main() {
|
|
|
|
|
|
</span>impl<K, V> HashMap<K, V>
|
|
|
|
|
|
where
|
|
|
|
|
|
K: Eq + Hash,
|
|
|
|
|
|
{
|
|
|
|
|
|
pub fn get<Q>(&self, k: &Q) -> Option<&V>
|
|
|
|
|
|
where
|
|
|
|
|
|
K: Borrow<Q>,
|
|
|
|
|
|
Q: Hash + Eq + ?Sized,
|
|
|
|
|
|
{ ... }
|
|
|
|
|
|
}
|
|
|
|
|
|
<span class="boring">}</span></code></pre></pre>
|
|
|
|
|
|
<ul>
|
|
|
|
|
|
<li>可以看到签名中的 <code>k: &Q</code>。下面的特征约束 <code>K: Borrow<Q></code> 是指类型 <code>K</code> 需要能以另一种形式 <code>Q</code> 被借用。在这种情况下，<code>String</code> 实现了 <code>Borrow<str></code>，所以 <code>&String</code> 和 <code>&str</code> 类型都可以用于 <code>get</code> 方法。</li>
|
|
|
|
|
|
</ul>
|
|
|
|
|
|
<p>还可以继续拓展下，上面的代码中，如果我们想直接获得值类型的 <code>score</code> 该怎么办，答案简约但不简单：</p>
|
|
|
|
|
|
<pre><pre class="playground"><code class="language-rust edition2021"><span class="boring">#![allow(unused)]
|
|
|
|
|
|
</span><span class="boring">fn main() {
|
|
|
|
|
|
</span>let score: i32 = scores.get(&team_name).copied().unwrap_or(0);
|
|
|
|
|
|
<span class="boring">}</span></code></pre></pre>
|
|
|
|
|
|
<p>这里留给大家一个小作业：去官方文档中查询下 <code>Option</code> 的 <code>copied</code> 方法和 <code>unwrap_or</code> 方法的含义及该如何使用。</p>
|
|
|
|
|
|
<p>还可以通过循环的方式依次遍历 <code>KV</code> 对：</p>
|
|
|
|
|
|
<pre><pre class="playground"><code class="language-rust edition2021"><span class="boring">#![allow(unused)]
|
|
|
|
|
|
</span><span class="boring">fn main() {
|
|
|
|
|
|
</span>use std::collections::HashMap;
|
|
|
|
|
|
|
|
|
|
|
|
let mut scores = HashMap::new();
|
|
|
|
|
|
|
|
|
|
|
|
scores.insert(String::from("Blue"), 10);
|
|
|
|
|
|
scores.insert(String::from("Yellow"), 50);
|
|
|
|
|
|
|
|
|
|
|
|
for (key, value) in &scores {
|
|
|
|
|
|
println!("{}: {}", key, value);
|
|
|
|
|
|
}
|
|
|
|
|
|
<span class="boring">}</span></code></pre></pre>
|
|
|
|
|
|
<p>最终输出：</p>
|
|
|
|
|
|
<pre><code class="language-console">Yellow: 50
|
|
|
|
|
|
Blue: 10
|
|
|
|
|
|
</code></pre>
|
|
|
|
|
|
<h2 id="更新-hashmap-中的值"><a class="header" href="#更新-hashmap-中的值">更新 HashMap 中的值</a></h2>
|
|
|
|
|
|
<p>更新值的时候，涉及多种情况，咱们在代码中一一进行说明：</p>
|
|
|
|
|
|
<pre><pre class="playground"><code class="language-rust edition2021">fn main() {
|
|
|
|
|
|
use std::collections::HashMap;
|
|
|
|
|
|
|
|
|
|
|
|
let mut scores = HashMap::new();
|
|
|
|
|
|
|
|
|
|
|
|
scores.insert("Blue", 10);
|
|
|
|
|
|
|
|
|
|
|
|
// 覆盖已有的值
|
|
|
|
|
|
let old = scores.insert("Blue", 20);
|
|
|
|
|
|
assert_eq!(old, Some(10));
|
|
|
|
|
|
|
|
|
|
|
|
// 查询新插入的值
|
|
|
|
|
|
let new = scores.get("Blue");
|
|
|
|
|
|
assert_eq!(new, Some(&20));
|
|
|
|
|
|
|
|
|
|
|
|
// 查询Yellow对应的值，若不存在则插入新值
|
|
|
|
|
|
let v = scores.entry("Yellow").or_insert(5);
|
|
|
|
|
|
assert_eq!(*v, 5); // 不存在，插入5
|
|
|
|
|
|
|
|
|
|
|
|
// 查询Yellow对应的值，若不存在则插入新值
|
|
|
|
|
|
let v = scores.entry("Yellow").or_insert(50);
|
|
|
|
|
|
assert_eq!(*v, 5); // 已经存在，因此50没有插入
|
|
|
|
|
|
}</code></pre></pre>
|
|
|
|
|
|
<p>具体的解释在代码注释中已有，这里不再进行赘述。</p>
|
|
|
|
|
|
<h4 id="在已有值的基础上更新"><a class="header" href="#在已有值的基础上更新">在已有值的基础上更新</a></h4>
|
|
|
|
|
|
<p>另一个常用场景如下：查询某个 <code>key</code> 对应的值，若不存在则插入新值，若存在则对已有的值进行更新，例如在文本中统计词语出现的次数：</p>
|
|
|
|
|
|
<pre><pre class="playground"><code class="language-rust edition2021"><span class="boring">#![allow(unused)]
|
|
|
|
|
|
</span><span class="boring">fn main() {
|
|
|
|
|
|
</span>use std::collections::HashMap;
|
|
|
|
|
|
|
|
|
|
|
|
let text = "hello world wonderful world";
|
|
|
|
|
|
|
|
|
|
|
|
let mut map = HashMap::new();
|
|
|
|
|
|
// 根据空格来切分字符串(英文单词都是通过空格切分)
|
|
|
|
|
|
for word in text.split_whitespace() {
|
|
|
|
|
|
let count = map.entry(word).or_insert(0);
|
|
|
|
|
|
*count += 1;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
println!("{:?}", map);
|
|
|
|
|
|
<span class="boring">}</span></code></pre></pre>
|
|
|
|
|
|
<p>上面代码中，新建一个 <code>map</code> 用于保存词语出现的次数，插入一个词语时会进行判断：若之前没有插入过，则使用该词语作 <code>Key</code>，插入次数 0 作为 <code>Value</code>，若之前插入过则取出之前统计的该词语出现的次数，对其加一。</p>
|
|
|
|
|
|
<p>有两点值得注意：</p>
|
|
|
|
|
|
<ul>
|
|
|
|
|
|
<li><code>or_insert</code> 返回了 <code>&mut v</code> 引用，因此可以通过该可变引用直接修改 <code>map</code> 中对应的值</li>
|
|
|
|
|
|
<li>使用 <code>count</code> 引用时，需要先进行解引用 <code>*count</code>，否则会出现类型不匹配</li>
|
|
|
|
|
|
</ul>
|
|
|
|
|
|
<h2 id="哈希函数"><a class="header" href="#哈希函数">哈希函数</a></h2>
|
|
|
|
|
|
<p>你肯定比较好奇，为何叫哈希表，到底什么是哈希。</p>
|
|
|
|
|
|
<p>先来设想下，如果要实现 <code>Key</code> 与 <code>Value</code> 的一一对应，是不是意味着我们要能比较两个 <code>Key</code> 的相等性？例如 "a" 和 "b"，1 和 2，当这些类型做 <code>Key</code> 且能比较时，可以很容易知道 <code>1</code> 对应的值不会错误的映射到 <code>2</code> 上，因为 <code>1</code> 不等于 <code>2</code>。因此，一个类型能否作为 <code>Key</code> 的关键就是是否能进行相等比较，或者说该类型是否实现了 <code>std::cmp::Eq</code> 特征。</p>
|
|
|
|
|
|
<blockquote>
|
|
|
|
|
|
<p>f32 和 f64 浮点数，没有实现 <code>std::cmp::Eq</code> 特征，因此不可以用作 <code>HashMap</code> 的 <code>Key</code>。</p>
|
|
|
|
|
|
</blockquote>
|
|
|
|
|
|
<p>好了，理解完这个，再来设想一点，若一个复杂点的类型作为 <code>Key</code>，那怎么在底层对它进行存储，怎么使用它进行查询和比较？ 是不是很棘手？好在我们有哈希函数：通过它把 <code>Key</code> 计算后映射为哈希值，然后使用该哈希值来进行存储、查询、比较等操作。</p>
|
|
|
|
|
|
<p>但是问题又来了，如何保证不同 <code>Key</code> 通过哈希后的两个值不会相同？如果相同，那意味着我们使用不同的 <code>Key</code>，却查到了同一个结果，这种明显是错误的行为。
|
|
|
|
|
|
此时，就涉及到安全性跟性能的取舍了。</p>
|
|
|
|
|
|
<p>若要追求安全，尽可能减少冲突，同时防止拒绝服务（Denial of Service, DoS）攻击，就要使用密码学安全的哈希函数，<code>HashMap</code> 就是使用了这样的哈希函数。反之若要追求性能，就需要使用没有那么安全的算法。</p>
|
|
|
|
|
|
<h4 id="高性能三方库"><a class="header" href="#高性能三方库">高性能三方库</a></h4>
|
|
|
|
|
|
<p>因此若性能测试显示当前标准库默认的哈希函数不能满足你的性能需求，就需要去 <a href="https://crates.io"><code>crates.io</code></a> 上寻找其它的哈希函数实现，使用方法很简单：</p>
|
|
|
|
|
|
<pre><pre class="playground"><code class="language-rust edition2021"><span class="boring">#![allow(unused)]
|
|
|
|
|
|
</span><span class="boring">fn main() {
|
|
|
|
|
|
</span>use std::hash::BuildHasherDefault;
|
|
|
|
|
|
use std::collections::HashMap;
|
|
|
|
|
|
// 引入第三方的哈希函数
|
|
|
|
|
|
use twox_hash::XxHash64;
|
|
|
|
|
|
|
|
|
|
|
|
// 指定HashMap使用第三方的哈希函数XxHash64
|
|
|
|
|
|
let mut hash: HashMap<_, _, BuildHasherDefault<XxHash64>> = Default::default();
|
|
|
|
|
|
hash.insert(42, "the answer");
|
|
|
|
|
|
assert_eq!(hash.get(&42), Some(&"the answer"));
|
|
|
|
|
|
<span class="boring">}</span></code></pre></pre>
|
|
|
|
|
|
<blockquote>
|
|
|
|
|
|
<p>目前，<code>HashMap</code> 使用的哈希函数是 <code>SipHash</code>，它的性能不是很高，但是安全性很高。<code>SipHash</code> 在中等大小的 <code>Key</code> 上，性能相当不错，但是对于小型的 <code>Key</code> （例如整数）或者大型 <code>Key</code> （例如字符串）来说，性能还是不够好。若你需要极致性能，例如实现算法，可以考虑这个库：<a href="https://github.com/tkaitchuck/ahash">ahash</a>。</p>
|
|
|
|
|
|
</blockquote>
|
|
|
|
|
|
<p>最后，如果你想要了解 <code>HashMap</code> 更多的用法，请参见本书的标准库解析章节：<a href="https://course.rs/std/hashmap.html">HashMap 常用方法</a></p>
|
|
|
|
|
|
<h2 id="课后练习"><a class="header" href="#课后练习">课后练习</a></h2>
|
|
|
|
|
|
<blockquote>
|
|
|
|
|
|
<p><a href="https://practice-zh.course.rs/collections/hashmap.html">Rust By Practice</a>，支持代码在线编辑和运行，并提供详细的<a href="https://github.com/sunface/rust-by-practice/blob/master/solutions/collections/Hashmap.md">习题解答</a>。</p>
|
|
|
|
|
|
</blockquote>
|
|
|
|
|
|
|
|
|
|
|
|
</main>
|
|
|
|
|
|
|
|
|
|
|
|
<nav class="nav-wrapper" aria-label="Page navigation">
|
|
|
|
|
|
<!-- Mobile navigation buttons -->
|
|
|
|
|
|
<a rel="prev" href="../../basic/collections/vector.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
|
|
|
|
|
|
<i class="fa fa-angle-left"></i>
|
|
|
|
|
|
</a>
|
|
|
|
|
|
|
|
|
|
|
|
<a rel="next prefetch" href="../../basic/lifetime.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
|
|
|
|
|
|
<i class="fa fa-angle-right"></i>
|
|
|
|
|
|
</a>
|
|
|
|
|
|
|
|
|
|
|
|
<div style="clear: both"></div>
|
|
|
|
|
|
</nav>
|
|
|
|
|
|
</div>
|
|
|
|
|
|
</div>
|
|
|
|
|
|
|
|
|
|
|
|
<nav class="nav-wide-wrapper" aria-label="Page navigation">
|
|
|
|
|
|
<a rel="prev" href="../../basic/collections/vector.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
|
|
|
|
|
|
<i class="fa fa-angle-left"></i>
|
|
|
|
|
|
</a>
|
|
|
|
|
|
|
|
|
|
|
|
<a rel="next prefetch" href="../../basic/lifetime.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
|
|
|
|
|
|
<i class="fa fa-angle-right"></i>
|
|
|
|
|
|
</a>
|
|
|
|
|
|
</nav>
|
|
|
|
|
|
|
|
|
|
|
|
</div>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
<script>
|
|
|
|
|
|
window.playground_copyable = true;
|
|
|
|
|
|
</script>
|
|
|
|
|
|
|
|
|
|
|
|
<script src="../../ace.js"></script>
|
|
|
|
|
|
<script src="../../editor.js"></script>
|
|
|
|
|
|
<script src="../../mode-rust.js"></script>
|
|
|
|
|
|
<script src="../../theme-dawn.js"></script>
|
|
|
|
|
|
<script src="../../theme-tomorrow_night.js"></script>
|
|
|
|
|
|
|
|
|
|
|
|
<script src="../../elasticlunr.min.js"></script>
|
|
|
|
|
|
<script src="../../mark.min.js"></script>
|
|
|
|
|
|
<script src="../../searcher.js"></script>
|
|
|
|
|
|
|
|
|
|
|
|
<script src="../../clipboard.min.js"></script>
|
|
|
|
|
|
<script src="../../highlight.js"></script>
|
|
|
|
|
|
<script src="../../book.js"></script>
|
|
|
|
|
|
|
|
|
|
|
|
<!-- Custom JS scripts -->
|
|
|
|
|
|
<script src="../../assets/custom2.js"></script>
|
|
|
|
|
|
<script src="../../assets/bigPicture.js"></script>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
</div>
|
|
|
|
|
|
</body>
|
|
|
|
|
|
</html>
|
