F32/f64 should implement Hash

[pedrocr]

I’d say that any time you can detect that the values are different through the normal f32/f64 API the hashing should be different as well. And any time that you can only detect differences by doing a transmute to u32 or similar it’s fine if the hashing is the same.

By these rules and reading the docs we should have different hashes for +Inf, -Inf, +0, -0, NaN.

[vadimcn]

I’d say that any time you can detect that the values are different through the normal f32/f64 API the hashing should be different as well.

Right, but unfortunately, HashMap uses the Eq trait, which is derived from PartialEq used for overloading == and !=, so we can’t have it both ways at the same time.

[oli-obk]

@kennytm ordered_float is the workaround I’ll be using but it makes for very ugly code.

You can do

mod helper {
    pub type f32_helper = f32;
    pub type f64_helper = f64;
}
#[allow(non_camel_case_types)]
type f32 = ordered_float::OrderedFloat<helper::f32_helper>;
#[allow(non_camel_case_types)]
type f64 = ordered_float::OrderedFloat<helper::f64_helper>;

to shadow the f32 and f64 typename, so your code looks just like it would with regular f32 or f64

[eddyb]

Wrapping and unwrapping a newtype are the ugly operations on it though.

[pedrocr]

so we can’t have it both ways at the same time.

Not sure what you mean. If you can detect that the values are different with the API Eq should also return a difference.

[pedrocr]

Wrapping and unwrapping a newtype are the ugly operations on it though.

Indeed, I’ve had to write a bunch of boilerplate code to make the wrapping and unwrapping palatable:

pedrocr/rawloader/blob/2ccb92a3161009276f8a9e5ca0ef25e6d01d72f6/src/imageops/colorspaces.rs#L6-L20

[sfackler]

So should f32::NAN == f32::NAN and 0. != -0.? That would break backwards compatibility in a pretty fundamental way, as well as disagreeing with ~every other language in existence.

[pedrocr]

@sfackler If NAN!=NAN you’re going to have a bad time using f32 as keys in a hash table. But I see there are also math reasons for that to be like that. Personally I don’t care for Eq, my use case only requires Hash.

[dzamlo]

a hash of all those values that’s guaranteed to be different if the values are different. The use case is mostly for caching and I don’t care about false inequality only false equality.

I think that a hash works the opposite ways. If the values are the same, you have the guarantee that the hash is the same. But two different values can have the same hash (this a collision).

[pedrocr]

But two different values can have the same hash (this a collision).

Obviously no hash can guarantee no collisions (pigeon-hole principle and all) but if you start making +0 and -0 hash to the same value on purpose and then that makes a difference mathematically down the line I’ll have a problem of broken caching. It increasingly seems to me that at least for my usage just hashing the underlying bytes is ideal.

[Apanatshka]

I also needed a larger datastructure that might contain floats (though in practice rarely used) to implement Hash in my aterm crate. What I did was implement Eq/Hash based on the underlying bytes and I documented that you shouldn’t put floats in there if you’re going to use the Hash instance. I went so far as to call the module bad_idea to discourage use of it. It was the fastest way to “fix” problem.

[pedrocr]

What I did was implement Eq/Hashbased on the underlying bytes and I documented that you shouldn’t put floats in there if you’re going to use theHash instance.

This is pretty much my use case. It seems to me that the reason for not having hashing on f32/f64 is that someone might use those values as keys in a hash table. That will always be broken if we want to keep things like NAN != NAN. But there’s another set of use cases that just needs hashing as a cheap way to do aggregate equality comparison for things like caching and other cases where false-inequality is not really an issue. So maybe the solution is to have a way to implement Hash while at the same time disallowing floats as HashMap keys?

[Apanatshka]

I think that’s a good idea, perhaps a marker trait that Hash is “sane”, i.e. ok for HashMap use. Although in my case I’m reproducing old programs in Rust, which have the silly behaviour of allowing these datastructures with float in the key of a hashmap. Given that I’m porting the system from Java though, I should probably coalesce all NaN values in my Eq/Hash implementations, since that’s what Float.equals does as mentioned earlier in the thread.

[Nemo157]

I don’t see any reason that f32 / f64 can’t implement Hash because of HashMap, f32: !Eq so the bounds impl<K: Hash + Eq, V> HashMap<K, V, RandomState> will still disallow it from being used in a HashMap. I would call Eq the marker trait that Hash is sane (given that Hash matches PartialEq in all cases, that’s not explicitly stated in the docs but I feel like it should be).

+0 and -0 hash to the same value on purpose

I would expect that will be required though, even though f32 doesn’t implement Eq its Hash implementation should match its PartialEq implementation, given x == y then hash(x) == hash(y) MUST be true.

[pedrocr]

given x == y then hash(x) == hash(y) MUST be true

I think this is a broken result for f32 +0 and -1 since there’s specific API that can be used to check sign and thus that information leaks and can result in hash(x) == hash(y) but your_func(x) != your_func(y) which is not what you need for caching.

At least for caching uses transmuting to u32/u64 and hashing that would be fine. So maybe there should just be a way to tell #derive(Hash) to do that for structs?

[Nemo157]

That’s not broken, there is absolutely nothing guaranteeing that two different values hash to a different value,

impl Hash for f32 {
    fn hash<H>(&self, state: &mut H) where H: Hasher {
        state.write_u8(4);
    }
}

is a 100% valid implementation of Hash for f32.

If a type implements Eq then the contract for Hash states that it must satisfy if x == y: hash(x) == hash(y), but there are no other constraints on Hash.

If you care about +0 and -0 behaving differently you must check that yourself after receiving a matching hashed value. In that case you can’t use == directly on the f32 value since -0.0 == 0.0 is true, you will have to define your own equality comparison and use that instead.

[pedrocr]

That’s not broken, there is absolutely nothing guaranteeing that two different values hash to a different value

I don’t think there’s any remaining use case for hashing that doesn’t require that building a colision be an extremely difficult thing to do.

is a 100% valid implementation of Hash for f32.

It’s actually fully broken. Your HashTable is now a Vec and your software can now be victim of denial of service attacks by exploiting that fact. The use for old-school insecure hashes went away when it was demonstrated that non-secure hashes created exploitable software and thus secure and fast hashes were created.

If you care about +0 and -0 behaving differently you must check that yourself after receiving a matching hashed value.

All I’m saying is that it’s an extremely useful property that if hash(x) == hash(y) then it’s not possible to do myfunc(x) != myfunc(y). As it turns out float values make that hard to do with a single equality operator because for math you want one thing and for testing repeated values you want another thing. Other languages end up with several equality operators because of this.

Within the confines of the current rust implementation this may be unsolvable but it’s also not a very common use case. So having a way of telling #derive(Hash) to transmute to u32 would probably be the best idea to solve this.

[cuviper]

All I’m saying is that it’s an extremely useful property that if hash(x) == hash(y) then it’s not possible to do myfunc(x) != myfunc(y).

The rule is that x == y implies hash(x) == hash(y), but not the other way around. So the hash function alone tells you nothing about how myfunc will compare, even just for the identity function.

[pedrocr]

but not the other way around

I’m not saying x != y implies hash(x) != hash(y). That’s of course impossible to guarantee mathematically as you don’t have infinite bits in your hash. But if you use a cryptographic hash it can be true in practice as causing a collision is practically impossible unless you find a fault in the hash.

Now, even though it’s possible to avoid collisions in practice we would be guaranteeing them by setting hash(-0) == hash(+0). To me that’s something important to avoid because rust explicitely supports .is_sign_negative() and friends. We’d be setting hash(+0) == hash(-0) when it’s very easy to have myfunc(+0) != myfunc(-0). For caching applications of hashing that sucks and is completely avoidable.

[cuviper]

You said “not possible” before, and I doubt even your updated “practically impossible.” Rust’s Hash and Hasher produce a u64, which only needs about 5 billion items for a 50% probable birthday attack.

I agree that hash(-0) == hash(+0) is a trivial collision, but it’s consistent with what std::hash is designed for. I think this is just not the cryptographic hash you’re looking for…