Tracking Issue for `BuildHasher::hash_one`

[scottmcm]

Feature gate: #![feature(build_hasher_simple_hash_one)]

This is a tracking issue for the hash_one method on the BuildHasher trait. This is a convenience method to make it easier to get the hash of a value, such as when implementing a hash table or when writing unit tests.

Public API

pub trait BuildHasher { // existing trait
    fn hash_one<T: Hash>(&self, x: T) -> u64
    where
        Self: Sized; // new method, with provided implementation
}

Steps / History

• Implementation: Add BuildHasher::hash_one as unstable #86151
• Add missing Self: Sized: Make BuildHasher object safe #88031
• Final commenting period (FCP)
• Stabilization PR

Unresolved Questions

• None yet.

[dtolnay]

Added where Self: Sized in #88031 in order to preserve object safety of BuildHasher.

[thomcc]

This API is unexpectedly useful for performance.

There are certain hash algorithms which can provide a (substantially) more efficient implementation if they know they aren't being used in a streaming scenario, and that they just need to hash a single input (such as a range of bytes).

xxHash is one of these — the streaming API is very much set up for the "hash a big file" use case, and has a large flat overhead to initialize the state for computing the streaming hash. That is, in a direct port, BuildHasher::build_hasher is very slow — much slower than the actual hashing for small keys.

However, it has a separate API for hashing a chunk of memory (with an optional seed), which you're supposed to use for hashtable keys and such. This API produces the same results as streaming (it wouldn't be much of a hash if this weren't the case), but is quite fast... far faster if this is all you need and you have small strings and such, as are common for hash-table keys.

I had some plans on how to subvert the issues here (by doing a less-direct port)... But I don't need to if this API exists (and is used in HashMap), so long as I provide a bunch of specializations on T (a pain, but worth it here).

I dunno if this was completely unintentional, or just not mentioned, but I had considered this basically unsolvable the way Rust's hashing APIs were designed^[1], so it's nice to be wrong.

I'll try to get benchmark numbers for this soonish.

---

[1]: I figured that we had traded perf for flexibility here, and that it was... a bit unfortunate, but probably worth it given that Rust's hashing APIs are far more convenient (and far less error-prone) than the ones in other langs which are hashcode-based.

[tkaitchuck]

Yes. This could give a significant performance gain particularly if the implementation was not held to the requirement that the resulting output be identical to what would have resulted by passing the value into the hasher and then calling finish(). This means that hashers can take advantage of knowing that all the data is present and more is not coming to reduce the amount of work done.

[thomcc]

I think it needs to return the same value, otherwise things like Borrow won't work. Users currently can implement Hash for their own types in terms of hashing a nested type, and have their Borrow implementation be correct. I suspect there's other things like this too.

I also think it would be very surprising if it returned different values, and suspect that it still can be done as efficiently in most cases, just more work to derive an efficient "closed-form" version of the computation.

[Amanieu]

I think this is a generally useful helper function that makes it easier for code to work with hashers. In particular, it replaces this rather cumbersome code for hashing a value:

fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 {
    let mut state = hash_builder.build_hasher();
    key.hash(&mut state);
    state.finish()
}

@rfcbot fcp merge

[rfcbot]

Team member @Amanieu has proposed to merge this. The next step is review by the rest of the tagged team members:

• @Amanieu
• @BurntSushi
• @dtolnay
• @joshtriplett
• @m-ou-se

No concerns currently listed.

Once a majority of reviewers approve (and at most 2 approvals are outstanding), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

[rfcbot]

🔔 This is now entering its final comment period, as per the review above. 🔔