如何使用通用方法参数创建可散列特征对象/特征对象？

Question

我有一些结构可以实现 Hash 和 MyTrait。我将它们用作 &MyTrait 特征对象。

现在我希望 &MyTrait 也实现 Hash。我已经尝试了一些事情：

天真，trait MyTrait: Hash {}:

the trait `MyTrait` cannot be made into an object

然后我试了这个：

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

但是我想我需要委托给self具体类型的hash方法。

所以天真的下一步就是把它放在 MyTrait:
```
fn my_hash<H: Hasher>(&self, hasher: &mut H);
```
这让我回到了第一点。

我读到一些关于使用特征对象而不是泛型参数的东西，这听起来很聪明，所以我把它放在 MyTrait

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

然后我需要实际执行它。最好不要对每个特征都进行手动操作：

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

然后

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

所以我不得不低头Hasher…

如果向下转换 Hasher 是方法，我需要一个可以转换为 Any Hasher 的通用参数 H，让我们试试：

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

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

然后向下转换

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

可惜

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

我想这是真的，但后来我卡住了。（到目前为止，这似乎有点荒谬）。

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

我之前问过 PartialEq for trait objects，这很难，因为需要特征对象的具体类型信息。这是通过向下转换解决的，但我没有设法在这里应用该解决方案。

Answer 1

您可以将所需的功能放入您的特征中，即您可以混合第二次和第三次尝试：

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 trait 不是一件好事，因为你不知道trait 旁边的具体类型是什么。有人可以为同一类型实现特征，例如：

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

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

在你的情况下，真正的问题是：你如何定义特征的相同或不同？在我看来，处理这个问题的更好方法是从 "business" 特征方法计算散列，例如：

#[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);
    }
}

特质只是契约或对事物的部分考虑（就像你说 "human being" 是 "developer" 一样）。你不应该（以我的拙见）将特征视为具体类型。

Answer 2

我不是 Rust 专家，但在我看来，您试图将 Rust 变成 Java（不要生气：我真的很喜欢 Java）。

How can I create hashable trait objects?

您不想创建特征对象的哈希表（这很简单），您想要创建特征的哈希表不是特征对象，这就是您遇到的原因困难。

问题

我总结一下：你有一些实现特征 MyTrait、Hash 和 Eq 的不同结构，你想将这些混合结构放入单个哈希表中作为TunedMyTrait 特征对象。这需要 TunedMyTrait 是 Hash 和 Eq 的子特征。但是 MyTrait 可以成为特征对象，而 TunedMyTrait 不能 .

我相信您知道原因，但我会尝试使用 this valuable resource. (I put it in my own words, don't be shy and edit it if you think that isn't clear.) Trait objects rely on something that is called "object safety" (see the RFC 255) 向其他读者解释清楚。 "Object safety"表示：trait的所有方法必须是object-safe.

Rust 大量使用栈，因此它必须知道它能知道的所有东西的大小。在借用检查器之后，这是 Rust 的难点和优点之一。特征对象是有类型和大小的：它是某种 "fat" 指针，包含有关具体类型的信息。每个方法调用都使用 vtable 方法委托给具体类型。我没有详细说明，但此委派可能会出现一些问题，创建 "safety check" 是为了避免这些问题。这里：

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

解决方法

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

您可以像您一样尝试破解对象安全机制。您找到了破解 PartialEq 的解决方案（通过强制转换尝试，How to test for equality between trait objects?), and you have now another hack from @Boiethios (which basically makes of hash a non generic function). If you finally reach your goal, I can imagine the future reader of the code: "OMG, what is this guy trying to do?" or (worse): "I'm not sure of what it does, but I'm pretty sure it would run faster if...". You have hacked a protection of the language and your code is likely to create issues worse than the problem you are trying to solve. This reminds me this kind of discussion: Get generic type of class at runtime。然后？您将如何处理这段代码？

或者你可以讲道理。有一些可能性：您使用具有相同具体类型的键的哈希表，将 MyTrait 对象装箱，使用枚举...可能还有其他方法（如前所述，我不是Rust 专家）。

不要误会我的意思：破解一门语言真的很有趣，有助于深入理解它的机制和限制（注意：如果你没有问这个问题，我就不会仔细研究 DST和特征对象，因此我感谢你）。但是如果你打算做一些严肃的事情，你必须认真：Rust 不是 Java...

编辑

I want to compare and hash objects that are runtime-polymorphic.

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

我再给你一个见解。基本上，您知道哈希表是一个桶数组。 Rust 使用开放寻址来解决哈希冲突（特别是：Robin Hood 哈希），这意味着每个桶将包含 0 或 1 对 (key, value)。当你put a pair (key, value) in an empty bucket, the tuple (key, value) is written in the buffer array, at the position pair_start + index * sizeof::<K, V>(), according to the definition of offset。很明显你需要 sized 对。

如果你可以使用 trait 对象，你就会有胖指针，它是有大小的。但由于已经说明的原因，这是不可能的。我提出的所有想法都集中在这一点上：具有大小的键（假设值已经大小）。混凝土型：明显尺寸。装箱：指针的大小。枚举：最大元素的大小+标签的大小+填充。

拳击基本示例

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

首先，向您的特征添加一个方法，该方法标识实现 MyTrait 的任何具体类型的每个实例，具有 comparable 和 hashable 值，假设一个 id 方法 returns 一个 i64:

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<MyTrait>：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

我不确定它是否能解决您的问题，但我真的不知道您要做什么...

如何使用通用方法参数创建可散列特征对象/特征对象？

How can I create hashable trait objects / trait objects with generic method parameters?

generics

traits

rust

问题

解决方法

拳击基本示例