Monday, 11 September 2017

Algorithms | Rolling hash

A rolling hash (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 old hash value, the old value removed from the window, and the new value added to the window—similar to the way a moving average function can be computed much more quickly than other low-pass filters.

Rabin–Karp rolling hash
The Rabin–Karp string search algorithm is normally used with a very simple rolling hash function that only uses multiplications and additions:
Code to generate Rolling Hash

package com.string.algos;

/**
 * @author rajesh.dixit
 */
public class RollingHash {

     private static int PRIME_NUM = 3;
    
     /**
      * This method is used to calculate the hash of all window in O(n) time complexity.
      * @param str
      */
     private static void printRollingHash(String str) {
           int hash  = 0;
           int window = 3;
          
           char[] array = str.toCharArray();
          
           for (int i = 0; i < window; i++) {
                hash = hash + (int) ((array[i]-'a'+1)*Math.pow(PRIME_NUM, i));
           }
           System.out.println(hash);
          
           for (int i = 0; i < array.length-window; i++) {
                /** Rolling out first element of window. */
                hash = hash -(array[i]-'a'+1);
               
                /** Divide by prime number. */
                hash = hash/PRIME_NUM;
               
                /** Add new element to window. */
                hash = (int) (hash +(array[i+window]-'a'+1)*Math.pow(PRIME_NUM, window-1));
               
                System.out.println(hash);
           }
     }
    
     /**
      * Driver method.
      * @param args
      */
     public static void main(String[] args) {
           String str = "abeda";
          
           printRollingHash(str);
     }
}

Output:
52
53
26

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...