Trait object as hash key - possible

help
1

Playground:

I want to have a trait object as a hash key. Is that possible?

It ought to work, per Workaround for Hash trait not being object-safe
but I can't even get the declaration to compile, let alone the implementation.

What's the problem with PartialEq, anyway? That seems safe. It doesn't output a Self.

2

PartialEq is short for PartialEq<Self>.

i32 implements Hash, Eq, and PartialEq<i32>. So you can use i32 as a hash key because it is hashable and comparable to other i32s.

String implements Hash, Eq, and PartialEq<String>. So you can use String as a hash key because it is hashable and comparable to other Strings.

Now, suppose you could make a hash table containing both i32s and Strings as keys. And suppose that when trying to insert an i32 into it, you find that the hash already exists. How do you know whether the key that already exists in the table is another i32, or a String that happens to have the same hash?

2 Likes
3

I was able to get your example working: Rust Playground

The main things to note are

  • I un-elided a lot of trait object lifetimes since this elision is often confusing. If you want to be able to put non-'static trait objects into your HashMap then you can do so by replacing 'static with a generic lifetime 'a in the appropriate places
  • Hash is not object-safe because Hash::hash has a type generic parameter for the hasher. The workaround for this is to put a method on your trait that takes &mut dyn Hasher, and then impl Hash for dyn ViewableObjectMesh using this method
  • To implement Eq for the trait object type you need to be able to downcast it, which involves going through dyn Any
  • Due to the use of these techniques there is some boilerplate involved in implementing ViewableObjectMesh for your type—if this gets really annoying you could put it in a macro
  • The key type for a HashMap needs to be Sized, so you have to box the trait object values to use them as keys. This doesn't cause problems because Hash & co. have blanket impls for Box<T> where T is another implementor
  • I didn't deal with the Clone requirement in your original code. Trait object types can't be Clone because it would require returning a !Sized value from a function, which the language doesn't support; but you can have a method on the trait that returns Box<dyn ViewableObjectMesh> and use that instead
6 Likes
4

Thanks very much.

I need to think about this. This adds so much complexity that I may re-do my code to not use traits at all. The key is actually either a Uuid or an Md5, so I could use an enum rather than trying to kludge traits into doing the job.

1 Like
5

This is a great plan. If you don't need the set to be open for extensibility, the enum will be way easier -- especially since the derive will get all the cross-type Eq/Ord logic right.

1 Like
6

You should be able to write a blanket implementation of ViewableObjectMesh for any T: Any + Hash + Eq, thus avoiding any macro or boilerplate after that.

7

Note that there's a commented-out additional trait method in John_Nagle's playground (and mine) which presumably doesn't have a reasonable blanket implementation.

8

In that case I would move the part that needs T: Any + Hash + Eq in a subtrait and write a blanket impl for that.

1 Like
9

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.