< 返回版块

HashMap的key的临时定义

LongRiver 发表于 2023-08-26 13:34

我要使用HashMap。其中key是一个struct，其中包括了一个String类型（就是非Copy的）：

struct Key {
  uid: u64,
  name: String,
}

然后我想定义一个get函数：

fn get(dict: &HashMap, uid: u64, name: &String) -> Option<Value> {
  let key = Key { uid, name };  // <-- name.clone()?
  dict.get(&key)
}

这个函数的最后一个参数，name，我希望是&String而不是String，这样外面的调用者就不用消耗掉这个name。

然后问题就来了，在函数内部定义这个临时的key变量时，这个name怎么处理？难道要clone()吗？这个代价就太高了。

请问下，这种需求，应该怎么处理？

评论区

写评论
ribs 2023-10-17 17:23

name可否换成Cow类型

作者 LongRiver 2023-09-02 20:01

明白了！

--
👇
hangj: 也就是：如果我们实现了 Borrow<Inner> for Outer, 那么 Equivalent<Outer> for Inner 会被自动实现

hangj 2023-09-01 13:36

也就是：如果我们实现了 Borrow<Inner> for Outer, 那么 Equivalent<Outer> for Inner 会被自动实现

hangj 2023-09-01 13:32

可以编译过，因为 Equivalent 实现了这个

impl<Q: ?Sized, K: ?Sized> Equivalent<K> for Q
where
    Q: Eq,
    K: core::borrow::Borrow<Q>,
{
    fn equivalent(&self, key: &K) -> bool {
        self == key.borrow()
    }
}

所以它兼容了 Borrow 的情况，测试代码：

use std::borrow::Borrow;

#[derive(Hash, PartialEq, Eq)]
struct Outer {
    raw: Inner,
}

#[derive(Hash, PartialEq, Eq)]
struct Inner;

impl Borrow<Inner> for Outer {
    fn borrow(&self) -> &Inner {
        &self.raw
    }
}

fn main() {
    {
        // 标准库的 HashMap
        use std::collections::HashMap;

        let mut m = HashMap::new();
        m.insert(Outer{raw: Inner}, 0);
        m.get(&Inner).unwrap();
    }

    {
        // hashbrown 的 HashMap
        extern crate hashbrown;
        use hashbrown::HashMap;

        let mut m = HashMap::new();
        m.insert(Outer{raw: Inner}, 0);
        m.get(&Inner).unwrap();
    }
}

--
👇
LongRiver: 那在用户自己的app里，如果也定义了类似的Inner和Outer并且也实现了Borrow，然后在代码里用Inner作为key去调用HashMap::get()；那么如果HashMap::get()换了原型后，用户的代码也就编译不过了吧。

--
👇
hangj: 如果仔细看标准库里所有 Borrow trait 的实现（Implementors），你会发现它们都是 impl Borrow<Inner> for Outer 这种模式的，其中 Inner 和 Outer 的关系是这样:

struct Outer {
    raw: Inner,
}

struct Inner {
    // ...
}

这种情况下实现 Borrow<Inner> for Outer 很简单

impl Borrow<Inner> for Outer {
    fn borrow(&self) -> &Inner {
        &self.raw
    }
}

Borrow<str> for String Borrow<[T]> for Vec<T> 等等都是如此，从 Outer borrow 出它内部的数据而已

但是对于没有包含关系的 TmpKey 和 Key, 要实现 Borrow<TmpKey> for Key 是几乎不可能做到的

--
👇
LongRiver: 虽然难，但应该也是可以做到的吧。我看Borrow的文档里，就举了String和str的例子。

我看SO上的那个回答也说了，非常难实现Borrow。

我的意思是如果这么改，至少在理论上，是不兼容了。实际上可能会影响非常小。

--
👇
hangj: 问题是 Borrow<TmpKey> for Key 如何实现？这几乎是无法做到的。如果可以做到的话，Equavlant 就没必要存在了

--
👇
LongRiver: 我说的“原来的代码”，指的是使用了hashmap的app的代码，而不是 hashmap自己的代码。

比如我之前写了个app，使用hashmap，并且实现了 Borrow<TmpKey> for Key。

那么如果HashMap::get()的原型中参数key的约束改了，改成了Equavlant。那么我原来的app代码还能编译通过吗？

我是猜的，感觉就不会通过了。

作者 LongRiver 2023-09-01 09:30

那在用户自己的app里，如果也定义了类似的Inner和Outer并且也实现了Borrow，然后在代码里用Inner作为key去调用HashMap::get()；那么如果HashMap::get()换了原型后，用户的代码也就编译不过了吧。

--
👇
hangj: 如果仔细看标准库里所有 Borrow trait 的实现（Implementors），你会发现它们都是 impl Borrow<Inner> for Outer 这种模式的，其中 Inner 和 Outer 的关系是这样:

struct Outer {
    raw: Inner,
}

struct Inner {
    // ...
}

这种情况下实现 Borrow<Inner> for Outer 很简单

impl Borrow<Inner> for Outer {
    fn borrow(&self) -> &Inner {
        &self.raw
    }
}

Borrow<str> for String Borrow<[T]> for Vec<T> 等等都是如此，从 Outer borrow 出它内部的数据而已

但是对于没有包含关系的 TmpKey 和 Key, 要实现 Borrow<TmpKey> for Key 是几乎不可能做到的

--
👇
LongRiver: 虽然难，但应该也是可以做到的吧。我看Borrow的文档里，就举了String和str的例子。

我看SO上的那个回答也说了，非常难实现Borrow。

我的意思是如果这么改，至少在理论上，是不兼容了。实际上可能会影响非常小。

--
👇
hangj: 问题是 Borrow<TmpKey> for Key 如何实现？这几乎是无法做到的。如果可以做到的话，Equavlant 就没必要存在了

--
👇
LongRiver: 我说的“原来的代码”，指的是使用了hashmap的app的代码，而不是 hashmap自己的代码。

比如我之前写了个app，使用hashmap，并且实现了 Borrow<TmpKey> for Key。

那么如果HashMap::get()的原型中参数key的约束改了，改成了Equavlant。那么我原来的app代码还能编译通过吗？

我是猜的，感觉就不会通过了。

hangj 2023-08-31 19:03

如果仔细看标准库里所有 Borrow trait 的实现（Implementors），你会发现它们都是 impl Borrow<Inner> for Outer 这种模式的，其中 Inner 和 Outer 的关系是这样:

struct Outer {
    raw: Inner,
}

struct Inner {
    // ...
}

这种情况下实现 Borrow<Inner> for Outer 很简单

impl Borrow<Inner> for Outer {
    fn borrow(&self) -> &Inner {
        &self.raw
    }
}

Borrow<str> for String Borrow<[T]> for Vec<T> 等等都是如此，从 Outer borrow 出它内部的数据而已

但是对于没有包含关系的 TmpKey 和 Key, 要实现 Borrow<TmpKey> for Key 是几乎不可能做到的

--
👇
LongRiver: 虽然难，但应该也是可以做到的吧。我看Borrow的文档里，就举了String和str的例子。

我看SO上的那个回答也说了，非常难实现Borrow。

我的意思是如果这么改，至少在理论上，是不兼容了。实际上可能会影响非常小。

--
👇
hangj: 问题是 Borrow<TmpKey> for Key 如何实现？这几乎是无法做到的。如果可以做到的话，Equavlant 就没必要存在了

--
👇
LongRiver: 我说的“原来的代码”，指的是使用了hashmap的app的代码，而不是 hashmap自己的代码。

比如我之前写了个app，使用hashmap，并且实现了 Borrow<TmpKey> for Key。

那么如果HashMap::get()的原型中参数key的约束改了，改成了Equavlant。那么我原来的app代码还能编译通过吗？

我是猜的，感觉就不会通过了。

作者 LongRiver 2023-08-31 17:27

虽然难，但应该也是可以做到的吧。我看Borrow的文档里，就举了String和str的例子。

我看SO上的那个回答也说了，非常难实现Borrow。

我的意思是如果这么改，至少在理论上，是不兼容了。实际上可能会影响非常小。

--
👇
hangj: 问题是 Borrow<TmpKey> for Key 如何实现？这几乎是无法做到的。如果可以做到的话，Equavlant 就没必要存在了

--
👇
LongRiver: 我说的“原来的代码”，指的是使用了hashmap的app的代码，而不是 hashmap自己的代码。

比如我之前写了个app，使用hashmap，并且实现了 Borrow<TmpKey> for Key。

那么如果HashMap::get()的原型中参数key的约束改了，改成了Equavlant。那么我原来的app代码还能编译通过吗？

我是猜的，感觉就不会通过了。

hangj 2023-08-31 15:20

问题是 Borrow<TmpKey> for Key 如何实现？这几乎是无法做到的。如果可以做到的话，Equavlant 就没必要存在了

--
👇
LongRiver: 我说的“原来的代码”，指的是使用了hashmap的app的代码，而不是 hashmap自己的代码。

比如我之前写了个app，使用hashmap，并且实现了 Borrow<TmpKey> for Key。

那么如果HashMap::get()的原型中参数key的约束改了，改成了Equavlant。那么我原来的app代码还能编译通过吗？

我是猜的，感觉就不会通过了。

作者 LongRiver 2023-08-31 15:10

我说的“原来的代码”，指的是使用了hashmap的app的代码，而不是 hashmap自己的代码。

比如我之前写了个app，使用hashmap，并且实现了 Borrow<TmpKey> for Key。

那么如果HashMap::get()的原型中参数key的约束改了，改成了Equavlant。那么我原来的app代码还能编译通过吗？

我是猜的，感觉就不会通过了。

--
👇
hangj: 原来的代码也没有实现 Borrow<TmpKey> for Key

--
👇
LongRiver: 也没有完全兼容吧。

比如原来的代码里，实现了 Borrow<TmpKey> for Key，然后调用：get(&tmpkey)。

而对于新接口，由于并没有实现 Equavlant<TmpKey> for Key，那么 get(&tmpkey)就会编译不过吧。

--
👇
hangj: 新的 get() 放宽了约束的限制，可以兼容原 API

hangj 2023-08-31 12:14

原来的代码也没有实现 Borrow<TmpKey> for Key

--
👇
LongRiver: 也没有完全兼容吧。

比如原来的代码里，实现了 Borrow<TmpKey> for Key，然后调用：get(&tmpkey)。

而对于新接口，由于并没有实现 Equavlant<TmpKey> for Key，那么 get(&tmpkey)就会编译不过吧。

--
👇
hangj: 新的 get() 放宽了约束的限制，可以兼容原 API

作者 LongRiver 2023-08-30 21:51

也没有完全兼容吧。

比如原来的代码里，实现了 Borrow<TmpKey> for Key，然后调用：get(&tmpkey)。

而对于新接口，由于并没有实现 Equavlant<TmpKey> for Key，那么 get(&tmpkey)就会编译不过吧。

--
👇
hangj: 新的 get() 放宽了约束的限制，可以兼容原 API

hangj 2023-08-30 21:35

新的 get() 放宽了约束的限制，可以兼容原 API

问题是约束放得有点太宽(原约束是 &Key, 现在是 Equivalent trait)了, 而 TmpKey 是我们手工构造的，一旦原始 Key 有什么变化而 TmpKey 忘记同步修改，那就必然出问题，此时这个约束并不会给我们提示

所以说这个 get() 好用，但并不完美。如果我们要用 TmpKey 来传参则需要非常谨慎。

那么，能否在定义 Key 的时候，通过宏自动定义一个引用版本的 RefKey 呢，比如

struct Key {
    id: i32,
    name: String,
}
/// 自动定义一个下面这个
struct RefKey<'a> {
    id: &'a i32,
    name: &'a String,
}

自然是可以的，用 macro 不就行嘛，于是我手撸一个 equivalent_ref_struct macro

macro_rules! equivalent_ref_struct {
    (
        $ref_name: ident;
        $(#[$meta: meta])*
        $vis: vis struct $name: ident {
            $(
                $(#[$field_meta: meta])*
                $field_vis: vis $field_name: ident : $field_ty: ty
            ),*

            $(,)?
        }
    ) => {
        $(#[$meta])*
        $vis struct $name {
            $(
                $(#[$field_meta])*
                $field_vis $field_name: $field_ty
            ),*
        }

        $(#[$meta])*
        $vis struct $ref_name<'a> {
            $(
                $(#[$field_meta])*
                $field_vis $field_name: &'a $field_ty
            ),*
        }

        impl<'a> Equivalent<$name> for $ref_name<'a> {
            fn equivalent(&self, k: &$name) -> bool {
                $(
                    self.$field_name == &k.$field_name &&
                )* true
            }
        }
    };
}

用法：

equivalent_ref_struct! {
    RefKey;
    #[derive(Hash, PartialEq, Eq, Debug)]
    struct Key {
        id: i32,
        name: String,
    }
}


fn main() {
    let mut m = HashMap::new();
    m.insert(Key {id: 0, name: "hangj".into()}, 0);

    let key = Key {id: 0, name: "hangj".into()};
    let ref_key = RefKey {id: &key.id, name: &key.name};

    println!("{:?}", m.get(&key));
    println!("{:?}", m.get(&ref_key));
}

playground

--
👇
LongRiver: 明白了。

这种修改get()里key的约束的做法，算是修改了API的定义，属于不兼容的修改了吧？

如果是不兼容的，那感觉标准库是不会改的。除非新增一套API，比如get_equiv()之类的？那也要加好多API了。

作者 LongRiver 2023-08-30 17:56

明白了。

这种修改get()里key的约束的做法，算是修改了API的定义，属于不兼容的修改了吧？

如果是不兼容的，那感觉标准库是不会改的。除非新增一套API，比如get_equiv()之类的？那也要加好多API了。

--
👇
hangj: hashbrown 里面添加 Equivalent trait 的时间是 2022-7-22

hangj 2023-08-30 17:30

hashbrown 里面添加 Equivalent trait 的时间是 2022-7-22

https://github.com/rust-lang/hashbrown/commit/75a9ef979b7502ce123631d5af77b65ac6131911#diff-110e61eb735b79c762510f02f157a12094bcf2b9a15d2ed767532a0e3d5f7bafR1214

pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
    where
        Q: Hash + Equivalent<K>,
{}

标准库里一直还没跟进，我觉得可能标准库更严谨吧。
你看这个 get 函数它要求 Q: Hash + Equivalent<K>, 但其实它还有一个隐含的要求，就是对于具有相同 fields 的 Q 和 K, 它们的 hash 值应该是相等的。我之前的例子中 Key 和 TmpKey 就符合这个要求

use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};

#[derive(PartialEq, Eq, Hash)]
struct Key {
    id: i32,
    name: String,
}

#[derive(PartialEq, Eq, Hash)]
struct TmpKey<'a> {
    id: i32,
    name: &'a String,
}

let key = Key {id: 0, name: "hangj".into()};
let tmp_key = TmpKey {id: 0, name: &"hangj".into()};

let mut hasher = DefaultHasher::new();
key.hash(&mut hasher);
println!("key hash: {:?}", hasher.finish());

let mut hasher = DefaultHasher::new();
tmp_key.hash(&mut hasher);
println!("tmpkey hash: {:?}", hasher.finish());

当 id 和 name 都相等时，输出的这两个 hash 也是相等的。

但是，万一有人这么定义 TmpKey:

#[derive(PartialEq, Eq, Hash)]
struct TmpKey<'a> {
    // 改变了 field 的顺序
    name: &'a String,
    id: i32,
    // 甚至添加了更多的 field
    // ...
}

// 也实现了 Equivalent trait
impl<'a> Equivalent<Key> for TmpKey<'a> {
    fn equivalent(&self, key: &Key) -> bool {
        self.id == key.id && self.name == &key.name
    }
}

// 此时对于 id:0, name:"hangj" 的 Key 和 TmpKey，它们的 hash 值不再相等

那么我们依然可以把 &TmpKey 传递给 get(), 但是可能永远得不到我们想要的结果。。

因此，我觉得这个接口可能还不适合完全暴露出来吧。

SO 上那个回复没有上下文，我也不太清楚是啥意思。

--
👇
LongRiver: 晚点有空了学习下。

我看在SO上你的这个答案下面，有人回复 “Now that is a promising new feature.”，这是什么意思？是说标准库已经在准备这个功能了吗？

作者 LongRiver 2023-08-30 14:50

晚点有空了学习下。

我看在SO上你的这个答案下面，有人回复 “Now that is a promising new feature.”，这是什么意思？是说标准库已经在准备这个功能了吗？

--
👇
hangj: 研究了下，发现还有更简单写法:

作者 LongRiver 2023-08-30 14:47

多谢回复。

这确实是个方法。不过这应该是增加了一些开销。就要看具体场景中是否值得了。

--
👇
asuper: 以下代码经实测，应该能满足你的需求，原理就是让Key可以同时接受String和&str，并让他们可以相等


enum StrKey<'a> {
    Keep(String),
    Temp(&'a str),
}

impl<'a> StrKey<'a> {
    fn get_str(&'a self) -> &'a str {
        match self {
            Self::Keep(a) => &*a,
            Self::Temp(b) => *b,
        }
    }

    fn from_str(s: &'a str) -> Self {
        Self::Temp(s)
    }

    fn from_string(s: String) -> Self {
        Self::Keep(s)
    }
}

impl<'a> Hash for StrKey<'a> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        match self {
            StrKey::Keep(a) => a.hash(state),
            StrKey::Temp(b) => b.hash(state),
        };
    }
}

impl<'a> PartialEq for StrKey<'a> {
    fn eq(&self, other: &Self) -> bool {
        self.get_str() == other.get_str()
    }
}

#[derive(Hash, PartialEq, Eq, Debug)]
struct MyKey<'a> {
    id: u64,
    name: StrKey<'a>,
}
作者 LongRiver 2023-08-30 14:45

你的问题是，为什么是 &Q 而不是 Q ？

如果是这个问题的话，那我理解get没必要consume这个key，所以引用就足够了。

--
👇
leolee0101: 不好意思，稍微歪个楼。 std hashmap 的 get 方法为什么设计为 接受 引用类型的key 呢？

fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>

leolee0101 2023-08-30 13:24

不好意思，稍微歪个楼。 std hashmap 的 get 方法为什么设计为 接受 引用类型的key 呢？

fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>

asuper 2023-08-30 10:01

以下代码经实测，应该能满足你的需求，原理就是让Key可以同时接受String和&str，并让他们可以相等


enum StrKey<'a> {
    Keep(String),
    Temp(&'a str),
}

impl<'a> StrKey<'a> {
    fn get_str(&'a self) -> &'a str {
        match self {
            Self::Keep(a) => &*a,
            Self::Temp(b) => *b,
        }
    }

    fn from_str(s: &'a str) -> Self {
        Self::Temp(s)
    }

    fn from_string(s: String) -> Self {
        Self::Keep(s)
    }
}

impl<'a> Hash for StrKey<'a> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        match self {
            StrKey::Keep(a) => a.hash(state),
            StrKey::Temp(b) => b.hash(state),
        };
    }
}

impl<'a> PartialEq for StrKey<'a> {
    fn eq(&self, other: &Self) -> bool {
        self.get_str() == other.get_str()
    }
}

#[derive(Hash, PartialEq, Eq, Debug)]
struct MyKey<'a> {
    id: u64,
    name: StrKey<'a>,
}
hangj 2023-08-29 15:01

研究了下，发现还有更简单写法:

extern crate hashbrown;

// 标准库里的 HashMap 就是用的 hashbrown 的这个 HashMap
use hashbrown::hash_map::HashMap;
use hashbrown::Equivalent;

#[derive(PartialEq, Eq, Hash)]
struct Key {
    id: i32,
    name: String,
}


fn main() {
    let mut m = HashMap::new();
    m.insert(Key {id: 0, name: "hangj".into()}, 0);

    m.get(&Key {id: 0, name: "hangj".into()}).unwrap();

    {
        #[derive(Hash, Eq, PartialEq)]
        struct TmpKey<'a> {
            id: i32,
            name: &'a String,
        }

        impl<'a> Equivalent<Key> for TmpKey<'a> {
            fn equivalent(&self, key: &Key) -> bool {
                self.id == key.id && self.name == &key.name
            }
        }

        m.get(&TmpKey {id: 0, name: &"hangj".into()}).unwrap();
    }
}
1 2 共 27 条评论, 2 页