作为一种学习练习,我想try 制作一种 map 类型(EQ.HashMap),它有多个键,可以用几种不同的方式查找值.我以为我有一个很好的解决方案,但我很快就发现了一个明显的漏洞:

use std::borrow::Borrow;
use std::collections::HashMap;

/// Values used as keys in a Map, e.g. `HashMap<Key, _>`.
#[derive(Clone, Debug, Eq, Hash, PartialEq)]
struct Key {
    session_id: usize,
    screen_name: String,
}

/// Different ways to look up a value in a Map keyed by `Key`.
///
/// Each variant must constitute a unique index.
#[derive(Clone, Debug, Eq, Hash, PartialEq)]
enum KeyQuery<'s> {
    SessionId(usize),
    ScreenName(&'s str),
}

impl<'s> Borrow<KeyQuery<'s>> for Key {
    fn borrow(&self) -> &KeyQuery<'s> {
        // ???
    }
}

fn main() {
    let mut map: HashMap<Key, ()> = HashMap::new();
    map.insert(
        Key {
            session_id: 1248,
            screen_name: "nombe_hombre".to_string(),
        },
        (),
    );

    // Look up values by either field of Key.
    map.get(&KeyQuery::SessionId(1248));
    map.get(&KeyQuery::ScreenName("nombre_hombre"));
}

简单地说,你很容易告诉拉斯特:"如果你需要一张KeyQuery::SessionId,这里有从Key借一张的方法."KeyQuery::ScreenName的情况也是如此.有没有一种合理的方式来用代码来表达这一点?我不确定我是遗漏了什么明显的东西,还是遇到了类型系统的限制(可能是故意的).

Trait objects?

我已经保存了相关的问题How To Implement Hash Map With Two Keys?以备将来阅读.当我简单地通读它时,我发现自己有点超出了我的理解范围.我可以开始想象如何用实现PartialEqEqHashKey的每个字段的方法编写一个简单的特征.不过,我不确定这是不是正确/最佳的答案.我希望有一种更直接的方法.

Just use a database?

我知道这是在突破合理的极限,简单地查询数据库可能更有意义.我仍然想学习如何最好地用铁 rust 来直接表达这个 idea .

推荐答案

有一个根本的障碍阻碍了它的工作,这不是由于铁 rust 的任何东西.元素的哈希图查询的方法是对您搜索的键进行哈希处理,以派生出一些索引,该索引将直接(或接近直接-哈希图算法不同)指向元素现在或将要位于的位置.这意味着您要用来查询的任何键的散列必须与您要查找的存储键的散列匹配.

为了在您想要的 struct 中工作,session_idscreen_name都必须散列到exact same valueKey,以满足来自散列图的期望.这在一般情况下是不可能的(除非您有一个本质上返回常量的糟糕的散列算法,但是散列映射根本没有好处).

在Rust中,您可以看到Borrow的文档中表达了这个概念,该文档用于HashMap::get(重点是我的):

此外,在提供附加特征的实现时,需要考虑它们是否应该作为底层类型的表示的结果而表现为底层类型的identically行为.当泛型代码依赖于这些额外的特征实现中的identical behavior个时,它通常使用Borrow<T>.这些特征可能会作为额外的特征界限出现.

特别是,对于借入和拥有的价值,100, 101 and 102 must be equivalent:x.borrow() == y.borrow()应该会得到与x == y相同的结果.

How To Implement Hash Map With Two Keys?的答案中的技巧仍然有效,因为在查询时总是使用both个键,只是引用的 struct 不同.这在这种情况下是行不通的.


用多个查找方法表示一个哈希图的方法是有多个哈希图(通常指的是共享值,以避免重复数据).

Rust相关问答推荐

如何优化小型固定大小数组中的搜索?

程序退出后只写入指定管道的数据

在rust中如何修改一个盒装函数并将其赋回?

为什么幻影数据不能自动推断?

何时可以在Rust中退出异步操作?

这种获取-释放关系是如何运作的?

如何在 struct 的自定义序列化程序中使用serde序列化_WITH

捕获FnMut闭包的时间不够长

函数内模块的父作用域的访问类型

重写Rust中的方法以使用`&;mut self`而不是`mut self`

我们可以在 Rust 切片中使用步骤吗?

decltype、dyn、impl traits,重构时如何声明函数的返回类型

在给定 Rust 谓词的情况下,将 Some 转换为 None 的惯用方法是什么?

为什么 `tokio::join!` 宏不需要 Rust 中的 `await` 关键字?

如何将这些测试放在一个单独的文件中?

是否可以预测堆栈溢出?

第 7.4 章片段中如何定义 `thread_rng`

为什么 match 语句对引用类型比函数参数更挑剔?

为什么这个值在上次使用后没有下降?

覆盖类型的要求到底是什么?为什么单个元素元组满足它?