Conditionally impl Trait(Hash)

Say I wanna impl a fn as following:


// find if A is in B 
// A is vector, B is more like a set
// e.g. A: [1,67,2,12,7] && B: [1,2,2] -> [true, false, true, false, false]
fn find_if_a_in_b<T: PartialEq + Eq>(A: Vec<T>, B: Vec<T>) > Vec<T> {
   todo!();
}

The naive way to do this is by iterating 2 vectors, as we know(omit here).

But when I want to boost performance a little by converting B into HashSet internally, like:

fn array_diff<T: PartialEq + Eq>(a: Vec<T>, b: Vec<T>) -> Vec<T> {
    let rms = b.into_iter().collect::<HashSet<_>>();
    // ... 
}

problems arise:

error[E0277]: the trait bound `T: Hash` is not satisfied
 --> src/main.rs:8:29
  |
8 |     let rms = b.into_iter().collect::<HashSet<_>>();
  |                             ^^^^^^^ the trait `Hash` is not implemented for `T`
  |
  = note: required because of the requirements on the impl of `FromIterator<T>` for `HashSet<T>`
help: consider further restricting this bound
  |
7 | fn array_diff<T: PartialEq + Eq + Hash>(a: Vec<T>, b: Vec<T>) -> Vec<T> {
  |                                 ^^^^^^

error: aborting due to previous error; 1 warning emitted

Seems I miss a trait bound here

But my question is more intrinsic:

why should we add one more trait constraint on T when it's already Eq?
we can default to a naive impl of Hash by fact of T being Eq

In summary,
What I finally wanna do is:

  1. check if T is Hash, if yes, we use its hash provided
  2. if not, I can impl a naive Hash for T, which is like hash(val: T) = val, i.e. just return its value

But I cannot find a working code to do this, also I'm not sure if Rust supports this

Could anyone please give me a rust playground link to a working code where we can meet the api shape as above?

Thanks a lot in advance!!!

You have to add more traits if you want something better than the slow nested loops solution. It doesn't have to be Hash since types like BTreeSet can make do with the Ord trait instead, but you need more traits.

Using the value itself as the hash is not valid because the hash must be an integer. There is no naive hash impl you can add here besides always returning the same constant, which will be just as slow as the nested loops.

I think you may be misunderstanding what the Hash trait in the standard library does. It represents something that can feed itself to a Hasher, so the hash() method doesn't actually compute or return a hash value, it just calls methods on the provided Hasher to supply the components of the value. You wouldn't know the structure of the type you are working with in this case, so if it doesn't already implement Hash the best you could do is provide some constant value to the Hasher, which would give a fairly useless hash as a result.

really thanks for your reply

I also thought this might be the explanation before asking this question

But that time I was mainly troubled by the fact that how inconvinent this could be(and still now)

Anyway, I understand Rust is a "strict" language
And I would back to do it in a hard, handy way

What you seem to look for is Specialization (RFC 1210), and unfortunately, it's not stable as of today.

HashSet<i32> is Eq but not Hash since hashing the collection relies on the iteration order which is not stable on hash table. What do you want to do if the T is HashSet<i32>?

2 Likes