hash_rings/
jump.rs

1//! Hashing ring implemented using jump hashing.
2
3use crate::util;
4use std::collections::hash_map::RandomState;
5use std::hash::{BuildHasher, Hash};
6
7/// A hashing ring implemented using jump hashing.
8///
9/// Jump hashing is based on using a hash of the key as the seed for a random number generator and
10/// using it to jump forward in a list of nodes until it falls off the end. The last node it lands
11/// on is the result.
12///
13/// Jump hashing is very fast and executes in `O(ln n)` time. It also has no memory overhead and has
14/// virtually perfect key distribution. However, the main limitation of jump hashing is that it
15/// returns an integer in the range [0, nodes) and it does not support arbitrary node names.
16///
17/// # Examples
18///
19/// ```
20/// use hash_rings::jump::Ring;
21/// use std::collections::hash_map::DefaultHasher;
22/// use std::hash::BuildHasherDefault;
23///
24/// type DefaultBuildHasher = BuildHasherDefault<DefaultHasher>;
25///
26/// let ring = Ring::with_hasher(DefaultBuildHasher::default(), 100);
27///
28/// assert_eq!(ring.get_node(&"foo"), 8);
29/// assert_eq!(ring.nodes(), 100);
30/// ```
31pub struct Ring<H = RandomState> {
32    nodes: u32,
33    hash_builder: H,
34}
35
36impl Ring<RandomState> {
37    /// Constructs a new `Ring` with a specified number of nodes.
38    ///
39    /// # Panics
40    ///
41    /// Panics if the number of nodes is zero.
42    ///
43    /// # Examples
44    ///
45    /// ```
46    /// use hash_rings::jump::Ring;
47    ///
48    /// let ring: Ring = Ring::new(100);
49    /// ```
50    pub fn new(nodes: u32) -> Self {
51        Self::with_hasher(Default::default(), nodes)
52    }
53}
54
55impl<H> Ring<H> {
56    /// Constructs a new `Ring` with a specified number of nodes and hash builder.
57    ///
58    /// # Panics
59    ///
60    /// Panics if the number of nodes is zero.
61    ///
62    /// # Examples
63    ///
64    /// ```
65    /// use hash_rings::jump::Ring;
66    /// use std::collections::hash_map::DefaultHasher;
67    /// use std::hash::BuildHasherDefault;
68    ///
69    /// type DefaultBuildHasher = BuildHasherDefault<DefaultHasher>;
70    ///
71    /// let ring: Ring<_> = Ring::with_hasher(DefaultBuildHasher::default(), 100);
72    /// ```
73    pub fn with_hasher(hash_builder: H, nodes: u32) -> Self {
74        assert!(nodes >= 1);
75        Self {
76            hash_builder,
77            nodes,
78        }
79    }
80
81    /// Returns the node associated with a key.
82    ///
83    /// # Examples
84    ///
85    /// ```
86    /// use hash_rings::jump::Ring;
87    /// use std::collections::hash_map::DefaultHasher;
88    /// use std::hash::BuildHasherDefault;
89    ///
90    /// type DefaultBuildHasher = BuildHasherDefault<DefaultHasher>;
91    ///
92    /// let ring = Ring::with_hasher(DefaultBuildHasher::default(), 100);
93    /// assert_eq!(ring.get_node(&"foo"), 8);
94    /// ```
95    pub fn get_node<T>(&self, key: &T) -> u32
96    where
97        T: Hash,
98        H: BuildHasher,
99    {
100        let mut h = util::gen_hash(&self.hash_builder, key);
101        let mut i: i64 = -1;
102        let mut j: i64 = 0;
103
104        while j < i64::from(self.nodes) {
105            i = j;
106            h = h.wrapping_mul(2_862_933_555_777_941_757).wrapping_add(1);
107            j = (((i.wrapping_add(1)) as f64) * ((1i64 << 31) as f64)
108                / (((h >> 33).wrapping_add(1)) as f64)) as i64;
109        }
110        i as u32
111    }
112
113    /// Returns the number of nodes in the ring.
114    ///
115    /// # Examples
116    ///
117    /// ```
118    /// use hash_rings::jump::Ring;
119    ///
120    /// let ring = Ring::new(100);
121    /// assert_eq!(ring.nodes(), 100);
122    /// ```
123    pub fn nodes(&self) -> u32 {
124        self.nodes
125    }
126}
127
128#[cfg(test)]
129mod tests {
130    use super::Ring;
131    use crate::test_util::BuildDefaultHasher;
132
133    #[test]
134    #[should_panic]
135    fn test_new_zero_nodes() {
136        let _ring = Ring::with_hasher(BuildDefaultHasher::default(), 0);
137    }
138
139    #[test]
140    fn test_get_node() {
141        let ring = Ring::with_hasher(BuildDefaultHasher::default(), 100);
142        assert_eq!(ring.get_node(&"foo"), 8);
143    }
144
145    #[test]
146    fn test_nodes() {
147        let ring = Ring::with_hasher(BuildDefaultHasher::default(), 100);
148        assert_eq!(ring.nodes(), 100);
149    }
150}
hash_rings/jump.rs

hash_rings/
jump.rs
