`std::hash::Hash` documentation should suggest that the hash data should be prefix-free

[kpreid]

As discussed at Why does str.hash(…) pass an extra byte to the Hasher?: the code of impl Hash for &str specifically passes an extra 0xFF byte to the Hasher, so that values like ("ab", "c") and ("a", "bc") hash differently (added in 6066118).

This is a subtle property of hashing and should probably be mentioned in the documentation for Hash — particularly as the documentation for Hasher already says “you cannot assume, for example, that a write_u32 call is equivalent to four calls of write_u8” which could be sloppily interpreted as an expectation that a good Hasher implementation will handle “quoting” of sequential calls itself.

If an implementor of Hash fails to have this property, it could compromise the hash-DoS resistance that Rust tries to offer by default.

@rustbot labels: +A-docs +T-libs-api +C-enhancement

[fosskers]

Should hand-implementors of Hash instances keep this in mind as well? For instance, for the following struct:

struct User {
    name: String,
    age: u32,
    cool: bool,
}

rust-analyzer can auto-generate the following implementation (and I assume #[derive(Hash)] does the same):

impl Hash for User {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.name.hash(state);
        self.age.hash(state);
        self.cool.hash(state);
    }
}

There are no magic bytes here, as in str. Is that okay? Do we run the risk of this hashing to the same value as (String, u32, bool)? (Actually I will test this, one moment...)

[fosskers]

use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};

#[derive(Hash)]
struct User {
    name: String,
    age: u32,
    cool: bool,
}

struct Boozer {
    name: String,
    age: u32,
    cool: bool,
}

impl Hash for Boozer {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.name.hash(state);
        self.age.hash(state);
        self.cool.hash(state);
    }
}

fn hash<H: Hash>(h: H) {
    let mut hasher = DefaultHasher::new();
    h.hash(&mut hasher);
    println!("{}", hasher.finish());
}

fn main() {
    let user = User {
        name: "Jack".to_string(),
        age: 8,
        cool: true,
    };
    let boozer = Boozer {
        name: "Jack".to_string(),
        age: 8,
        cool: true,
    };
    let tuple = ("Jack".to_string(), 8, true);

    hash(user);
    hash(boozer);
    hash(tuple);
}

The results are:

#+RESULTS:
: 10970795962411125193
: 10970795962411125193
: 10970795962411125193

Is this expected?

[tczajka]

Is that okay? Do we run the risk of this hashing to the same value as (String, u32, bool)? (Actually I will test this, one moment...)

Different types hashing to the same value are not a problem. What is a problem is different (unequal) values of the same type hashing to the same value (for all Hashers).

[pierwill]

@rustbot claim

[cuviper]

Different types hashing to the same value are not a problem. What is a problem is different (unequal) values of the same type hashing to the same value (for all Hashers).

Collisions are inevitable, and it shouldn't matter between Hashers for the same reason it doesn't for different types.

I do agree that types should try to avoid collisions, as long as we make this kind of thing a suggestion of best practice, not stated as a hard requirement of the trait.

[tczajka]

Collisions are inevitable

Collisions in Hasher are inevitable. Collisions in Hash are not inevitable.

One benefit of not creating collisions in Hash is that it then is possible to implement a randomized Hasher with mathematically bounded small collision probability for any two unequal inputs (using universal hashing). If there is a deterministic collision in Hash, then it becomes impossible, because you have 100% collision probability for that pair of inputs.

[cuviper]

OK, that's a compelling distinction between the responsibilities of Hash and Hasher.

Is it always possible to do this perfectly on the Hash side? I suppose it must be -- if there's a feature that makes values different from an Eq perspective, that is an input that should also be used for hashing.

[kpreid]

[Trying again to set labels since I typoed the first one:]
@rustbot label: +A-docs +T-libs-api +C-enhancement

[tczajka]

Is it always possible to do this perfectly on the Hash side? I suppose it must be -- if there's a distinction makes them different from an Eq perspective, that is an input that should also be used for hashing.

I am not sure it's always possible, in theory you could imagine some contrived Eq algorithm that makes it computationally expensive to Hash in a way fully consistent with it, but I can't think of a practical example.

I think it would be fine to say that if can't come up with a proper Hash algorithm that has this property, you shouldn't implement Hash (perhaps you'd be better served by BTreeMap in that case).

[pierwill]

For the docs, would it make sense to discuss the case of impl Hash for &str in a new paragraph after this paragraph:

rust/library/core/src/hash/mod.rs

Lines 246 to 249 in ed93759

	/// This trait makes no assumptions about how the various `write_*` methods are
	/// defined and implementations of [`Hash`] should not assume that they work one
	/// way or another. You cannot assume, for example, that a [`write_u32`] call is
	/// equivalent to four calls of [`write_u8`].

?

The paragraph could start with something like:

For example, the code for impl Hash for &str passes an extra 0xFF byte to the Hasher, so that values like ("ab", "c") and ("a", "bc") hash differently.

[danielhenrymantilla]

Let's then note that BTreeMap Hash is thus currently "bugged" in that regard (c.f. my snippet in the URLO thread).