HashSet<Foo> vs Vec<Foo> as a __KEY__

Consider HashMap<K, V> the special case where K can be either:

  1. HashSet<Foo> OR
  2. Vec<Foo>

Foo has Ord, PartialOrd, Eq, PartialEq, Hash defined on it.

In the Vec<Foo> case, we sort the Vec before lookups.

There are no duplicate Foo values in the key.

Thus, either Vec or HashSet can function as the key.

Question: given the above, is there any big advantage or disadvantage of using HashSet<Foo> vs Vec<Foo> for the key?

HashSet cannot be the key, because it doesn't implement Hash itself. Doing so would require it to be consistent with its Eq, which is notably independent of item order.

1 Like

To be pedantic (this tripped me up), we can use HashSet<Foo> as the Key, and it will compile (tripping me up), but we can't use get/insert/delete on the HashMap, making it sorta useless.

But yes, you're right, there is no debate here, Vec<Foo> is the only practical choice.

1 Like

Just to clarify even more, by "it will compile" you must mean HashMap::new will compile when a HashSet is used as the key, because new doesn't require the Hash bound on the key, while insert does require it.

  1. For anyone else reading, @cuviper is absolutely right, Vec<Foo> is the only choice, HashSet<Foo> is silly.

  2. @jumpnbrownweasel : I didn't even get as far as HashMap::new -- I merely declared a

pub struct Blah {
  x: HashMap<HashSet<Foo>, V>

it compiled, and I started wondering if I should go with HashSet or Vec, LOL.

BTreeSet does implement Hash, though, so you could ask about that vs. Vec<Foo> as a key.

5 Likes

Well, it would be possible to implement an order-independent hash function. We had that in rustc for a while.
If someone needs it they can do so via a newtype.

A commutative Hash was also attempted for the standard library once:

1 Like

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.