rollinghash: github.com/chmduquesne/rollinghash Index | Examples | Files | Directories

package rollinghash

import "github.com/chmduquesne/rollinghash"

Package rollinghash implements rolling versions of some hashes

Code:

s := []byte("The quick brown fox jumps over the lazy dog")

// This example works with adler32, but the api is identical for all
// other rolling checksums. Consult the documentation of the checksum
// of interest.
classic := hash.Hash32(_adler32.New())
rolling := _adler32.New()

// Window len
n := 16

// You MUST load an initial window into the rolling hash before being
// able to roll bytes
rolling.Write(s[:n])

// Roll it and compare the result with full re-calculus every time
for i := n; i < len(s); i++ {

    // Reset and write the window in classic
    classic.Reset()
    classic.Write(s[i-n+1 : i+1])

    // Roll the incoming byte in rolling
    rolling.Roll(s[i])

    // Compare the hashes
    if classic.Sum32() != rolling.Sum32() {
        log.Fatalf("%v: expected %x, got %x",
            s[i-n+1:i+1], classic.Sum32(), rolling.Sum32())
    }
}

Index

Examples

Package Files

rollinghash.go

Constants

const DefaultWindowCap = 64

DefaultWindowCap is the default capacity of the internal window of a new Hash.

type Hash Uses

type Hash interface {
    hash.Hash
    Roller
}

rollinghash.Hash extends hash.Hash by adding the method Roll. A rollinghash.Hash can be updated byte by byte, by specifying which byte enters the window.

type Hash32 Uses

type Hash32 interface {
    hash.Hash32
    Roller
}

rollinghash.Hash32 extends hash.Hash by adding the method Roll. A rollinghash.Hash32 can be updated byte by byte, by specifying which byte enters the window.

type Hash64 Uses

type Hash64 interface {
    hash.Hash64
    Roller
}

rollinghash.Hash64 extends hash.Hash by adding the method Roll. A rollinghash.Hash64 can be updated byte by byte, by specifying which byte enters the window.

type Roller Uses

type Roller interface {
    Roll(b byte)
}

A Roller is a type that has the method Roll. Roll updates the hash of a rolling window from just the entering byte. You MUST call Write() BEFORE using this method and provide it with an initial window of size at least 1 byte. You can then call this method for every new byte entering the window. The byte leaving the window is automatically computed from a copy of the window internally kept in the checksum. This window is updated along with the internal state of the checksum every time Roll() is called.

Directories

PathSynopsis
adler32
bozo32
buzhash32
buzhash64
rabinkarp64
roll

Package rollinghash imports 1 packages (graph) and is imported by 20 packages. Updated 2018-09-16. Refresh now. Tools for package owners.