differential_dataflow/hashable.rs
1//! Traits and types related to the distribution of data.
2//!
3//! These traits and types are in support of a flexible approach to data distribution and organization,
4//! in which we might like to more explicitly manage how certain types are handled. Although the term
5//! "hashing" is used throughout, it is a misnomer; these traits relate to extracting reasonably distributed
6//! integers from the types, and hashing happens to be evocative of this.
7//!
8//! Differential dataflow operators need to co-locate data that are equivalent so that they may have
9//! the differences consolidated, and eventually cancelled. The chose approach is to extract an integer
10//! from the keys of the data, ensuring that elements with the same key arrive at the same worker, where
11//! the consolidation can occur.
12//!
13//! The intent is that types should be able to indicate how this integer is determined, so that general
14//! data types can use a generic hash function, where as more specialized types such as uniformly
15//! distributed integers can perhaps do something simpler (like report their own value).
16
17use std::hash::{BuildHasher, Hasher};
18
19/// Types with a `hashed` method, producing an unsigned output of some type.
20///
21/// The output type may vary from a `u8` up to a `u64`, allowing types with simple keys
22/// to communicate this through their size. Certain algorithms, for example radix sorting,
23/// can take advantage of the smaller size.
24pub trait Hashable {
25 /// The type of the output value.
26 type Output: Into<u64>+Copy+Ord;
27 /// A well-distributed integer derived from the data.
28 ///
29 /// The blanket `Hash` implementation is deterministic for a fixed build and target.
30 /// Its hash values are not a persistent format and may change with dependencies.
31 fn hashed(&self) -> Self::Output;
32}
33
34impl<T: ::std::hash::Hash> Hashable for T {
35 type Output = u64;
36 fn hashed(&self) -> u64 {
37 // Exchanges must use the same seed in every process.
38 let mut h = foldhash::quality::FixedState::with_seed(0).build_hasher();
39 self.hash(&mut h);
40 h.finish()
41 }
42}