rust - 制作使用项目字段作为键的查找表的惯用方法是什么？

Question

我有一个 Foo 的集合。

struct Foo {
    k: String,
    v: String,
}

我想要一个 HashMap，它有键 &foo.k 和值 foo。

显然，如果不通过引入 Rc 或克隆/复制 k 来重新设计 Foo 是不可能的。

fn t1() {
    let foo = Foo { k: "k".to_string(), v: "v".to_string() };
    let mut a: HashMap<&str, Foo> = HashMap::new();
    a.insert(&foo.k, foo); // Error
}

似乎可以通过滥用 HashSet ( Playground ) 中的 get() 来解决:

use std::collections::{HashMap, HashSet};
use std::hash::{Hash, Hasher, BuildHasher};
use std::collections::hash_map::Entry::*;

struct Foo {
    k: String,
    v: String,
}

impl PartialEq for Foo {
    fn eq(&self, other: &Self) -> bool { self.k == other.k }
}

impl Eq for Foo {}

impl Hash for Foo {
    fn hash<H: Hasher>(&self, h: &mut H) { self.k.hash(h); }
}

impl ::std::borrow::Borrow<str> for Foo {
    fn borrow(&self) -> &str {
        self.k.as_str()
    }
}

fn t2() {
    let foo = Foo { k: "k".to_string(), v: "v".to_string() };
    let mut a: HashSet<Foo> = HashSet::new();
    a.insert(foo);
    let bar = Foo { k: "k".to_string(), v: "v".to_string() };
    let foo = a.get("k").unwrap();
    println!("{}", foo.v);
}

这很乏味。如果一个 Foo 有多个字段和不同的 Foo 集合来键入不同的字段怎么办？

Answer 1

Apparently, it is not possible without redesigning Foo by introducing Rc or clone/copy the k.

没错，HashMap<&K, V> 是不可能的其中键指向值的某个组成部分。

HashMap拥有键和值，概念上将两者都存储在大向量中。当向 HashMap 添加新值时，这些现有值可能需要由于散列冲突而四处移动或向量可能需要重新分配以容纳更多项目。这两个操作都会使任何现有 key 的地址无效，使其指向无效内存。这会破坏 Rust 的安全保证，因此是不允许的。

阅读Why can't I store a value and a reference to that value in the same struct?进行彻底的讨论。

此外，trentcl points out那 HashMap::get_mut 将允许您获得对键 的可变引用，这将允许您在 map 不知道的情况下更改键。正如文档所述:

It is a logic error for a key to be modified in such a way that the key's hash, as determined by the Hash trait, or its equality, as determined by the Eq trait, changes while it is in the map.

---

解决方法包括:

• 从结构中删除键并单独存储。而不是 HashMap<&K, V>其中 V 是 (K, Data) , 商店 HashMap<K, Data> .您可以返回一个将对键和值的引用粘合在一起的结构 (example)

• 使用 Rc 共享 key 所有权(example)

• 使用 Clone 创建重复键或 Copy .

• 使用 HashSet正如您所做的那样，由 Sebastian Redl's suggestion 增强. HashSet<K>实际上只是一个HashMap<K, ()> ，所以这通过将所有所有权转移到 key 来实现。