jumpch/
lib.rs

1use std::collections::hash_map::DefaultHasher;
2use std::hash::Hasher;
3
4/// `JumpHasher` is the wrapper for `Jump Consistent Hash` that implementing `Hasher` trait.
5/// `MUST TO KNOW`: This implementation finish never return value more than `u32`.
6///
7/// Example:
8/// ```rust
9/// use std::collections::hash_map::DefaultHasher;
10/// use std::hash::{Hash, Hasher};
11/// use jumpch::JumpHasher;
12///
13/// let mut hasher: JumpHasher<DefaultHasher> = JumpHasher::new(1000);
14///
15/// "test".hash(&mut hasher);
16///
17/// assert_eq!(hasher.finish(), 677)
18/// ```
19#[derive(Copy, Clone, Debug)]
20pub struct JumpHasher<H = DefaultHasher> {
21    slots: u32,
22    hasher: H,
23}
24
25impl<H: Hasher> JumpHasher<H> {
26    /// Create new JumpHasher with custom hasher
27    /// ```rust
28    /// use std::collections::hash_map::DefaultHasher;
29    /// use jumpch::JumpHasher;
30    ///
31    /// let hasher = JumpHasher::new_with_hasher(1000, DefaultHasher::new());
32    pub fn new_with_hasher(slots: u32, hasher: H) -> Self {
33        Self { slots, hasher }
34    }
35}
36
37impl<H: Hasher + Default> JumpHasher<H> {
38    /// Create new JumpHasher with default hasher
39    /// ```rust
40    /// use std::collections::hash_map::DefaultHasher;
41    /// use jumpch::JumpHasher;
42    ///
43    /// let hasher = JumpHasher::new(1000);
44    pub fn new(slots: u32) -> Self {
45        Self {
46            slots,
47            hasher: H::default(),
48        }
49    }
50}
51
52impl<H: Hasher> Hasher for JumpHasher<H> {
53    fn finish(&self) -> u64 {
54        hash(self.hasher.finish(), self.slots as i64) as u64
55    }
56
57    fn write(&mut self, bytes: &[u8]) {
58        self.hasher.write(bytes)
59    }
60}
61
62/// The base realization of `Jump Consistent Hash` algorithm.
63/// Usage example:
64/// ```rust
65/// use jumpch::hash;
66///
67/// assert_eq!(hash(123456, 1000), 176)
68/// ```
69pub fn hash(mut key: u64, slots: i64) -> u32 {
70    let (mut b, mut j) = (-1i64, 0i64);
71    while j < slots {
72        b = j;
73        key = key.wrapping_mul(2862933555777941757).wrapping_add(1);
74        j = ((b.wrapping_add(1) as f64) * (((1u64 << 31) as f64) / (((key >> 33) + 1) as f64)))
75            as i64;
76    }
77    b as u32
78}
79
80#[cfg(test)]
81mod tests {
82    use crate::JumpHasher;
83    use std::collections::hash_map::DefaultHasher;
84    use std::hash::{Hash, Hasher};
85
86    #[test]
87    fn test_struct() {
88        #[derive(Hash)]
89        struct Test(i32, String);
90
91        let test = Test(123456, "test".to_string());
92        check_range(&test);
93    }
94
95    #[test]
96    fn test_str() {
97        let test = "test 1";
98        check_range(&test);
99    }
100
101    #[test]
102    fn test_int() {
103        let test = 123456;
104        check_range(&test);
105    }
106
107    fn check_range<H: Hash>(test: &H) {
108        for slots in 0..1000 {
109            check_algorithm(slots, test);
110        }
111    }
112
113    fn check_algorithm<H: Hash>(slots: u32, test: H) {
114        let mut hasher: JumpHasher<DefaultHasher> = JumpHasher::new(slots);
115        test.hash(&mut hasher);
116        let hash = hasher.finish();
117
118        for i in (hash.wrapping_add(1) as u32)..slots.max(1) {
119            let mut hasher = JumpHasher::<DefaultHasher>::new(i);
120
121            test.hash(&mut hasher);
122
123            assert_eq!(hasher.finish(), hash)
124        }
125    }
126}
jumpch/lib.rs

jumpch/
lib.rs
