Skip to main content
Mapagam

Implementing String Hashing and Rolling Hash

1. Understanding Polynomial Hashing

Property Description Values
hash(x) Polynomial hash function h = (h * base + x) % mod
base Base for polynomial hashing 31 or 257
mod Modulus for hash value 10^9 + 7 or 2^64 - 1

Example: Polynomial Hashing Implementation

function polynomialHash(str, base = 31, mod = 1000000007) {
    let hash = 0;
    for (let i = 0; i < str.length; i++) {
        hash = (hash * base + str.charCodeAt(i)) % mod;
    }
    return hash;
}

console.log(polynomialHash("hello")); // Example output: 123456789
Note: Polynomial hashing is used in string matching algorithms like Rabin-Karp to efficiently compute hash values for substrings.

2. Implementing Single Hash Function

Method Description Time Complexity Space Complexity
hash(string) Computes a hash value for the input string using polynomial rolling hash O(n) O(1)

Example: Basic Hash Function Implementation

function hash(string, base = 31, mod = 1e9 + 7) {
    let result = 0;
    for (let i = 0; i < string.length; i++) {
        result = (result * base + string.charCodeAt(i)) % mod;
    }
    return result;
}

console.log(hash("hello")); // Example hash value
Note: The base and modulus values can be adjusted for different hash distributions or to avoid collisions in specific use cases.

3. Implementing Double Hashing

Component Description Implementation
Hash Function Primary hash function h1(k) = k mod m
Secondary Hash Function Secondary hash function to resolve collisions h2(k) = p - (k mod p)
Probe Sequence Double hashing probe sequence (h1(k) + i * h2(k)) mod m

Example: Double Hashing Implementation in JavaScript

class DoubleHashing {
  constructor(size = 10) {
    this.size = size;
    this.table = new Array(size).fill(null);
    this.deleted = Symbol("deleted");
  }

  h1(key) {
    return key % this.size;
  }

  h2(key) {
    const p = 7; // Prime number less than size
    return p - (key % p);
  }

  insert(key, value) {
    let i = 0;
    while (i < this.size) {
      const index = (this.h1(key) + i * this.h2(key)) % this.size;
      if (this.table[index] === null || this.table[index] === this.deleted) {
        this.table[index] = { key, value };
        return;
      }
      i++;
    }
    throw new Error("Hash table is full");
  }

  search(key) {
    let i = 0;
    while (i < this.size) {
      const index = (this.h1(key) + i * this.h2(key)) % this.size;
      if (this.table[index] === null) return null;
      if (this.table[index] !== this.deleted && this.table[index].key === key) {
        return this.table[index].value;
      }
      i++;
    }
    return null;
  }

  delete(key) {
    let i = 0;
    while (i < this.size) {
      const index = (this.h1(key) + i * this.h2(key)) % this.size;
      if (this.table[index] === null) return false;
      if (this.table[index] !== this.deleted && this.table[index].key === key) {
        this.table[index] = this.deleted;
        return true;
      }
      i++;
    }
    return false;
  }
}

// Example usage:
const hashTable = new DoubleHashing(10);
hashTable.insert(12, "value1");
hashTable.insert(25, "value2");
console.log(hashTable.search(12)); // "value1"
Note: Double hashing reduces clustering compared to linear probing, improving performance in hash table operations.

4. Calculating Substring Hash

Operation Description Implementation Notes
hash(string) Computes hash value of a string using polynomial rolling hash 
function hash(s) {
  let h = 0;
  const base = 31;
  for (let i = 0; i < s.length; i++) {
    h = (h * base + s.charCodeAt(i)) % MOD;
  }
  return h;
}
 Base 31 is commonly used for string hashing
substringHash(s, l, r) Computes hash of substring s[l..r] 
function substringHash(s, l, r) {
  const base = 31;
  let h = 0;
  for (let i = l; i <= r; i++) {
    h = (h * base + s.charCodeAt(i)) % MOD;
  }
  return h;
}
 Can be optimized with precomputed powers
rollingHash(s, windowSize) Generates hash for all substrings of given window size 
function rollingHash(s, windowSize) {
  const base = 31;
  const hashes = [];
  let h = 0;

  // Compute hash for first window
  for (let i = 0; i < windowSize; i++) {
    h = (h * base + s.charCodeAt(i)) % MOD;
  }
  hashes.push(h);

  // Rolling hash for remaining windows
  const power = modPow(base, windowSize - 1, MOD);
  for (let i = windowSize; i < s.length; i++) {
    h = (h - power * s.charCodeAt(i - windowSize)) % MOD;
    h = (h * base + s.charCodeAt(i)) % MOD;
    hashes.push(h);
  }
  return hashes;
}
 Uses modular arithmetic to avoid recomputation

Example: Rolling Hash for Pattern Matching

const MOD = 1000000007;
const BASE = 31;

function modPow(base, exp, mod) {
  let result = 1;
  base %= mod;
  while (exp > 0) {
    if (exp % 2 === 1) result = (result * base) % mod;
    base = (base * base) % mod;
    exp >>= 1;
  }
  return result;
}

function findPattern(text, pattern) {
  const patternHash = hash(pattern);
  const textHashes = rollingHash(text, pattern.length);

  for (let i = 0; i < textHashes.length; i++) {
    if (textHashes[i] === patternHash) {
      // Verify match to handle hash collisions
      if (text.slice(i, i + pattern.length) === pattern) {
        return i;
      }
    }
  }
  return -1;
}

function hash(s) {
  let h = 0;
  for (let i = 0; i < s.length; i++) {
    h = (h * BASE + s.charCodeAt(i)) % MOD;
  }
  return h;
}

function rollingHash(s, windowSize) {
  const hashes = [];
  let h = 0;
  const power = modPow(BASE, windowSize - 1, MOD);

  for (let i = 0; i < windowSize; i++) {
    h = (h * BASE + s.charCodeAt(i)) % MOD;
  }
  hashes.push(h);

  for (let i = windowSize; i < s.length; i++) {
    h = (h - power * s.charCodeAt(i - windowSize)) % MOD;
    h = (h * BASE + s.charCodeAt(i)) % MOD;
    hashes.push(h);
  }
  return hashes;
}

// Usage
const text = "hello world";
const pattern = "world";
console.log(findPattern(text, pattern)); // 6
Note: Hash collisions can occur; always verify actual matches when using hash values for pattern matching.

5. Implementing Rolling Hash Update

Example: Rolling Hash Update Function

function updateRollingHash(oldChar, newChar, oldHash, windowSize, base, mod) {
    // Remove contribution of the leftmost character
    oldHash = (oldHash - oldChar * pow(base, windowSize - 1, mod)) % mod;
    // Add contribution of the new rightmost character
    oldHash = (oldHash * base + newChar) % mod;
    // Ensure hash is positive
    return (oldHash + mod) % mod;
}

// Helper function to compute power modulo
function pow(base, exp, mod) {
    let result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp % 2 === 1) result = (result * base) % mod;
        exp = Math.floor(exp / 2);
        base = (base * base) % mod;
    }
    return result;
}

// Example usage:
const base = 256;
const mod = 1000000007;
let hash = 123456; // initial hash
const oldChar = 65; // 'A'
const newChar = 66; // 'B'
const windowSize = 5;

const updatedHash = updateRollingHash(oldChar, newChar, hash, windowSize, base, mod);
console.log(updatedHash); // Updated rolling hash value
Parameter Description Values
oldChar ASCII value of the character to be removed from the window number
newChar ASCII value of the new character to be added to the window number
oldHash Current hash value of the window number
windowSize Length of the sliding window number
base Base for polynomial rolling hash (e.g., 256) number
mod Modulus for hash computation (e.g., 1000000007) number
Note: The update operation assumes that the hash was computed using a polynomial rolling hash function with a base and modulus.
Warning: Ensure that mod is a large prime number to minimize hash collisions.

Key Points

  • The rolling hash update efficiently computes a new hash by removing one character and adding another.
  • It avoids recomputing the entire hash from scratch, which is crucial for performance in string matching algorithms.
  • Modular arithmetic ensures that hash values remain within a manageable range.

6. Solving Longest Common Substring

Example: Using Rolling Hash for Longest Common Substring

function longestCommonSubstring(str1, str2) {
  const base = 256;
  const mod = 1000000007;

  let left = 0;
  let right = Math.min(str1.length, str2.length);
  let result = "";

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const hash1 = new RollingHash(str1, base, mod);
    const hash2 = new RollingHash(str2, base, mod);

    let found = false;
    const substr1 = new Set();

    for (let i = 0; i <= str1.length - mid; i++) {
      const hash = hash1.getHash(i, i + mid);
      substr1.add(hash);
    }

    for (let i = 0; i <= str2.length - mid; i++) {
      const hash = hash2.getHash(i, i + mid);
      if (substr1.has(hash)) {
        result = str2.substring(i, i + mid);
        found = true;
        break;
      }
    }

    if (found) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return result;
}

class RollingHash {
  constructor(str, base, mod) {
    this.str = str;
    this.base = base;
    this.mod = mod;
    this.powers = [1];
    this.hashes = [0];

    for (let i = 1; i <= str.length; i++) {
      this.powers[i] = (this.powers[i - 1] * base) % mod;
      this.hashes[i] = (this.hashes[i - 1] * base + str.charCodeAt(i - 1)) % mod;
    }
  }

  getHash(start, end) {
    const hash = (this.hashes[end] - (this.hashes[start] * this.powers[end - start]) % this.mod + this.mod) % this.mod;
    return hash;
  }
}

// Example usage:
const str1 = "GeeksforGeeks";
const str2 = "GeeksQuiz";
console.log(longestCommonSubstring(str1, str2)); // Output: "Geeks"
Property Description Notes
base Base value for polynomial rolling hash Typically 256 or 31
mod Modulus for hash computation Large prime number to reduce collisions
str Input string for hashing Used to compute rolling hash values
Note: The rolling hash technique allows for efficient substring matching by precomputing hash values of all substrings of a given length.
Warning: Hash collisions can occur, leading to incorrect results. Using a large prime modulus helps minimize this risk.

7. Finding Repeated Substring

Property Description Usage
hash Hash value of the current substring Used for comparison with other substrings
base Base value for polynomial rolling hash Typically 256 or 31
mod Modulus for hash computation Large prime number to prevent overflow

Example: Rolling Hash for Repeated Substring Detection

function findRepeatedSubstring(s) {
  const n = s.length;
  const base = 256;
  const mod = 1000000007;

  let hash = 0;
  let power = 1;

  const hashes = new Map();

  for (let i = 0; i < n; i++) {
    hash = (hash * base + s.charCodeAt(i)) % mod;
    if (i >= 3) {
      if (hashes.has(hash)) {
        return true;
      }
      hashes.set(hash, true);
    }
  }

  return false;
}
Note: This approach uses a fixed window size of 4 characters to detect repeated substrings.

8. Implementing Pattern Matching

Algorithm Description Time Complexity Space Complexity
Naive String Matching Compares pattern with every substring of text O(n*m) O(1)
KMP (Knuth-Morris-Pratt) Uses failure function to avoid redundant comparisons O(n+m) O(m)
Rabin-Karp Uses hash values to find pattern matches O(n+m) average O(1)

Example: KMP Algorithm Implementation

function buildFailureFunction(pattern) {
  const failure = new Array(pattern.length).fill(0);
  let j = 0;

  for (let i = 1; i < pattern.length; i++) {
    while (j > 0 && pattern[i] !== pattern[j]) {
      j = failure[j - 1];
    }

    if (pattern[i] === pattern[j]) {
      j++;
    }

    failure[i] = j;
  }

  return failure;
}

function kmpSearch(text, pattern) {
  const failure = buildFailureFunction(pattern);
  let j = 0;

  for (let i = 0; i < text.length; i++) {
    while (j > 0 && text[i] !== pattern[j]) {
      j = failure[j - 1];
    }

    if (text[i] === pattern[j]) {
      j++;
    }

    if (j === pattern.length) {
      return i - pattern.length + 1;
    }
  }

  return -1;
}

Example: Rabin-Karp Implementation

function rabinKarp(text, pattern) {
  const d = 256; // Number of characters in alphabet
  const q = 101; // Prime number for hashing

  const n = text.length;
  const m = pattern.length;

  let h = 1;
  for (let i = 0; i < m - 1; i++) {
    h = (h * d) % q;
  }

  let p = 0; // Hash value for pattern
  let t = 0; // Hash value for text

  // Calculate hash values for pattern and first window of text
  for (let i = 0; i < m; i++) {
    p = (p * d + pattern.charCodeAt(i)) % q;
    t = (t * d + text.charCodeAt(i)) % q;
  }

  // Slide the pattern over text one by one
  for (let i = 0; i <= n - m; i++) {
    if (p === t) {
      let j;
      for (j = 0; j < m; j++) {
        if (text[i + j] !== pattern[j]) break;
      }

      if (j === m) return i;
    }

    // Calculate hash value for next window of text
    if (i < n - m) {
      t = (d * (t - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % q;
      if (t < 0) t += q;
    }
  }

  return -1;
}
Note: The KMP algorithm is preferred when the pattern is long and has repeated subpatterns, while Rabin-Karp is useful for multiple pattern searches or when hash collisions are rare.

9. Solving Palindrome Hashing

Property Description Notes
hash string Hash value of the string
length number Length of the string
isPalindrome boolean Whether the string is a palindrome

Example: Check if a string is a palindrome using hashing

function isPalindromeHash(str) &#123;
  const n = str.length;
  let left = 0;
  let right = n - 1;
  const base = 31;
  const mod = 1000000007;

  let hashLeft = 0;
  let hashRight = 0;
  let power = 1;

  while (left < right) &#123;
    hashLeft = (hashLeft * base + str[left].charCodeAt(0)) % mod;
    hashRight = (hashRight + power * str[right].charCodeAt(0)) % mod;
    power = (power * base) % mod;
    left++;
    right--;
  &#125;

  return hashLeft === hashRight;
&#125;
Note: This method uses rolling hash to compare prefixes and suffixes of the string. It's efficient for large strings but may have collisions.

10. Selecting Hash Parameters

Parameter Description Recommended Value Notes
base Base for polynomial rolling hash 256 Should be larger than the size of the alphabet. Common values: 256 (ASCII), 31 (Java String hash), 37 (used in some C implementations)
modulus Prime number for modulo operation 2^61 - 1 Large prime to reduce collisions. Must be larger than the maximum possible hash value. Often chosen as a Mersenne prime (2^p - 1) for efficient computation
windowSize Length of the substring to hash Depends on use case Must be less than or equal to the length of the input string. Typically 10–100 for substring matching

Example: Selecting Parameters for Rolling Hash

const base = 256;
const modulus = 2**61 - 1; // Mersenne prime
const windowSize = 10;

// Example of computing hash for a substring
function rollingHash(str, base, modulus, windowSize) {
  let hash = 0;
  for (let i = 0; i < windowSize; i++) {
    hash = (hash * base + str.charCodeAt(i)) % modulus;
  }
  return hash;
}

const text = "hello world";
const hashValue = rollingHash(text, base, modulus, windowSize);
console.log(hashValue); // Example hash value
Note: Choosing a large prime modulus like 2^61 - 1 helps in reducing hash collisions, especially when dealing with large datasets.
Warning: Using a small base or modulus can lead to many hash collisions, degrading performance of algorithms that rely on hashing.

11. Handling Hash Collisions

Collision Type Description Technique Notes
Chaining Each hash bucket stores a list of elements LinkedList<T> Simple to implement, handles many collisions well
Open Addressing When a collision occurs, probe for the next available slot Linear Probing, Quadratic Probing More memory efficient, but can suffer from clustering
Double Hashing Use a second hash function to compute the probe sequence h1(k) + i * h2(k) Better distribution than linear probing, reduces clustering

Example: Chaining Implementation

class HashTable<K, V> {
    private LinkedList<Entry<K, V>>[] buckets;
    
    public void put(K key, V value) {
        int index = hash(key);
        LinkedList<Entry<K, V>> bucket = buckets[index];
        for (Entry<K, V> entry : bucket) {
            if (entry.key.equals(key)) {
                entry.value = value;
                return;
            }
        }
        bucket.add(new Entry<>(key, value));
    }
    
    private int hash(K key) {
        return key.hashCode() % buckets.length;
    }
}

Example: Linear Probing

class LinearProbingHashTable<K, V> {
    private K[] keys;
    private V[] values;
    
    public void put(K key, V value) {
        int index = hash(key);
        while (keys[index] != null) {
            if (keys[index].equals(key)) {
                values[index] = value;
                return;
            }
            index = (index + 1) % keys.length;
        }
        keys[index] = key;
        values[index] = value;
    }
}
Note: The choice of collision handling method affects performance characteristics. Chaining is simpler to implement and more robust under high load, while open addressing can offer better cache locality.

Was this article helpful?

Related Cheat Sheets