Algorithm.OptimalBlocks.BuzzHash

This is a rolling hash used to calculate the hashes of fixed-length sequences of characters within a given ByteString. BuzzHash is nice in that it makes this calculation very efficient.

Documentation

hashes

Arguments

:: Int

How many bytes to put into each hash

-> ByteString

The ByteString to calculate hashes of.

-> Vector Word64

Determine the hash of every len sequence of bytes in the given ByteString. Because this uses BuzzHash, a rolling hash, this runs in O(n) time dependent on the length of bs, and independent of len.

This will generate (length bs - len + 1) 64-bit hashes.

data Hash

A representation of a hash that allows rolling hashes to be easily calculated.

Constructors

Hash

Fields

windowLength :: !Int

currentVal :: !Word64

Instances

Show Hash

init :: ByteString -> Hash

Create a Hash instance using an entire ByteString. This doesn't have any sort of length argument to do partial ByteStrings because ByteString supports efficient slices on its own.

roll :: Hash -> Word8 -> Word8 -> Hash

Roll the Hash to the next byte over in the ByteString being hashed. This doesn't do any sort of checking to ensure that old and new are actually correct, so this is probably easy to mess up when using it manually. The expected usage is that one would initialize a hash using init on the beginning of some ByteString, and then to calculate the hash of each sequence of bytes one would manually track the first and last byte of each window on the ByteString. hashes does this for you...

h :: Word8 -> Word64

Upgrade an 8-bit word to a 64-bit one that is very different from all the other possible 8-bit words. This library uses SipHash to do this.