search

indexmap-rs / indexmap

A hash table with consistent order and fast iteration; access items by key or sequence index
https://docs.rs/indexmap/
Other
1.67k stars 150 forks source link

Add hash implementation #329

Closed fabianboesiger closed 3 months ago

fabianboesiger commented 3 months ago

There were several requests to implement Hash for IndexMap and IndexSet. The problem with implementing Hash is that it should be consistent with the Eq implementation. The Eq implementation is based on containing equivalent items regardless of order, requiring the hash to stay the same regardless of order. To fix this issue, one comment https://github.com/indexmap-rs/indexmap/issues/67#issuecomment-368576339 suggests using a commutative operation to combine the hashes of the individual entries.

This draft is an implementation of this proposal.

cuviper commented 3 months ago

That comment also linked to https://github.com/rust-lang/rust/pull/48366, which was closed due to that hash approach being rather weak.

What is your use-case? Would you be able to work with a newtyped key that does consider the order of items?

fabianboesiger commented 3 months ago

Yes, I'm aware that the solution is not perfect, but as many people seem to request it, it might still make sense to consider it.

I'm also aware that the .as_slice() API exists where Slice implements Hash, however, this is still very inconvenient when we want to derive Hash for a struct that contains an IndexMap.

It is also possible to add an implementation for newtyped keys that do consider the order of items, I can look into that if sou decide to add this feature.

cuviper commented 3 months ago

but as many people seem to request it

Not so many that we need to do something, IMO, especially since the standard HashMap did not.

[...] when we want to derive Hash for a struct that contains an IndexMap.

I am still skeptical that it makes sense to do that. We can figure out ways to create a Hash, ordered or not, but that doesn't necessarily make it useful. Do you have a concrete use-case that you can share?

fabianboesiger commented 3 months ago

My use case is I'd like to create sets of sets. I could use BTreeSets for that, but this is a bit too slow.

I think I will close this PR for now and create my own wrapper struct that I can use for my use case. Feel free to reopen this in case it is needed in the future.