Polynomial Rolling Hash

Hash Function

Hash functions are used to map large data sets of elements of an arbitrary length (the keys) to smaller data sets of elements of a fixed length (the fingerprints).

The basic application of hashing is efficient testing of equality of keys by comparing their fingerprints.

A collision happens when two different keys have the same fingerprint. The way in which collisions are handled is crucial in most applications of hashing. Hashing is particularly useful in construction of efficient practical algorithms.

Rolling Hash

A rolling hash (also known as recursive hashing or rolling checksum) is a hash function where the input is hashed in a window that moves through the input.

A few hash functions allow a rolling hash to be computed very quickly — the new hash value is rapidly calculated given only the following data:

old hash value,
the old value removed from the window,
and the new value added to the window.

Polynomial String Hashing

An ideal hash function for strings should obviously depend both on the multiset of the symbols present in the key and on the order of the symbols. The most common family of such hash functions treats the symbols of a string as coefficients of a polynomial with an integer variable p and computes its value modulo an integer constant M:

The Rabin–Karp string search algorithm is often explained using a very simple rolling hash function that only uses multiplications and additions - polynomial rolling hash:

H(s0, s1, ..., sk) = s0 * pk-1 + s1 * pk-2 + ... + sk * p0

where p is a constant, and (s1, ... , sk) are the input characters.

For example we can convert short strings to key numbers by multiplying digit codes by powers of a constant. The three letter word ace could turn into a number by calculating:

key = 1 * 262 + 3 * 261 + 5 * 260

In order to avoid manipulating huge H values, all math is done modulo M.

H(s0, s1, ..., sk) = (s0 * pk-1 + s1 * pk-2 + ... + sk * p0) mod M

A careful choice of the parameters M, p is important to obtain “good” properties of the hash function, i.e., low collision rate.

This approach has the desirable attribute of involving all the characters in the input string. The calculated key value can then be hashed into an array index in the usual way:

function hash(key, arraySize) {
  const base = 13;

  let hash = 0;
  for (let charIndex = 0; charIndex < key.length; charIndex += 1) {
    const charCode = key.charCodeAt(charIndex);
    hash += charCode * (base ** (key.length - charIndex - 1));
  }

  return hash % arraySize;
}

The hash() method is not as efficient as it might be. Other than the character conversion, there are two multiplications and an addition inside the loop. We can eliminate one multiplication by using Horner's method:

a4 * x4 + a3 * x3 + a2 * x2 + a1 * x1 + a0 = (((a4 * x + a3) * x + a2) * x + a1) * x + a0

In other words:

Hi = (P * Hi-1 + Si) mod M

The hash() cannot handle long strings because the hashVal exceeds the size of int. Notice that the key always ends up being less than the array size. In Horner's method we can apply the modulo (%) operator at each step in the calculation. This gives the same result as applying the modulo operator once at the end, but avoids the overflow.

function hash(key, arraySize) {
  const base = 13;

  let hash = 0;
  for (let charIndex = 0; charIndex < key.length; charIndex += 1) {
    const charCode = key.charCodeAt(charIndex);
    hash = (hash * base + charCode) % arraySize;
  }

  return hash;
}

Polynomial hashing has a rolling property: the fingerprints can be updated efficiently when symbols are added or removed at the ends of the string (provided that an array of powers of p modulo M of sufficient length is stored). The popular Rabin–Karp pattern matching algorithm is based on this property

Code

PolynomialHash.js

const DEFAULT_BASE = 37;
const DEFAULT_MODULUS = 101;

export default class PolynomialHash {
  /**
   * @param {number} [base] - Base number that is used to create the polynomial.
   * @param {number} [modulus] - Modulus number that keeps the hash from overflowing.
   */
  constructor({ base = DEFAULT_BASE, modulus = DEFAULT_MODULUS } = {}) {
    this.base = base;
    this.modulus = modulus;
  }

  /**
   * Function that creates hash representation of the word.
   *
   * Time complexity: O(word.length).
   *
   * @param {string} word - String that needs to be hashed.
   * @return {number}
   */
  hash(word) {
    const charCodes = Array.from(word).map((char) => this.charToNumber(char));

    let hash = 0;
    for (let charIndex = 0; charIndex < charCodes.length; charIndex += 1) {
      hash *= this.base;
      hash += charCodes[charIndex];
      hash %= this.modulus;
    }

    return hash;
  }

  /**
   * Function that creates hash representation of the word
   * based on previous word (shifted by one character left) hash value.
   *
   * Recalculates the hash representation of a word so that it isn't
   * necessary to traverse the whole word again.
   *
   * Time complexity: O(1).
   *
   * @param {number} prevHash
   * @param {string} prevWord
   * @param {string} newWord
   * @return {number}
   */
  roll(prevHash, prevWord, newWord) {
    let hash = prevHash;

    const prevValue = this.charToNumber(prevWord[0]);
    const newValue = this.charToNumber(newWord[newWord.length - 1]);

    let prevValueMultiplier = 1;
    for (let i = 1; i < prevWord.length; i += 1) {
      prevValueMultiplier *= this.base;
      prevValueMultiplier %= this.modulus;
    }

    hash += this.modulus;
    hash -= (prevValue * prevValueMultiplier) % this.modulus;

    hash *= this.base;
    hash += newValue;
    hash %= this.modulus;

    return hash;
  }

  /**
   * Converts char to number.
   *
   * @param {string} char
   * @return {number}
   */
  charToNumber(char) {
    let charCode = char.codePointAt(0);

    // Check if character has surrogate pair.
    const surrogate = char.codePointAt(1);
    if (surrogate !== undefined) {
      const surrogateShift = 2 ** 16;
      charCode += surrogate * surrogateShift;
    }

    return charCode;
  }
}

SimplePolynomialHash.js

const DEFAULT_BASE = 17;

export default class SimplePolynomialHash {
  /**
   * @param {number} [base] - Base number that is used to create the polynomial.
   */
  constructor(base = DEFAULT_BASE) {
    this.base = base;
  }

  /**
   * Function that creates hash representation of the word.
   *
   * Time complexity: O(word.length).
   *
   * @assumption: This version of the function  doesn't use modulo operator.
   * Thus it may produce number overflows by generating numbers that are
   * bigger than Number.MAX_SAFE_INTEGER. This function is mentioned here
   * for simplicity and LEARNING reasons.
   *
   * @param {string} word - String that needs to be hashed.
   * @return {number}
   */
  hash(word) {
    let hash = 0;
    for (let charIndex = 0; charIndex < word.length; charIndex += 1) {
      hash += word.charCodeAt(charIndex) * (this.base ** charIndex);
    }

    return hash;
  }

  /**
   * Function that creates hash representation of the word
   * based on previous word (shifted by one character left) hash value.
   *
   * Recalculates the hash representation of a word so that it isn't
   * necessary to traverse the whole word again.
   *
   * Time complexity: O(1).
   *
   * @assumption: This function doesn't use modulo operator and thus is not safe since
   * it may deal with numbers that are bigger than Number.MAX_SAFE_INTEGER. This
   * function is mentioned here for simplicity and LEARNING reasons.
   *
   * @param {number} prevHash
   * @param {string} prevWord
   * @param {string} newWord
   * @return {number}
   */
  roll(prevHash, prevWord, newWord) {
    let hash = prevHash;

    const prevValue = prevWord.charCodeAt(0);
    const newValue = newWord.charCodeAt(newWord.length - 1);

    hash -= prevValue;
    hash /= this.base;
    hash += newValue * (this.base ** (newWord.length - 1));

    return hash;
  }
}

Hash Function

Rolling Hash

Polynomial String Hashing

Code

References

Practice

Hash Map / Set Lookup

On this page

Polynomial Rolling Hash

Hash FunctionCopy Anchor Link

Rolling HashCopy Anchor Link

Polynomial String HashingCopy Anchor Link

CodeCopy Anchor Link

ReferencesCopy Anchor Link

Practice

Hash Map / Set Lookup

On this page

Hash Function

Rolling Hash

Polynomial String Hashing

Code

References