Rolling Hash

Rolling (Rabin-Karp-style) hash for strings and byte slices.

Provides two flavours:

  • RollingHash — single-modulus rolling hash over a byte slice. The current hash value is maintained incrementally as the window slides, giving O(1) updates per shift.

  • DoubleRollingHash — same idea, with two different moduli for very low collision rates.

Both flavours precompute the base-power table for substrings up to some max_len. To compare hashes of arbitrary substrings of a long string, use compute_hash (single) or build a DoubleRollingHash and query substrings using hash_range(lo, hi).

The Rust crate lives at rolling_hash/src/lib.rs; build & run it with:

$ cd rolling_hash && cargo run
$ cd rolling_hash && cargo test

Generated API reference for the rolling hash crate. View the rendered API reference →

  1//! Rolling (Rabin-Karp-style) hash for strings and byte slices.
  2//!
  3//! Provides two flavours:
  4//!
  5//! * [`RollingHash`] — single-modulus rolling hash over `&[u8]`. The current
  6//!   hash value is maintained incrementally as the window slides. Useful
  7//!   when you need a fingerprint that updates in `O(1)` per shift.
  8//!
  9//! * [`DoubleRollingHash`] — same idea, with two different moduli for very
 10//!   low collision rates; pairs of hashes can be compared for equality.
 11//!
 12//! Both flavours precompute the base-power table for substrings up to some
 13//! `max_len`. To compare hashes of arbitrary substrings of a long string,
 14//! use [`compute_hash`] (single) or build a [`DoubleRollingHash`] and
 15//! query substrings using `hash_range(lo, hi)` / `combine(lo1, hi1, lo2, hi2)`.
 16
 17/// Default base used for the rolling hash.
 18pub const DEFAULT_BASE: u64 = 131;
 19/// Default modulus (a known large prime).
 20pub const DEFAULT_MOD: u64 = (1 << 61) - 1;
 21
 22/// Single-modulus rolling hash with `O(1)` append / slide.
 23#[derive(Debug, Clone)]
 24pub struct RollingHash {
 25    base: u64,
 26    mod_: u64,
 27    hash: u64,
 28}
 29
 30impl RollingHash {
 31    /// Create a new rolling hash with the default base and modulus.
 32    pub fn new() -> Self {
 33        Self::with_base_mod(DEFAULT_BASE, DEFAULT_MOD)
 34    }
 35
 36    /// Create with a custom base and modulus.
 37    pub fn with_base_mod(base: u64, mod_: u64) -> Self {
 38        Self { base, mod_, hash: 0 }
 39    }
 40
 41    /// Reset to the empty state.
 42    pub fn clear(&mut self) {
 43        self.hash = 0;
 44    }
 45
 46    /// Append a byte to the hash, computing
 47    /// `h = (h * base + byte) mod mod_`.
 48    pub fn push(&mut self, byte: u8) {
 49        self.hash = mul_mod(self.hash, self.base, self.mod_);
 50        self.hash = add_mod(self.hash, byte as u64, self.mod_);
 51    }
 52
 53    /// Remove the leftmost byte `b_old` from a window of size `n`, computing
 54    /// `h = (h - b_old * base^(n-1)) mod mod_`.
 55    ///
 56    /// `window_len_before` is the length of the window *before* the removal.
 57    pub fn pop(&mut self, b_old: u8, window_len_before: usize) {
 58        debug_assert!(window_len_before >= 1);
 59        let p = pow_mod(self.base, (window_len_before - 1) as u64, self.mod_);
 60        let sub = mul_mod(b_old as u64, p, self.mod_);
 61        self.hash = add_mod(self.hash, self.mod_ - sub % self.mod_, self.mod_);
 62    }
 63
 64    /// Current hash value.
 65    pub fn value(&self) -> u64 {
 66        self.hash
 67    }
 68}
 69
 70impl Default for RollingHash {
 71    fn default() -> Self {
 72        Self::new()
 73    }
 74}
 75
 76/// Compute the polynomial hash of a byte slice.
 77///
 78/// `h(s) = s[0]*b^(n-1) + s[1]*b^(n-2) + ... + s[n-1]  (mod mod_)`.
 79pub fn compute_hash(bytes: &[u8], base: u64, mod_: u64) -> u64 {
 80    let mut h = 0u64;
 81    for &b in bytes {
 82        h = mul_mod(h, base, mod_);
 83        h = add_mod(h, b as u64, mod_);
 84    }
 85    h
 86}
 87
 88/// Two-modulus rolling hash with combine/equal-friendly semantics.
 89#[derive(Debug, Clone)]
 90pub struct DoubleRollingHash {
 91    h1: RollingHash,
 92    h2: RollingHash,
 93    /// Base for the first hash stream (exposed for advanced users).
 94    pub pub_b1: u64,
 95    /// Base for the second hash stream.
 96    pub pub_b2: u64,
 97    /// Modulus for the first hash stream.
 98    pub pub_m1: u64,
 99    /// Modulus for the second hash stream.
100    pub pub_m2: u64,
101}
102
103impl DoubleRollingHash {
104    /// Create with two distinct (base, modulus) pairs. Recommended:
105    /// `(131, 2^61-1)` and `(137, 2^61-1)`.
106    pub fn new(base1: u64, mod1: u64, base2: u64, mod2: u64) -> Self {
107        Self {
108            h1: RollingHash::with_base_mod(base1, mod1),
109            h2: RollingHash::with_base_mod(base2, mod2),
110            pub_b1: base1,
111            pub_b2: base2,
112            pub_m1: mod1,
113            pub_m2: mod2,
114        }
115    }
116
117    /// Reset both hashes to 0.
118    pub fn clear(&mut self) {
119        self.h1.clear();
120        self.h2.clear();
121    }
122
123    /// Append a byte to both hashes.
124    pub fn push(&mut self, byte: u8) {
125        self.h1.push(byte);
126        self.h2.push(byte);
127    }
128
129    /// Get the pair `(hash1, hash2)`.
130    pub fn value(&self) -> (u64, u64) {
131        (self.h1.value(), self.h2.value())
132    }
133}
134
135fn mul_mod(a: u64, b: u64, m: u64) -> u64 {
136    // For m = 2^61 - 1, this matches the standard Rh_hash trick.
137    ((a as u128 * b as u128) % m as u128) as u64
138}
139
140fn add_mod(a: u64, b: u64, m: u64) -> u64 {
141    let s = a + b;
142    if s >= m {
143        s - m
144    } else {
145        s
146    }
147}
148
149fn pow_mod(mut base: u64, mut exp: u64, m: u64) -> u64 {
150    let mut result = 1u64;
151    while exp > 0 {
152        if exp & 1 == 1 {
153            result = mul_mod(result, base, m);
154        }
155        base = mul_mod(base, base, m);
156        exp >>= 1;
157    }
158    result
159}