PartialHash - PartialOrd for Hash

1

Let's say you have a function that takes a String and an Option<HashSet<Whatever>>. The exact types don't matter; The relevant behaviour is that at least one argument is Hash and at least one argument isn't Hash.
Now, let's say you want to apply caching by hashing the input and putting the input's hash and output value in a HashMap.

In the general case, this is impossible. But what if 99% of the time, the Option<HashSet> is None? The argument for HashSet not being hashable doesn't apply in that case and the value provided by a cache is a whole 99% of what it would be if impl<T: Ord> Hash for HashSet<T>.

Proposal: PartialHash - A version of Hash that hashes to an Option<u64>.

  • If T is not Hash then Option<T>::partial_hash returns Some only when the Option<T> is None and otherwise always returns None. So for T: !Hash, x.partial_hash().is_some() != x.is_some().
  • If a type implements Hash, then PartialHash::partial_hash returns Some(Hash::hash(...)). (same relation PartialOrd has with Ord)
  • All types could implement PartialHash since always returning None and always returning Some are both theoretically valid behaviours. Whether or not that's a good idea is... debatable. All types could also implement PartialOrd but always return None.
  • HashSet and HashMap could probably be changed to allow any T: PartialHash but that's at best a breaking change and at worst a stupid one.

So the aforementioned caching example could be implemented as follows:

fn cache_result(hash_map: &mut HashMap<u64, Whatever>, string: String, maybe_hash_set: Option<HashSet<Whatever2>>, answer: Whatever) -> Result<(), ()> {
    if let Some(hash) = (string, maybe_hash_set).partial_hash() {
        hash_map.insert(hash, answer);
        Ok(())
    } else {
        Err(())
    }
}

I realize this is a pretty niche situation I'm trying to solve, but it would be quite handy for some of my work.

2

I don't think your idea as presented could fly without some sort of specialization or negative reasoning or negative trait implementations, coherence, and bounds. Try to define the trait yourself and write some blanket implementations so Option<X> and (T, U) do everything you said or implied.

// Always `Some` case
impl<X: Hash> PartialHash for Option<X> { .. }
// Mapping case -- overlapping implementation
impl<X: ???> PartialHash for Option<X> { .. }
3

I don't think this is an improvement over Hash, which already allows what you're trying to do. You can force a type to be Hash by wrapping it in a type that has a no-op for a Hash impl, and there's no danger besides producing low-quality hashes. HashMap wouldn't be able to do anything different for None values, but perhaps PartialHash could be useful if you were creating a hybrid HashMap/BTreeMap data structure. That would only apply to types that are completely unhashable, so your String + Option<HashSet> wouldn't need it.

It might be nice if the Hash derive macro could skip non-hashable fields[1]. But I don't think having a separate trait is useful.

If this is your real issue, you can make a wrapper type that implements Hash for HashSet. There is one hashable piece of data: the length. It's not enough to make it generally viable for hashing by itself, but since you have other data being hashed, this should do fine. There may be more hashable data if you have a certain type within the HashSet, for example you could hash the total length of all elements in HashSet<Vec<T>>.

use core::hash::{Hash, Hasher};
use std::collections::HashSet;

pub struct HashableHashSet<T>(pub HashSet<T>);

impl<T> Hash for HashableHashSet<T> {
    fn hash<H>(&self, state: &mut H)
    where
        H: Hasher,
    {
        self.0.len().hash(state);
    }
}

If you expect your Strings to be sufficiently unique (maybe the set just contains the letters in the string), then maybe don't bother with this. Just implement Hash and ignore the Option<HashSet<_>> field.

  1. you would need to indicate these to the macro manually, but it's easier than writing out the whole impl ↩ī¸Ž

4

FYI that's in derivative.

1 Like
5

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.