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::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    fn hashed(&self) -> Self::Output;
29}
30
31impl<T: ::std::hash::Hash> Hashable for T {
32    type Output = u64;
33    fn hashed(&self) -> u64 {
34        let mut h: ::fnv::FnvHasher = Default::default();
35        self.hash(&mut h);
36        h.finish()
37    }
38}