Rolling Hash

A high performance nim implementation of a Cyclic Polynomial Hash, aka BuzHash, and the Rabin-Karp algorithm. A Cyclic Polynomial hash is a type of Rolling hash which avoids multiplication by using circular shifts and xoring. This implementation has type support for (uint8, uint16, uint32, and uint64). For more information regarding Cyclic Polynomial hashing please refer to wiki's article on Rolling Hash. Also In this implementation is Rabin Karp hasing algorithm, which can be used for variable content based chunking.

Example Usage

import cyclichash, sequtils                                                   

var hf = newCyclicHash[uint64, char](5, 19) # Create a Cyclic with a 5 n-gram sliding window and 19 bit sized hash values
let input = "ABCDE"
  
hf.eat(input[0]) # A
hf.eat(input[1]) # B
hf.eat(input[2]) # C
hf.eat(input[3]) # D
echo "Hash value of ABCD is ", hf.hashValue
  
let charSeqFull = toSeq(input.items) # create a seq[char] out of input string "ABCDE"
let charSeqPart = charSeqFull[0 ..< 4] # slice input string to obtain "ABCD"
  
var trueAnswer = hf.hash(charSeqPart) # Check if hash value of "ABCD" is correct
assert trueAnswer == hf.hashValue
  
hf.eat(input[4]) # E
echo "Hash value of ABCDE is ", hf.hashValue
  
trueAnswer = hf.hash(charSeqFull) # Check if hash value of "ABCDE" is correct
assert trueAnswer == hf.hashValue

Installation

Install Nim for Windows or Unix by following the instructions in , or preferably by installing choosenim

Once choosenim is installed you can nimble install rollinghash to pull the latest bipbuffer release and all its dependencies

Documentation

Refer to the following documentation for a list of procedures and templates: Cyclic Hash , Character Hash and Rabin-Karp Hashing

Credits

Special thanks for Dr. Daniel Lemire for his help and for replying to my inquires concerning his implementation of cyclic hash in c++ found here along with other handy rolling hash functions!