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!