Hash not implemented, why can't it be derived?

I have an Vec of an enum embedded in a struct that both derive Hash and I do not get an error. However, if I change the Vec to a HashSet to prevent duplicates I get an error that Hash is not implemented for the type with HashSet. --see code below.

I'm really confused as to what I need to do as Hash is derived for both types (struct and enum).

[derive(Serialize, Deserialize, Hash, Eq, PartialEq, Debug, Clone)]
pub struct User {
    name: Option<String>,
    groups: HashSet<UserGroup>,
}
#[derive(Serialize, Deserialize, Hash, Eq, PartialEq, Debug, Default, Clone)]
pub enum UserGroup {
    #[default]
    User,
    Admin,
}
the trait bound `HashSet<UserGroup>: std::hash::Hash` is not satisfied
the trait `std::hash::Hash` is not implemented for `HashSet<UserGroup>`

HashSet does not implement Hash, so you can't derive Hash for User.

2 Likes

And the reason why: HashSet (and HashMap, too) stores its elements in pseudo-random order. However, two sets/maps are equal if they contain the same elements, regardless of order (the pseudo-randomization is merely an implementation detail).

Thus, they can't be hashed – they could only be hashed in a way that's either inconsistent with Eq (producing false negatives), or prohibitively expensive (allocates a new array and sorts it internally).

4 Likes

So it sounds like structs can't be hashed. That would mean I just have to make sure that I have prevent duplicates in all my logic rather than being able to rely on a type. Am I correct in this assumption?

It's not that all structs can't be hashed, just that the HashSet type can't be hashed and therefore #[derive(Hash)] won't work on a struct containing a HashSet.

If you want your struct to be hashable, use something different like a BTreeSet.

4 Likes

Well the reason I was trying to use Hashset was just to make it easy to prevent duplicates. I guess BTreeSet should do the same thing.

Out of interest why are you deriving Hash on the User struct?

If you use it in a hashSet to guarantee unique user records it would be possible to insert duplicate usernames by having different groups set on the duplicate record. Would a hash map be more appropriate?

No, that's not correct. Your particular type can't be hashed because it contains a HashSet. If it didn't, it could.

Yes. As its name clearly implies, it's (also) a set.

1 Like

To be honest I'm not sure why. I've iterated over several implementations of things, and at some point it was required. Now it is required for the BTreeSet.

Some of it is laziness I suppose as it seems easier to rely on a std library type to do some of the work for me and since I'm relatively green, it seems most of my implementations of things will be relatively naive and so probably pretty inefficient. I expect that to change over time.

As for inserting duplicate usernames. That won't happen because I am checking a user based on username before taking any action (add, remove, modify). BTreeSet does seem to be the "correct" tool to use right now.

It sounds like what you really need is to restructure your project so that User is only the name, and store the groups in a HashMap<Username, HashSet<UserGroup>> which lets you take a username, check if it's registered, and find out what groups it has, in that order.

Think about this as if you're trying to build a database. You cannot have two of the same username with different sets of data, right? This means your primary key is the username, and everything else depends on the username. So, you map the username to the rest of the data. Only the username needs to be hashable.

This also lets you easily guard against duplicate usernames. You just check if the map contains the name. You no longer have to check for user group.

We can also talk about using bitflags for your UserGroup, but that's another story. For now, see if the HashMap method works.

1 Like

Why would you need to sort to hash? Can't you just use a way of hashing that does not depend on the order? Such as adding the hash codes of all elements?

Hashing is generic, and not all hashers are commutative (in fact, most aren't).

Oh, I see, thanks. The hash may depend on what was hashed before.

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.