Polynomial Hash

Definition

Definition

The Polynomial Hash Algorithm is a method used in computer science for hashing strings into unique numerical values. It involves treating the characters of a string as coefficients of a polynomial, evaluating this polynomial at a specific point, and taking the result modulo a prime number to avoid overflow and ensure uniform distribution of hash values

Explanation

Set the hash value to zero. Next, examine each character in the given string individually. As you process each character, modify the hash value using a specific calculation method. Ensure the hash value remains within a defined range. Lastly, provide the resulting hash value as the output

Guidance

• Start with a hash value set to 0
• Go through each letter in the string one by one
• For each letter, add it to the hash value in a specific way
• After considering all the letters, make sure the hash value stays within a certain range
• Return resulting hash value

Tips

• choose a large prime number to minimize the chance of collisions
• ensure the base is sufficiently large to cover the character set of the input string
• consider using a rolling hash variant if dealing with large strings or streaming data, where the hash value can be efficiently updated with each character insertion or deletion

Practice

Practice

polynomial_hash(input_string):
  // Initialize variables
  hash = 0
  P = large_prime_number
  B = base_value

  // Iterate through each character in the input string
  for each character c in input_string:
    // Update hash using polynomial evaluation
    hash = (hash * B + c) % P

  // Return final hash value
  return hash

Solution

package main

type SimplePolynomialHash struct {
	base int
}

func NewSimplePolynomialHash(base int) *SimplePolynomialHash {
	return &SimplePolynomialHash{base}
}

func (s *SimplePolynomialHash) Hash(word string) int {
	hash := 0
	for charIndex := 0; charIndex < len(word); charIndex++ {
		hash += int(word[charIndex]) * pow(s.base, charIndex)
	}
	return hash
}

func (s *SimplePolynomialHash) Roll(prevHash int, prevWord string, newWord string) int {
	hash := prevHash
	prevValue := int(prevWord[0])
	newValue := int(newWord[len(newWord)-1])

	hash -= prevValue
	hash /= s.base
	hash += newValue * pow(s.base, len(newWord)-1)

	return hash
}

type PolynomialHash struct {
	base    int
	modulus int
}

func NewPolynomialHash(base, modulus int) *PolynomialHash {
	return &PolynomialHash{base, modulus}
}

func (p *PolynomialHash) Hash(word string) int {
	charCodes := make([]int, len(word))
	for i, char := range word {
		charCodes[i] = p.charToNumber(char)
	}

	hash := 0
	for _, charCode := range charCodes {
		hash *= p.base
		hash += charCode
		hash %= p.modulus
	}

	return hash
}

func (p *PolynomialHash) Roll(prevHash int, prevWord, newWord string) int {
	hash := prevHash
	prevValue := p.charToNumber(rune(prevWord[0]))
	newValue := p.charToNumber(rune(newWord[len(newWord)-1]))

	prevValueMultiplier := 1
	for i := 1; i < len(prevWord); i++ {
		prevValueMultiplier *= p.base
		prevValueMultiplier %= p.modulus
	}

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

	hash *= p.base
	hash += newValue
	hash %= p.modulus

	return hash
}

func (p *PolynomialHash) charToNumber(char rune) int {
	charCode := int(char)
	if surrogate := len(string(char)) == 2; surrogate {
		surrogateShift := 1 << 16
		charCode += int(char) * surrogateShift
	}
	return charCode
}

func pow(x, n int) int {
	result := 1
	for i := 0; i < n; i++ {
		result *= x
	}
	return result
}

import java.util.Arrays;

class SimplePolynomialHash {

  private final int base;

  SimplePolynomialHash(int base) {
    this.base = base;
  }

  int hash(String word) {
    int hash = 0;
    for (int charIndex = 0; charIndex < word.length(); charIndex++) {
      hash += word.charAt(charIndex) * Math.pow(base, charIndex);
    }
    return hash;
  }

  int roll(int prevHash, String prevWord, String newWord) {
    int hash = prevHash;
    int prevValue = prevWord.charAt(0);
    int newValue = newWord.charAt(newWord.length() - 1);

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

    return hash;
  }
}

class PolynomialHash {

  private final int base;
  private final int modulus;

  PolynomialHash() {
    this.base = 37;
    this.modulus = 101;
  }

  PolynomialHash(int base, int modulus) {
    this.base = base;
    this.modulus = modulus;
  }

  int hash(String word) {
    int[] charCodes = word.chars().map(this::charToNumber).toArray();

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

    return hash;
  }

  int roll(int prevHash, String prevWord, String newWord) {
    int hash = prevHash;
    int prevValue = charToNumber(prevWord.charAt(0));
    int newValue = charToNumber(newWord.charAt(newWord.length() - 1));

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

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

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

    return hash;
  }

  private int charToNumber(int charCode) {
    if (Character.charCount(charCode) == 2) {
      int surrogateShift = 1 << 16;
      charCode += Character.codePointAt(Character.toChars(charCode), 1) * surrogateShift;
    }
    return charCode;
  }
}

class SimplePolynomialHash {
  constructor(base = 17) {
    this.base = base;
  }

  hash(word) {
    let hash = 0;
    for (let charIndex = 0; charIndex < word.length; charIndex += 1) {
      hash += word.charCodeAt(charIndex) * this.base ** charIndex;
    }

    return hash;
  }

  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;
  }
}

class PolynomialHash {
  constructor({ base = 37, modulus = 101 } = {}) {
    this.base = base;
    this.modulus = modulus;
  }

  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;
  }

  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;
  }

  charToNumber(char) {
    let charCode = char.codePointAt(0);

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

    return charCode;
  }
}

import kotlin.math.pow

class SimplePolynomialHash(private val base: Int = 17) {

    fun hash(word: String): Int {
        var hash = 0
        for (charIndex in word.indices) {
            hash += word[charIndex].toInt() * base.toDouble().pow(charIndex).toInt()
        }
        return hash
    }

    fun roll(prevHash: Int, prevWord: String, newWord: String): Int {
        var hash = prevHash
        val prevValue = prevWord[0].toInt()
        val newValue = newWord[newWord.length - 1].toInt()

        hash -= prevValue
        hash /= base
        hash += newValue * base.toDouble().pow(newWord.length - 1).toInt()

        return hash
    }
}

class PolynomialHash(private val base: Int = 37, private val modulus: Int = 101) {

    fun hash(word: String): Int {
        val charCodes = word.map { charToNumber(it) }

        var hash = 0
        for (charCode in charCodes) {
            hash *= base
            hash += charCode
            hash %= modulus
        }

        return hash
    }

    fun roll(prevHash: Int, prevWord: String, newWord: String): Int {
        var hash = prevHash

        val prevValue = charToNumber(prevWord[0])
        val newValue = charToNumber(newWord[newWord.length - 1])

        var prevValueMultiplier = 1
        for (i in 1 until prevWord.length) {
            prevValueMultiplier *= base
            prevValueMultiplier %= modulus
        }

        hash += modulus
        hash -= (prevValue * prevValueMultiplier) % modulus

        hash *= base
        hash += newValue
        hash %= modulus

        return hash
    }

    private fun charToNumber(char: Char): Int {
        var charCode = char.code

        val surrogate = char.code
        if (Character.charCount(surrogate) == 2) {
            val surrogateShift = 2.toDouble().pow(16).toInt()
            charCode += Character.codePointAt(char.toString(), 1) * surrogateShift
        }

        return charCode
    }
}

class SimplePolynomialHash:
    def __init__(self, base=17):
        self.base = base

    def hash(self, word):
        hash_value = 0
        for char_index in range(len(word)):
            hash_value += ord(word[char_index]) * self.base ** char_index
        return hash_value

    def roll(self, prev_hash, prev_word, new_word):
        hash_value = prev_hash
        prev_value = ord(prev_word[0])
        new_value = ord(new_word[-1])

        hash_value -= prev_value
        hash_value //= self.base
        hash_value += new_value * self.base ** (len(new_word) - 1)

        return hash_value


class PolynomialHash:
    def __init__(self, base=37, modulus=101):
        self.base = base
        self.modulus = modulus

    def hash(self, word):
        char_codes = [self.char_to_number(char) for char in word]

        hash_value = 0
        for char_code in char_codes:
            hash_value *= self.base
            hash_value += char_code
            hash_value %= self.modulus

        return hash_value

    def roll(self, prev_hash, prev_word, new_word):
        hash_value = prev_hash

        prev_value = self.char_to_number(prev_word[0])
        new_value = self.char_to_number(new_word[-1])

        prev_value_multiplier = 1
        for i in range(1, len(prev_word)):
            prev_value_multiplier *= self.base
            prev_value_multiplier %= self.modulus

        hash_value += self.modulus
        hash_value -= (prev_value * prev_value_multiplier) % self.modulus

        hash_value *= self.base
        hash_value += new_value
        hash_value %= self.modulus

        return hash_value

    def char_to_number(self, char):
        char_code = ord(char)

        surrogate = ord(char[1]) if len(char) == 2 else None
        if surrogate is not None:
            surrogate_shift = 2 ** 16
            char_code += surrogate * surrogate_shift

        return char_code

struct SimplePolynomialHash {
    base: i32,
}

impl SimplePolynomialHash {
    fn new(base: i32) -> SimplePolynomialHash {
        SimplePolynomialHash { base }
    }

    fn hash(&self, word: &str) -> i32 {
        let mut hash = 0;
        for (char_index, character) in word.chars().enumerate() {
            hash += (character as i32) * self.base.pow(char_index as u32);
        }
        hash
    }

    fn roll(&self, prev_hash: i32, prev_word: &str, new_word: &str) -> i32 {
        let mut hash = prev_hash;
        let prev_value = prev_word.chars().nth(0).unwrap() as i32;
        let new_value = new_word.chars().nth(new_word.len() - 1).unwrap() as i32;

        hash -= prev_value;
        hash /= self.base;
        hash += new_value * self.base.pow((new_word.len() - 1) as u32);

        hash
    }
}

struct PolynomialHash {
    base: i32,
    modulus: i32,
}

impl PolynomialHash {
    fn new(base: i32, modulus: i32) -> PolynomialHash {
        PolynomialHash { base, modulus }
    }

    fn hash(&self, word: &str) -> i32 {
        let char_codes: Vec<i32> = word.chars().map(|char| self.char_to_number(char)).collect();
        let mut hash = 0;
        for char_index in 0..char_codes.len() {
            hash *= self.base;
            hash += char_codes[char_index];
            hash %= self.modulus;
        }
        hash
    }

    fn roll(&self, prev_hash: i32, prev_word: &str, new_word: &str) -> i32 {
        let mut hash = prev_hash;
        let prev_value = self.char_to_number(prev_word.chars().nth(0).unwrap());
        let new_value = self.char_to_number(new_word.chars().nth(new_word.len() - 1).unwrap());

        let mut prev_value_multiplier = 1;
        for i in 1..prev_word.len() {
            prev_value_multiplier *= self.base;
            prev_value_multiplier %= self.modulus;
        }

        hash += self.modulus;
        hash -= (prev_value * prev_value_multiplier) % self.modulus;

        hash *= self.base;
        hash += new_value;
        hash %= self.modulus;

        hash
    }

    fn char_to_number(&self, character: char) -> i32 {
        let mut char_code = character as i32;
        if let Some(surrogate) = character.encode_utf16().nth(1) {
            let surrogate_shift = 2_i32.pow(16);
            char_code += surrogate as i32 * surrogate_shift;
        }
        char_code
    }
}

class SimplePolynomialHash {
  private base: number;

  constructor(base: number = 17) {
    this.base = base;
  }

  hash(word: string): number {
    let hash = 0;
    for (let charIndex = 0; charIndex < word.length; charIndex += 1) {
      hash += word.charCodeAt(charIndex) * Math.pow(this.base, charIndex);
    }
    return hash;
  }

  roll(prevHash: number, prevWord: string, newWord: string): number {
    let hash = prevHash;

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

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

    return hash;
  }
}

class PolynomialHash {
  private base: number;
  private modulus: number;

  constructor({ base = 37, modulus = 101 } = {}) {
    this.base = base;
    this.modulus = modulus;
  }

  hash(word: string): number {
    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;
  }

  roll(prevHash: number, prevWord: string, newWord: string): number {
    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;
  }

  private charToNumber(char: string): number {
    let charCode = char.codePointAt(0)!;

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

    return charCode;
  }
}