jump_consistent_hash/
lib.rs

1#![deny(warnings)]
2
3//! Implements 'Jump Consistent Hash' from the paper
4//! [A Fast, Minimal Memory, Consistent Hash Algorithm](http://arxiv.org/abs/1406.2294)
5//! by John Lamping, Eric Veach (2014).
6
7const JUMP: u64 = 1 << 31;
8
9/// Takes a 64 bit key and the number of buckets, outputs a bucket number `0..buckets`.
10///
11/// # Examples
12///
13/// ```
14/// extern crate jump_consistent_hash as jch;
15/// assert_eq!(jch::hash(0, 60), 0);
16/// assert_eq!(jch::hash(1, 60), 55);
17/// assert_eq!(jch::hash(2, 60), 46);
18/// ```
19///
20pub fn hash(key: u64, buckets: usize) -> u32 {
21    let len = if buckets == 0 { 1 } else { buckets as i64 };
22    let mut k = key;
23    let mut b = -1;
24    let mut j = 0;
25    while j < len {
26        b = j;
27        k = k.wrapping_mul(2862933555777941757) + 1;
28        j = ((b + 1) as f64 * (JUMP as f64 / ((k >> 33) + 1) as f64)) as i64;
29    }
30    return b as u32;
31}
jump_consistent_hash/lib.rs

jump_consistent_hash/
lib.rs
