tdc::KarpRabinHash Class Reference

This is a randomized version of the Karp-Rabin hash function. More...

#include <rabinkarphash.h>

Inheritance diagram for tdc::KarpRabinHash:

Public Types
typedef uint64_t	hashvaluetype
typedef unsigned char	chartype
typedef hashvaluetype	key_type

Public Member Functions
void	operator+= (char c)
hashvaluetype	operator() () const
void	clear ()
	KarpRabinHash (Env &&env)
template<class container >
hashvaluetype	hash (container &c)
void	eat (chartype inchar)
void	update (chartype outchar, chartype inchar)
Public Member Functions inherited from tdc::Algorithm
virtual	~Algorithm ()=default
	Algorithm (Algorithm const &)=default
	Algorithm (Algorithm &&)=default
Algorithm &	operator= (Algorithm const &)=default
Algorithm &	operator= (Algorithm &&)=default
	Algorithm (Env &&env)
	Instantiates an algorithm in the specified environment. More...
Env &	env ()
	Provides access to the environment that the algorithm works in. More...
const Env &	env () const

Static Public Member Functions
static Meta	meta ()

Public Attributes
hashvaluetype	hashvalue
int	n
const int	wordsize
CharacterHash< hashvaluetype, chartype >	hasher
const hashvaluetype	HASHMASK
hashvaluetype	BtoN

Static Public Attributes
static const hashvaluetype	B =37

Detailed Description

This is a randomized version of the Karp-Rabin hash function.

Each instance is a rolling hash function meant to hash streams of characters. Each new instance of this class comes with new random keys.

Recommended usage to get L-bit hash values over n-grams: KarpRabinHash<> hf(n,L ); for(uint32 k = 0; k<n;++k) { unsigned char c = ... ; // grab some character hf.eat(c); // feed it to the hasher } while(...) { // go over your string hf.hashvalue; // at all times, this contains the hash value unsigned char c = ... ;// points to the next character unsigned char out = ...; // character we want to forget hf.update(out,c); // update hash value }

Definition at line 28 of file rabinkarphash.h.

Member Typedef Documentation

chartype

typedef unsigned char tdc::KarpRabinHash::chartype

Definition at line 31 of file rabinkarphash.h.

hashvaluetype

typedef uint64_t tdc::KarpRabinHash::hashvaluetype

Definition at line 30 of file rabinkarphash.h.

key_type

typedef hashvaluetype tdc::KarpRabinHash::key_type

Definition at line 32 of file rabinkarphash.h.

Constructor & Destructor Documentation

KarpRabinHash()

tdc::KarpRabinHash::KarpRabinHash ( Env &&  env )

inline

Definition at line 43 of file rabinkarphash.h.

Member Function Documentation

clear()

void tdc::KarpRabinHash::clear ( )

inline

Definition at line 39 of file rabinkarphash.h.

eat()

void tdc::KarpRabinHash::eat ( chartype  inchar )

inline

Definition at line 70 of file rabinkarphash.h.

hash()

template<class container >

hashvaluetype tdc::KarpRabinHash::hash ( container &  c )

inline

Definition at line 55 of file rabinkarphash.h.

meta()

static Meta tdc::KarpRabinHash::meta ( )

inlinestatic

Definition at line 33 of file rabinkarphash.h.

operator()()

hashvaluetype tdc::KarpRabinHash::operator() ( ) const

inline

Definition at line 38 of file rabinkarphash.h.

operator+=()

void tdc::KarpRabinHash::operator+= ( char  c )

inline

Definition at line 37 of file rabinkarphash.h.

update()

void tdc::KarpRabinHash::update ( chartype  outchar, chartype  inchar  )

inline

Definition at line 76 of file rabinkarphash.h.

Member Data Documentation

B

const hashvaluetype tdc::KarpRabinHash::B =37

static

Definition at line 87 of file rabinkarphash.h.

BtoN

hashvaluetype tdc::KarpRabinHash::BtoN

Definition at line 86 of file rabinkarphash.h.

hasher

CharacterHash<hashvaluetype,chartype> tdc::KarpRabinHash::hasher

Definition at line 84 of file rabinkarphash.h.

HASHMASK

const hashvaluetype tdc::KarpRabinHash::HASHMASK

Definition at line 85 of file rabinkarphash.h.

hashvalue

hashvaluetype tdc::KarpRabinHash::hashvalue

Definition at line 81 of file rabinkarphash.h.

n

int tdc::KarpRabinHash::n

Definition at line 82 of file rabinkarphash.h.

wordsize

const int tdc::KarpRabinHash::wordsize

Definition at line 83 of file rabinkarphash.h.

---

The documentation for this class was generated from the following file:

• rabinkarphash.h