basic/collections/hashmap

[giscus[bot]]

basic/collections/hashmap

https://course.rs/basic/collections/hashmap.html

[Rustln]

本篇还漏了一个很重要的知识点，HashMap 的兄弟 BTreeMap，前者是无序，后者是有序的。

[sunface]

应该放在标准库里，因为不是绝大多数人需要的。

[violin0622]

说的是。
另外链表，红黑树等复杂又常用的数据结构竟然没有放在标准库中简直离谱。

[yuyongmao]

BTreeMap是不是比特币用到了

[sweet2honey]

理想很骨感，现实很丰满
有没有写反了呀哈哈

[ZLD1819858]

有没有可能是：理想（的rust）很骨感，现实（的rust）太他妈丰满了

[jinliming2]

国足牛逼！！！

_{（这，这，脸都……}

[liwuhou]

不要了

[jinliming2]

如果发生哈希碰撞了，会发生什么？
旧值被意外更改吗？
还是说类似于哈希链表那样，所有 key 都存成链表，碰撞的 key 在链表上追加存储，不碰撞的时候是 O(1) 直接访问，碰撞的话就在链表上再去挨个搜索？

[clee01]

个人理解应该是 “旧值发生意外更改”

[Saltedf]

见 开链法 / 开放地址

[Almagestum469]

key 都存成红黑树, 碰撞的 key 在红黑树上追加存储

[violin0622]

例如 hash map，map，object，hash table，字典 等等，

字典直接用原名比较好吧。
以及名称也应该用对应语言中的类型名比较好吧。

例如 HashMap(Java), HashTable(Java),Object(javascript), Dict(Python) 等等。

[BreakingLead]

还有Lua的Table

[DeusSeuca]

C#的Dictionary

[Wyatex]

在js感觉是map准确一点，object的key只能是string

[weizhenhuan]

第二段代码为什么team.0加了借用，team.1没加？

[crescentBLADE]

因为遍历的式teams_list的引用，而team.0是String类型，没有实现Copy特征；也可以把team_list前的引用去掉，直接转让所有权，也可以编译通过

[realHakeen]

根据我的理解，存储是根据最小精度的类型来看的。string是在堆上，而i32在栈上，如果直接赋值（也就是所有权转移）的过程中，string是浅拷贝，i32栈上是默认深拷贝，因此一切涉及到堆类型，都需要记得加借用。其实rust是很统一的，比如说为什么我们的默认类型是&str切片？因为本身string是动态存储在堆上，但是我们系统默认所有类型都尽量存储在栈上，这也是为什么我们输入一个字符串，自动类型判定&str。其实这里面涉及两个知识点，所有权/堆栈问题。

[hdzhangzhe]

"SipHash 在中等大小的 Key 上，性能相当不错，但是对于小型的 Key （例如整数）或者大型 Key （例如字符串）来说，性能还是不够好" 大中小有评判的标准吗？

[oceangakki]

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)

}
为什么这段代码每次输出都不一样？
输出顺序会出现差别。
{"美国队":10，"中国队":100，"日本队":50}
{"美国队":10，"日本队":50，"中国队":100}

[ruaruagerry]

因为遍历hash的结果是无序的

[oceangakki]

恍然大悟！感谢。

[ZLD1819858]

感谢！还没注意到这一点

[zoloadang]

在 rust 里遍历结果无序性貌似跟 go 语言中一样

[tiancheng92]

go 里面 原本取出来是有序的，为了不让开发者依赖索引去取值特意引入了随机数取打乱了map的顺序，不知道rust底层是怎么样的。。。

[wxzcyy]

没有删除

[wsjswy]

HashMap 是线程安全的吗

[doge-ak]

所有的都是默认线程安全

[qianxiaoming]

这个能选择吗？默认都安全岂不是默认都有同步锁的调用负担？

[Lixuhuilll]

rust默认的线程安全，是指当你的代码可能被多个线程同时修改，或者读取和修改可能同时发生时，不可能通过编译，这种线程安全是不依靠线程锁的，同时存在上述那种严重限制。你可以自行加锁让多个线程去读写。

[iceonfirek]

课后练习第二题第一个方案跑不通， let teams = vec![...]; 加了vec!就可以了

[cddsgtc]

好家伙，直接对value修改，够暴力。

[JackySu]

let a: Option<i32> = Some(5);
let b = a.copy(); // b is now Some(5)

let a: Result<i32, String> = Ok(5);
let b = a.copied(); // b is now Ok(5)

copy 和 copied最大区别是一个是Some()一个是Ok()

let x: Option<i32> = Some(5);
let y: i32 = x.unwrap(); // y is now 5

let z: Result<i32, &str> = Ok(10);
let w: i32 = z.unwrap(); // w is now 10

let x: Option<i32> = None;
let y: i32 = x.unwrap_or(10); // y is now 10

let z: Result<i32, &str> = Err("Error message");
let w: i32 = z.unwrap_or(20); // w is now 20

unwrap()就是要么给我结果要么panic，unwrap_or()给你一个default值，前者不推荐使用

let x: Option<i32> = None;
let y: i32 = x.unwrap_or_else(|| {
    // Some complex computation that returns a default value
    100
}); // y is now 100

let z: Result<i32, &str> = Err("Error message");
let w: i32 = z.unwrap_or_else(|| {
    // Some complex computation that returns a default value
    200
}); // w is now 200

unwrap_or_else()你可以写一个闭包函数
出自chatgpt

[Kev1n3zz]

通过循环遍历键值对的方式这个地方的打印结果反了。
原来为

Yellow: 50
Blue: 10

应该为

Blue: 10
Yellow: 50

[tiancheng92]

HashMap 无序的...

[web4zn]

练习2的collection解法为什么会报错，没看懂

C:\Users\yoga>rustc -V
rustc 1.69.0 (84c898d65 2023-04-16)

use std::collections::HashMap;
fn main() {
    let teams = [
        ("Chinese Team", 100),
        ("American Team", 10),
        ("France Team", 50),
    ];

    let mut teams_map1 = HashMap::new();
    for team in &teams {
        teams_map1.insert(team.0, team.1);
    }

    let teams_map2: HashMap<_,_> = teams.into_iter().collect();

    assert_eq!(teams_map1, teams_map2);

    println!("Success!")
}

error[E0277]: a value of type `HashMap<_, _>` cannot be built from an iterator over elements of type `&(&str, {integer})`
    --> main.rs:14:54
     |
14   |     let teams_map2: HashMap<_,_> = teams.into_iter().collect();
     |                                                      ^^^^^^^ value of type `HashMap<_, _>` cannot be built from `std::iter::Iterator<Item=&(&str, {integer})>`
     |
     = help: the trait `FromIterator<&(&str, {integer})>` is not implemented for `HashMap<_, _>`
     = help: the trait `FromIterator<(K, V)>` is implemented for `HashMap<K, V, S>`
note: the method call chain might not have had the expected associated types
    --> main.rs:14:42
     |
3    |       let teams = [
     |  _________________-
4    | |         ("Chinese Team", 100),
5    | |         ("American Team", 10),
6    | |         ("France Team", 50),
7    | |     ];
     | |_____- this expression has type `[(&str, {integer}); 3]`
...
14   |       let teams_map2: HashMap<_,_> = teams.into_iter().collect();
     |                                            ^^^^^^^^^^^ `Iterator::Item` is `&(&str, {integer})` here
note: required by a bound in `collect`
    --> C:\Users\yoga\.rustup\toolchains\stable-x86_64-pc-windows-msvc\lib/rustlib/src/rust\library\core\src\iter\traits\iterator.rs:1887:19
     |
1887 |     fn collect<B: FromIterator<Self::Item>>(self) -> B
     |                   ^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `Iterator::collect`

error: aborting due to previous error

For more information about this error, try `rustc --explain E0277`.

[Wyatex]

1.75没报错，可能是你的版本太老了？

[qq143626]

let red = scores.entry(String::from("Red")).or_insert(0);
println!("{}", red);
println!("{:?}", scores);
println!("{}", red);
为什么第二次输出red的时候会有借用问题，这四行代码不应该都是可变借用么

[smallevilbeast]

一旦你调用 println!("{:?}", scores);，scores 就被借用为不可变的

[smallevilbeast]

违反了 Rust 的借用规则：你不能在不可变引用仍在作用范围内的情况下，创建一个可变引用

[smallevilbeast]

Rust 的借用规则是这样的：

1. 你可以有许多不可变引用（只读）。
2. 或者，你可以有一个可变引用（读/写）。
3. 但是你不能同时拥有可变引用和不可变引用。

在你的情况下，当你执行 println!("{:?}", scores);，scores 被不可变借用直到打印操作完成。在这期间，你不能对 scores 创建一个可变引用。即使 println!("{}", red); 并不会改变 red，但是 red 依然是 scores 的一个可变引用，这就违反了上述的第3条规则。因此，你需要等待 scores 的打印操作完成（即，对 scores 的不可变借用结束），然后再执行 println!("{}", red);。

即使这些打印操作并不是并发的，Rust 的借用规则仍然适用，因为这些规则旨在防止数据竞争和其他并发问题，即使在单线程上下文中也是如此。

[zhitaoli-6]

"好在我们有哈希函数：通过它把 Key 计算后映射为哈希值，然后使用该哈希值来进行存储、查询、比较等操作。

但是问题又来了，如何保证不同 Key 通过哈希后的两个值不会相同？如果相同，那意味着我们使用不同的 Key，却查到了同一个结果，这种明显是错误的行为。 此时，就涉及到安全性跟性能的取舍了。"

似乎作者理解的不太对，HashMap的Hash算法不需要保证“不同Key通过Hash后值不相同”。“不同Key的Hash相同”就是Hash碰撞，是HashMap的正常情况。

Hash碰撞不可能避免：Value有无限种可能；而64位Hash值也只能表达2^64种情况。

[zhitaoli-6]

Hash碰撞不可能避免：Key有无限种可能；而64位Hash值也只能表达2^64种情况。

[minminm]

关于Option中的copied和cloned方法的区别，可以参考源码实现

 #[must_use = "`self` will be dropped if the result is not used"]
    #[stable(feature = "copied", since = "1.35.0")]
    #[rustc_const_unstable(feature = "const_option", issue = "67441")]
    pub const fn copied(self) -> Option<T>
    where
        T: Copy,
    {
        // FIXME: this implementation, which sidesteps using `Option::map` since it's not const
        // ready yet, should be reverted when possible to avoid code repetition
        match self {
            Some(&v) => Some(v),
            None => None,
        }
    }

    /// Maps an `Option<&T>` to an `Option<T>` by cloning the contents of the
    /// option.
    ///
    /// # Examples
    ///
    /// ```
    /// let x = 12;
    /// let opt_x = Some(&x);
    /// assert_eq!(opt_x, Some(&12));
    /// let cloned = opt_x.cloned();
    /// assert_eq!(cloned, Some(12));
    /// ```
    #[must_use = "`self` will be dropped if the result is not used"]
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn cloned(self) -> Option<T>
    where
        T: Clone,
    {
        match self {
            Some(t) => Some(t.clone()),
            None => None,
        }
    }

[DylanJinx]

在 Rust 中，Option 类型是一个非常常用的枚举，它用于表示一个值可能存在也可能不存在。Option<T> 可以是 Some(T)，表示包含了一个类型为 T 的值，或者是 None，表示没有值。这个枚举通常用于安全地处理可能缺失的值，而不必使用空指针。

copied() 方法

copied() 方法是 Option 的一个方法，它用于 Option<&T> 类型的变量，其中 T 实现了 Copy trait。这个方法会尝试将 Option 中的引用复制为一个新的 Option 实例，里面包含被引用值的拷贝。这意味着，如果 Option 是 Some(&T)，它将变成 Some(T)；如果是 None，则仍然是 None。

let x = Some(&5);
let y = x.copied(); // y 的类型是 Option<i32>，值为 Some(5)

unwrap_or() 方法

unwrap_or() 方法用于处理 Option 类型的值，提供了一种在 Option 是 None 时提供默认值的方式。这个方法接受一个参数，这个参数是当 Option 是 None 时要返回的值。如果 Option 是 Some，它将返回包含的值。

let x = Some(10);
let y = None;

let a = x.unwrap_or(0);  // a 的值是 10，因为 x 是 Some(10)
let b = y.unwrap_or(0);  // b 的值是 0，因为 y 是 None

使用场景

在你的代码中：

let score: i32 = scores.get(&team_name).copied().unwrap_or(0);

这段代码的含义是：

1. scores.get(&team_name) 尝试从一个 HashMap 中获取与 team_name 关联的分数。get 方法返回的是 Option<&V> 类型，其中 V 是 HashMap 中值的类型。

2. .copied() 用于将得到的 Option<&i32> 转换为 Option<i32>，即如果存在值，就将它从引用复制为一个值。

3. .unwrap_or(0) 用于处理 Option<i32>：如果 Option 是 Some(i32)，则返回其内部的 i32 值；如果是 None（即 team_name 不在 HashMap 中），则返回 0 作为默认值。

这样的用法有效地避免了潜在的空值引用问题，并为缺失的数据提供了一个合理的默认值。

[DylanJinx]

是的，在 Rust 的 HashMap 中使用 insert 方法时，如果插入的键（key）已经存在于 HashMap 中，那么新的值（value）将会替换掉原有的值，并且 insert 方法会返回之前与该键关联的旧值包装在 Option 中。如果之前的键没有关联的值，则返回 None。

这里是一个具体的例子来说明这个行为：

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();
    
    // 插入键为 "key1" 的值 "value1"
    map.insert("key1", "value1");
    println!("{:?}", map);  // 输出: {"key1": "value1"}
    
    // 再次插入键为 "key1" 的新值 "value2"
    let old_value = map.insert("key1", "value2");
    println!("{:?}", map);  // 输出: {"key1": "value2"}
    println!("{:?}", old_value); // 输出: Some("value1")
}

在这个例子中，第二次调用 insert 时，我们插入了相同的键 "key1" 但是值是 "value2"。因此，原来的值 "value1" 被 "value2" 替换掉了，且 insert 方法返回了 Some("value1")，表示之前这个键有一个关联的值。

这种行为使得 HashMap 可以很容易地更新键所对应的值。

[yu244]

请问一下哈希函数和 dos 攻击有什么联系

[chq8191562]

teams_list.into_iter().collect()
就这段代码，看它的调用链，我花了半个小时，不过收益真的很大，建议在看过全书后，在第二遍看的时候搭配看rust的源代码，会有更多收益