hash

Documentation

Overview

Package hash provides rolling hashes.

Rolling hashes have to be used for maintaining the positions of n-byte sequences in the dictionary buffer.

The package provides currently the Rabin-Karp rolling hash and a Cyclic Polynomial hash. Both support the Hashes method to be used with an interface.

Index

• Constants
• func Hashes(r Roller, p []byte) []uint64
• type CyclicPoly
  • func NewCyclicPoly(n int) *CyclicPoly
  • func (r *CyclicPoly) Len() int
  • func (r *CyclicPoly) RollByte(x byte) uint64
• type RabinKarp
  • func NewRabinKarp(n int) *RabinKarp
  • func NewRabinKarpConst(n int, a uint64) *RabinKarp
  • func (r *RabinKarp) Len() int
  • func (r *RabinKarp) RollByte(x byte) uint64
• type Roller

Constants

const A = 0x97b548add41d5da1

A is the default constant for Robin-Karp rolling hash. This is a random prime.

Functions

func Hashes

func Hashes(r Roller, p []byte) []uint64

Hashes computes all hash values for the array p. Note that the state of the roller is changed.

Types

type CyclicPoly

type CyclicPoly struct {
	// contains filtered or unexported fields
}

CyclicPoly provides a cyclic polynomial rolling hash.

func NewCyclicPoly

func NewCyclicPoly(n int) *CyclicPoly

NewCyclicPoly creates a new instance of the CyclicPoly structure. The argument n gives the number of bytes for which a hash will be executed. This number must be positive; the method panics if this isn't the case.

func (*CyclicPoly) Len

func (r *CyclicPoly) Len() int

Len returns the length of the byte sequence for which a hash is generated.

func (*CyclicPoly) RollByte

func (r *CyclicPoly) RollByte(x byte) uint64

RollByte hashes the next byte and returns a hash value. The complete becomes available after at least Len() bytes have been hashed.

type RabinKarp

type RabinKarp struct {
	A uint64
	// contains filtered or unexported fields
}

RabinKarp supports the computation of a rolling hash.

func NewRabinKarp

func NewRabinKarp(n int) *RabinKarp

NewRabinKarp creates a new RabinKarp value. The argument n defines the length of the byte sequence to be hashed. The default constant will will be used.

func NewRabinKarpConst

func NewRabinKarpConst(n int, a uint64) *RabinKarp

NewRabinKarpConst creates a new RabinKarp value. The argument n defines the length of the byte sequence to be hashed. The argument a provides the constant used to compute the hash.

func (*RabinKarp) Len

func (r *RabinKarp) Len() int

Len returns the length of the byte sequence.

func (*RabinKarp) RollByte

func (r *RabinKarp) RollByte(x byte) uint64

RollByte computes the hash after x has been added.

type Roller

type Roller interface {
	Len() int
	RollByte(x byte) uint64
}

Roller provides an interface for rolling hashes. The hash value will become valid after hash has been called Len times.