如何创建可哈希的特质对象/带有泛型方法参数的特质对象？

Question

如何创建可哈希的特质对象/带有泛型方法参数的特质对象？

15

我有一些实现了Hash和MyTrait的结构体。我将它们用作&MyTrait特质对象。

现在我想让&MyTrait也实现Hash。我尝试了一些方法：

Naively, trait MyTrait: Hash {}:

the trait `MyTrait` cannot be made into an object

Then I tried this:

impl Hash for MyTrait {
    fn hash<H: Hasher>(&self, hasher: &mut H) {
        // ...
    }
}

but I need to delegate to the hash method of the concrete type of self, I think.

So the naive next step is to put this on MyTrait:
```
fn my_hash<H: Hasher>(&self, hasher: &mut H);
```
which brings me right back to the first point.

I read something about using a trait object instead of generic parameter, which sounds smart, so I put this on MyTrait

fn my_hash(&self, hasher: &mut H);

Then I need to actually implement this. Preferably not by hand for every trait:

impl<T: 'static + Hash> MyTrait for T {
    fn as_any(&self) -> &Any {
        self as &Any
    }

    fn my_hash(&self, hasher: &mut Hasher) {
        self.as_any().downcast_ref::<T>().unwrap().hash(hasher)
    }
}

but then

the trait bound `std::hash::Hasher: std::marker::Sized` is not satisfied
`std::hash::Hasher` does not have a constant size known at compile-time

So I'd have to downcast Hasher…

If downcasting Hasher is the way, I need a generic parameter H that can convert to an Any Hasher, Let's try:

trait AnyHasher {
    fn as_any(&self) -> &Any;
}

impl<H: 'static + Hasher> AnyHasher for H {
    fn as_any(&self) -> &Any {
        self as &Any
    }
}

and then to downcast

impl<T: 'static + Hash, H: 'static + Hasher> MyTrait for T {
    // ...
    fn my_hash(&self, hasher: &mut AnyHasher) {
        let h = hasher.as_any().downcast_ref::<H>().unwrap();
        self.as_any().downcast_ref::<T>().unwrap().hash(h)
    }
}

but alas

the type parameter `H` is not constrained by the impl trait, self type, or predicates

which I guess is true, but then I'm stuck. (Also it seems kind of ridiculous so far).

这个能做到吗？如果可以，怎么做？

我之前询问过关于PartialEq for trait objects的问题，因为需要具体类型的信息，所以很难。那个问题通过向下转换已经解决了，但我没有成功地将那个解决方案应用在这里。

- Mark

你的第一个例子对我有效。 - Jmb

@Jmb 是的，但是无法创建该特性的对象：https://play.integer32.com/?gist=066b22be8dc9286bf88f7da709d095ff&version=stable（或者我不知道如何创建）。 - Mark

我遇到了和这个几乎相同的问题，你已经解决了吗？ - J. Doe

1

为什么不在你的 trait 中添加一个 hash 方法，然后在第二次尝试中调用它呢？ - Boiethios

@Boiethios 哦，是的，你说得对，这有点为下一步做准备（使用 trait 对象 &Hasher），需要一个新的方法名。但我提前更改了名称并没有意义，抱歉。 - Mark

1

@Mark 我正在编写一个 POC。 - Boiethios

2个回答

1

你可以将所需的功能放在你的trait中，即将你的第二次尝试和第三次尝试进行混合：

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

#[derive(Hash)]
struct Foo(i32);

#[derive(Hash)]
struct Bar(String);

// Put the desired functionalities in your trait

trait MyTrait {
    fn my_hash(&self, h: &mut Hasher);
    fn my_eq(&self, other: &MyTrait) -> bool {
        let mut hasher1 = DefaultHasher::new();
        let mut hasher2 = DefaultHasher::new();

        self.my_hash(&mut hasher1);
        other.my_hash(&mut hasher2);
        hasher1.finish() == hasher2.finish()
    }

    // other funcs
}

impl MyTrait for Foo {
    fn my_hash(&self, mut h: &mut Hasher) {
        self.hash(&mut h)
    }
}

impl MyTrait for Bar {
    fn my_hash(&self, mut h: &mut Hasher) {
        self.hash(&mut h)
    }
}

// Implement needed traits for your trait

impl Hash for MyTrait {
    fn hash<H: Hasher>(&self, hasher: &mut H) {
        self.my_hash(hasher)
    }
}

impl PartialEq for MyTrait {
    fn eq(&self, other: &MyTrait) -> bool {
        self.my_eq(other)
    }
}

impl Eq for MyTrait {}

// This compiles

fn main() {
    let foo = Foo(42);
    let bar = Bar("answer".into());
    let mut set = HashSet::new();

    set.insert(&foo as &MyTrait);
    set.insert(&bar);
}

在我看来，按照你的方式为一个特质实现Hash并不是一个好主意，因为你不知道特质旁边的具体类型是什么。有人可能会为同一类型实现该特质，例如：

struct Foo(String);
struct Bar(String);

在这种情况下，您如何处理Foo("hello")和Bar("hello")？它们是相同的项吗？因为它们将具有相同的哈希值。

在您的情况下，真正的问题是：如何从特征中定义什么是相同或不同？ 在我看来，更好的处理方法是从“业务”特征方法计算哈希值，例如：

#[derive(Hash)]
struct Baz(...); // Business item
#[derive(Hash)]
struct Qux(...); // Another business item

trait MyTrait {
    // all those returned items make my MyTrait unique
    fn description(&self) -> &str;
    fn get_baz(&self) -> Baz;
    fn get_qux(&self) -> Qux;
}

impl Hash for MyTrait {
    fn hash<H: Hasher>(&self, hasher: &mut H) {
        self.description().hash(hasher);
        self.get_baz().hash(hasher);
        self.get_qux().hash(hasher);
    }
}

特质只是一种契约或某个事物的部分考虑（就像你说“人类”是“开发者”一样）。在我看来，你不应该把特质视为具体类型。

- Boiethios

哦，是的，那很聪明，我感到有点傻，没想到只需返回结构体的哈希值！不过... - Mark

我希望我能使用相同的Hasher，这样可以稍微提高性能（这样我只需委托给结构体的hash方法），但主要是因为似乎传递Hasher是有原因的（尽管我不太清楚Hasher的区别在哪里）。 - Mark

这是我的意思：https://play.integer32.com/?gist=745649a956638fb9fbeed0aa2420eb07&version=stable。不要误会，这个答案很聪明，在大多数实际情况下都有效；如果没有更好的出现，我会接受它。 - Mark

@Mark：你是指在多个对象中重复使用相同的“Hasher”实例吗？ - Matthieu M.

@MatthieuM。很好，你提出了哈希冲突的问题。在我的情况下，我只会接受哈希冲突（我的eq不是基于hash）。这可能会影响性能，但除此之外应该可以正常工作，对吧？ - Mark

显示剩余5条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jferard · Accepted Answer

我不是Rust专家，但我觉得你在试图将Rust变成Java（别生气：我真的很喜欢Java）。

如何创建可哈希的特质对象？

你不想创建特质对象的哈希表（这很容易），你想要创建一个特质的哈希表，它们不是特质对象，这就是你遇到困难的原因。

问题

总结一下：你有一些实现了特质MyTrait、Hash和Eq的各种结构体，并且你想将这些混合的结构体作为单个哈希表中的TunedMyTrait特质对象。这需要TunedMyTrait成为Hash和Eq的子特质。但是，虽然可以将MyTrait变成特质对象，但TunedMyTrait不能。

我相信你知道为什么，但我将尝试通过this valuable resource来为其他读者澄清（这是我自己的话，如果你认为不清楚，请不要犹豫编辑）。特质对象依赖于所谓的“对象安全性”（请参见RFC 255）。“对象安全性”意味着：特质的所有方法都必须是对象安全的。

Rust广泛使用堆栈，因此它必须知道它可以使用的所有内容的大小。在借用检查器之后，这是Rust的难点之一和美妙之处。特质对象是类型化且有大小的：它是一种包含具体类型信息的“大”指针。每个方法调用都被委托给具体类型，使用方法vtable。我不详细介绍，但是可能会出现一些问题，该“安全检查”旨在避免这些问题。在此：

方法fn eq(&self, other: &Rhs) -> bool，其中Rhs = Self，不是对象安全的，因为在运行时，Rhs被抹除，因此未知other的具体类型和大小。
方法fn hash<H: Hasher>(&self, hasher: &mut H)不是对象安全的，因为vtable没有为每个具体类型H构建。

解决方案

好的。 MyTrait是一个特征对象，但TunedMyTrait不是。然而，只有TunedMyTrait对象可能是您哈希表的有效键。你该怎么办？

您可以像之前一样尝试破解对象安全机制。您已经找到了一个破解PartialEq的方法(使用类型转换，如何测试特征对象之间的相等性？)，现在又从@Boiethios那里得到了另一个破解方法(基本上将哈希函数变成非泛型函数)。如果您最终达到了目标，我可以想象未来代码的读者会是怎样的心情："天哪，这个人在干什么啊?"或者更糟糕的是:"我不确定它做了什么，但我敢肯定如果...它会跑得更快"。您已经破解了语言的保护措施，您的代码可能会产生比您试图解决的问题更严重的问题。这让我想起了这种讨论: 在运行时获取类的泛型类型。那么接下来呢？你要怎么处理这段代码呢？

或者您可以理性一点。有一些可能性：您可以使用具有真正相同具体类型的键的哈希表，您可以将您的MyTrait对象包装起来，您可以使用枚举...还可能有其他的方式(正如我所说，我不是Rust专家)。

不要误解我的意思：通过黑客手段学习一门语言确实很有趣，有助于深入理解它的机制和限制（注意：如果你没有问那个问题，我就不会仔细研究DST和特质对象，因此非常感谢你）。但是，如果你打算做一些严肃的事情，你必须认真对待：Rust不是Java...

编辑：

我想比较和哈希运行时多态的对象。

那不难，但你也想把它们放在一个HashMap中，这就是问题所在。

我将给你另一个洞见。基本上，你知道哈希表是一个存放桶的数组。Rust使用开放式寻址来解决哈希冲突（具体而言：罗宾汉哈希），这意味着每个桶将包含0或1对 (key, value) 。当你将一对 (key, value) 放入空桶中时，元组 (key, value)会被写入缓冲区数组，在位置 pair_start + index * sizeof::<K, V>()，根据offset的定义。显然，您需要有大小限制的对。

如果您可以使用特质对象，您将拥有大小指针。但由于已经说明的原因，这是不可能的。我提出的所有想法都集中在这一点上：拥有大小键（假设值已经有大小）。具体类型：显然是有大小的。Boxing：指针的大小。枚举：最大元素的大小+标记的大小+填充的大小。

Boxing的基本示例

警告：我尽力在互联网上找到一个示例，但没有找到任何东西。所以我决定从头开始创建一个基本的boxing示例，但我不确定这是否是正确的方法。如有需要，请评论或编辑。

首先，在您的特质中添加一个方法，该方法使用可比较和可哈希的值来标识实现MyTrait的任何具体类型的每个实例，例如返回i64的id方法：

trait MyTrait {
    fn id(&self) -> i64; // any comparable and hashable type works instead of i64
}

Foo和Bar具体类型将实现此方法（这里给出的实现完全是愚蠢的）：

struct Foo(u32);

impl MyTrait for Foo {
    fn id(&self) -> i64 {
        -(self.0 as i64)-1 // negative to avoid collisions with Bar
    }
}

struct Bar(String);

impl MyTrait for Bar {
    fn id(&self) -> i64 {
        self.0.len() as i64 // positive to avoid collisions with Foo
    }
}

现在，我们需要实现Hash和Eq，以便将MyTrait放入HashMap中。但是如果我们为MyTrait这样做，我们会得到一个无法成为特征对象的特征，因为MyTrait没有大小。让我们为Box<Trait>实现它，这是有大小的：

impl Hash for Box<MyTrait> {
    fn hash<H>(&self, state: &mut H) where H: Hasher {
        self.id().hash(state)
    }
}

impl PartialEq for Box<MyTrait> {
    fn eq(&self, other: &Box<MyTrait>) -> bool {
        self.id() == other.id()
    }
}

impl Eq for Box<MyTrait> {}

我们使用了“id”方法来实现“eq”和“hash”。

现在，考虑“Box ”：1.它是有大小的；2.它实现了“Hash”和“Eq”。这意味着它可以用作“HashMap”的键：

fn main() {
    let foo = Foo(42);
    let bar = Bar("answer".into());
    let mut my_map = HashMap::<Box<MyTrait>, i32>::new();
    my_map.insert(Box::new(foo), 1);
    my_map.insert(Box::new(bar), 2);

    println!("{:?}", my_map.get(&(Box::new(Foo(42)) as Box<MyTrait>)));
    println!("{:?}", my_map.get(&(Box::new(Foo(41)) as Box<MyTrait>)));
    println!("{:?}", my_map.get(&(Box::new(Bar("answer".into())) as Box<MyTrait>)));
    println!("{:?}", my_map.get(&(Box::new(Bar("question".into())) as Box<MyTrait>)));

}

输出：

    Some(1)
    None
    Some(2)
    None

请试一下：https://play.integer32.com/?gist=85edc6a92dd50bfacf2775c24359cd38&version=stable

我不确定它是否解决了你的问题，因为我不知道你想要做什么...