用什么惯用方式制作查找表，该表使用项目字段作为键？

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的get()方法来解决问题（Playground）：

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 集合来根据不同的字段进行键控？

- colinfang

---

如果可能的话， HashMap 暴露了一个接口会不安全; get_mut 就是一个例子（如果可以调用此方法且值拥有它们的键，则可能会使地图无效）。 具有安全接口的解决方案将必须以某种方式防止这种情况发生。 - trent

@trentcl 有点过于追求严谨了，但按 Rust 的定义来说，这只是一个逻辑错误，而不是 不安全的。 - Shepmaster

@Shepmaster太晚了，无法编辑，但你绝对是正确的。也许“不稳定”会更好一些——我对该术语的语义感到有些摇摆不定。 - trent

Answer 1

显然，如果不通过引入Rc或克隆/复制k来重新设计Foo，则不可能实现。 是的，无法拥有HashMap<&K，V>，其中键指向值的某个组件。 HashMap在概念上拥有键和值，并将两者存储在大向量中。当向HashMap添加新值时，由于哈希冲突或向量需要重新分配以容纳更多项，这些现有值可能需要移动。这两种操作都会使任何现有键的地址无效，从而使其指向无效内存。这将破坏Rust的安全性保证，因此被禁止。阅读为什么无法在同一结构体中存储值和对该值的引用？进行深入讨论。

此外，trentcl指出 HashMap::get_mut 可以让您获得对key的可变引用，这将允许您更改键而不让映射知道。正如文档所述：

在这样的情况下修改键，即由 Hash 特征确定的键的哈希值或由 Eq 特征确定的相等性发生变化，这是一种逻辑错误。

---

解决方法包括：

• 从结构中移除关键字并单独存储。不要使用 HashMap<&K, V>，而是使用 HashMap<K, Data>。您可以返回一个将关键字和值的引用粘合在一起的结构体（示例）

• 使用 Rc 共享关键字的所有权（示例）

• 使用 Clone 或 Copy 创建重复的关键字。

• 像您所做的那样使用 HashSet，并采用 Sebastian Redl 建议 的增强版。 HashSet<K> 实际上只是一个 HashMap<K, ()>，因此通过将所有权转移到关键字来实现。

- Shepmaster

Answer 2

你可以为存储在集合中的项引入一个包装类型。

struct FooByK(Foo);

然后为此结构体实现所需的各种特性，而不是为其设置。这样，如果需要按不同成员索引的集合，则可以选择不同的包装类型。

- Sebastian Redl

---

我通常也主张创建一个“key”内在方法，从中调用“Eq”、“Ord”和其他相关方法，以减少它们不同步的机会。 - Shepmaster