如何在为HashMap使用复杂键时避免临时分配？

Question

我正在使用一个复杂的密钥,HashMap使得密钥包含两个部分,一个部分是a String,我无法弄清楚如何通过该HashMap::get方法进行查找而不String为每个查找分配新的.

这是一些代码:

#[derive(Debug, Eq, Hash, PartialEq)]
struct Complex {
    n: i32,
    s: String,
}

impl Complex {
    fn new<S: Into<String>>(n: i32, s: S) -> Self {
        Complex { n: n, s: s.into() }
    }
}

fn main() {
    let mut m = std::collections::HashMap::<Complex, i32>::new();
    m.insert(Complex::new(42, "foo"), 123);

    // OK, but allocates temporary String
    assert_eq!(123, *m.get(&Complex::new(42, "foo")).unwrap());
}

问题出在最后的断言上.它通过,但它需要临时堆分配,因为我不能构造一个Complex没有构造一个String.

为了消除这样的临时分配,Rust提供了Borrow该HashMap::get方法使用的特征.我理解如何Borrow为简单的键工作.例如,Rust标准库的PathBuf实现Borrow<Path>通过使用std::mem::transmute引擎盖,但我无法弄清楚如何使它适用于我的Complex类型:

#[derive(Debug)]
struct Borrowable {
    // ??? -- What goes here? Perhaps something like:
    n: i32,
    s1: &str, // ??? -- But what would the lifetime be? Or maybe:
    s2: str,  // ??? -- But how would I extend this to a complex type
              //        containing two or more strings?
}

impl Borrowable {
    fn new(n: i32, s: &str) -> &Self {
         // ??? -- What goes here? It must not allocate.
        unimplemented!();
    }
}

impl std::borrow::Borrow<Borrowable> for Complex {
    fn borrow(&self) -> &Borrowable {
        // ??? -- What goes here? How can I transmute a Complex into a
        //        &Borrowable?
        unimplemented!();
    }
}

这似乎是一个常见的用例,我怀疑我错过了一些重要的事情Borrow,但我完全失去了.

Answer 1

听起来你想要这个.

Cow会接受一个&str或String.

use std::borrow::Cow;

#[derive(Debug, Eq, Hash, PartialEq)]
struct Complex<'a> {
    n: i32,
    s: Cow<'a, str>,
}

impl<'a> Complex<'a> {
    fn new<S: Into<Cow<'a, str>>>(n: i32, s: S) -> Self {
        Complex { n: n, s: s.into() }
    }
}

fn main() {
    let mut m = std::collections::HashMap::<Complex<'_>, i32>::new();
    m.insert(Complex::new(42, "foo"), 123);

    assert_eq!(123, *m.get(&Complex::new(42, "foo")).unwrap());
}

关于生命周期参数的评论:

如果你不喜欢lifetime参数,你只需要使用&'static str或者String你可以使用Cow<'static, str>和删除impl块和结构定义中的其他生命周期参数.

Answer 2

您可以按照如何实现带有两个键的 HashMap？中描述的思路进行操作。。这是适用于您的案例的“借用特征对象”答案：

创建一个我们可以用作共同Borrow目标的特征：

trait Key {
    fn to_key(&self) -> (i32, &str);
}

HashMap为特征对象实现所需的特征：

use std::hash::{Hash, Hasher};

impl Hash for dyn Key + '_ {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.to_key().hash(state)
    }
}

impl PartialEq for dyn Key + '_ {
    fn eq(&self, other: &Self) -> bool {
        self.to_key() == other.to_key()
    }
}

impl Eq for dyn Key + '_ {}

为我们的主要类型和任何辅助查找类型实现该特征：

impl Key for Complex {
    fn to_key(&self) -> (i32, &str) {
        (self.n, &self.s)
    }
}

impl<'a> Key for (i32, &'a str) {
    fn to_key(&self) -> (i32, &str) {
        (self.0, self.1)
    }
}

为所有查找类型实现Borrow返回特征对象：

impl<'a> Borrow<dyn Key + 'a> for Complex {
    fn borrow(&self) -> &(dyn Key + 'a) {
        self
    }
}

impl<'a> Borrow<dyn Key + 'a> for (i32, &'a str) {
    fn borrow(&self) -> &(dyn Key + 'a) {
        self
    }
}

在查询时转换为特征对象：

assert_eq!(Some(&123), m.get((42, "foo").borrow() as &dyn Key));

游乐场中的完整代码

一个重要的“问题”是所有主键和辅助键必须以相同的方式进行哈希处理。这意味着相同的值需要以相同的顺序和数量进入哈希计算。

您可能希望Hash手动定义以确保您的主键和辅助键散列相同！

这是另一个例子，这次是一个枚举：

#[derive(Debug, PartialEq, Eq)]
enum ConfigKey {
    Text(String),
    Binary(Vec<u8>),
}

我们创建一个仅由引用组成的并行枚举，因此创建起来很轻量。重要的是，我们定义与主枚举相同的变体和相同的顺序，这样它们就会散列相同的值。我们依赖于这样一个事实：String和散列使用与和&str相同的算法：Vec<T>&[T]

impl ConfigKey {
    fn as_ref(&self) -> ConfigKeyRef<'_> {
        match self {
            ConfigKey::Text(t) => ConfigKeyRef::Text(t),
            ConfigKey::Binary(b) => ConfigKeyRef::Binary(b),
        }
    }
}

#[derive(Hash, PartialEq, Eq)]
enum ConfigKeyRef<'a> {
    Text(&'a str),
    Binary(&'a [u8]),
}

我们使用这个新的枚举作为我们常见的底层键类型：

trait Key {
    fn to_key(&self) -> ConfigKeyRef<'_>;
}

并为我们的主键和辅助键实现我们的特征：

impl Key for ConfigKey {
    fn to_key(&self) -> ConfigKeyRef<'_> {
        self.as_ref()
    }
}

impl<'a> Key for &'a str {
    fn to_key(&self) -> ConfigKeyRef<'_> {
        ConfigKeyRef::Text(self)
    }
}

游乐场中的完整代码