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

Question

我有一个收藏Foo。

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

我想要一个HashMap具有键&foo.k和值的键foo。

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

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
}

get()从HashSet（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在不同字段上具有不同的to键，该怎么办？

Answer 1

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

没错，不可能有HashMap<&K, V>键指向值的某个部分。

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

阅读为什么我不能在同一结构中存储值和对该值的引用？进行彻底的讨论。

此外，trentcl指出，这HashMap::get_mut将允许您获取对key的可变引用，这将允许您在不知道地图的情况下更改key。如文档所述：

以某种方式修改密钥是一种逻辑错误，即，当密钥在映射中时，由哈希特征确定的密钥哈希值或由等价特征确定的相等性会改变。

解决方法包括：

• 从结构中删除密钥并单独存储。而不是HashMap<&K, V>V 在哪里(K, Data)，存储HashMap<K, Data>。您可以返回将对键和值的引用粘合在一起的结构（示例）

• 使用密钥的股权Rc（例如）

• 使用Clone或创建重复的密钥Copy。

• HashSet像塞巴斯蒂安·雷德尔（Sebastian Redl）的建议所增强的那样，照常使用a 。A HashSet<K>实际上只是一个HashMap<K, ()>，因此这可以通过将所有所有权转让给密钥来实现。

Answer 2

您可以为集合中存储的项目引入包装类型。

struct FooByK(Foo);

然后实现该结构集所需的各种特征。如果您需要一个由不同成员索引的集合，这允许您选择不同的包装器类型。