Как избежать временных распределений при использовании сложного ключа для HashMap?

Я использую сложный ключ для HashMap, так что ключ состоит из двух частей, а одна часть - 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 Standard Library 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, но у меня полная потеря.

Ответы

Ответ 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());
}

Комментарий о параметрах времени жизни:

Если вам не нравится параметр времени жизни и вам нужно работать только с &'static str или String, тогда вы можете использовать Cow<'static, str> и удалить другие параметры времени жизни из блока impl и определения структуры.

Ответ 2

Вы можете следовать идеям, описанным в Как реализовать HashMap с двумя ключами?. Здесь ответ "заимствованный признак" применяется к вашему делу:

Создайте черту, которую мы можем использовать в качестве общей цели Borrow:

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

Реализуйте черты HashMap -required для объекта черты:

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)
    }
}

Полный код на детской площадке