Fnv1Generic

Fowler / Noll / Vo (FNV) 1/1a Hash Module

Very fast hashing algorithm implementation with support for 32/64 bit hashes. This modules implements two versions of FNV1: FNV1 and FNV1a. The difference is extremely slight and Noll himself says:

"Some people use FNV1a instead of FNV1 because they see slightly better dispersion for tiny (<4 octets) chunks of memory. Either FNV-1 or FNV-1a make a fine hash."

(cited from http://www.isthe.com/chongo/tech/comp/fnv/)

More...

Members

Aliases

HexDigest
alias HexDigest = char[HEXDGT_LENGTH]
Undocumented in source.
This
alias This = typeof(this)

This alias for chainable methods

opCall
alias opCall = fnv1
Undocumented in source.

Functions

binaryDigest
ubyte[] binaryDigest(ubyte[] buffer)

Computes the digest and resets the state

digestSize
uint digestSize()

Returns the size in bytes of the digest

getDigest
DigestType getDigest()

Simply returns the digest

reset
This reset()

Resets the state

ulongDigest
ulong ulongDigest()

Simply returns the digest as an ulong independently of the digest size and reset the internal state.

update
This update(const(void)[] data)

Processes data

Mixins

__anonymous
mixin Fnv1Const!(T)

DigestType type alias

Static functions

combined
hash_t combined(Vals vals)

Creates a combined hash of all the provided parameters. The previous hashed value is used as the initial state for the next.

fnv1
DigestType fnv1(U data, DigestType digest)

Calculates a FNV1/FNV1a digest from data. data are processed in octet/byte-wise manner.

fnv1_core
DigestType fnv1_core(ubyte d, DigestType digest)

FNV1/FNV1a core; calculates a digest of one octet d

fnv1_hex
char[] fnv1_hex(U data, char[] hexdgst, DigestType digest)

Calculates a FNV1/FNV1a digest from data and generates a hexdecimal string representation of the digest. data are processed in octet/byte-wise manner.

Static variables

DIGEST_LENGTH
auto DIGEST_LENGTH;

Binary digest length and hexadecimal digest string length constants

HEXDGT_LENGTH
auto HEXDGT_LENGTH;
Undocumented in source.

Unions

BinConvert
union BinConvert

Endianness aware integer to byte array converter

Inherited Members

From FnvDigest

ulongDigest
ulong ulongDigest()

Simply returns the digest as an ulong independently of the digest size and reset the internal state.

Detailed Description

The FNV1A template parameter selects FNV1a if set to true on instantiation or FNV1 otherwise. It is recommended to use the Fnv1XX/Fnv1aXX aliases.

Fnv1 and Fnv1a (without 32/64 suffix) use the native machine data word width.

32bit ~ 3704333.44 hash/sec 64bit ~ 1728119.76 hash/sec

--

Usage

It is recommended to use these Fnv1 class convenience aliases:

- Fnv1 for FNV1 digests of the machine's native width - Fnv1a for FNV1a digests of the machine's native width

- Fnv132 for 32-bit FNV1 digests - Fnv1a32 for 32-bit FNV1a digests

- Fnv164 for 64-bit FNV1 digests - Fnv1a64 for 64-bit FNV1a digests

Example 1: Generating FNV1 digests using class instances

import ocean.io.digest.Fnv1;

auto fnv1   = new Fnv1;
auto fnv132 = new Fnv132;
auto fnv164 = new Fnv164;

auto hello = "Hello World!";

fnv1.update(hello);
fnv132.update(hello);
fnv164.update(hello);

auto hash   = fnv1.hexDigest();
auto hash32 = fnv132.hexDigest();
auto hash64 = fnv164.hexDigest();

Example 2: Generating FNV1a digests using the static fnv1() method

import ocean.io.digest.Fnv;

auto hello = "Hello World!";

size_t hash   = Fnv1a(hello);       // size_t uses the native machine data word width
uint   hash32 = Fnv1a32(hello);
ulong  hash64 = Fnv1a64(hello);

--

We should use this hash algorithm in combination with this consistent hash algorithm in order to build a distributed hash table (DTH)

http://www.audioscrobbler.net/development/ketama/

svn://svn.audioscrobbler.net/misc/ketama/ http://pdos.csail.mit.edu/chord/

--

References

http://www.isthe.com/chongo/tech/comp/fnv/

http://www.azillionmonkeys.com/qed/hash.html

http://www.azillionmonkeys.com/qed/hash.c

http://www.digitalmars.com/d/2.0/htomodule.html

http://www.team5150.com/~andrew/blog/2007/03/breaking_superfasthash.html

http://www.team5150.com/~andrew/blog/2007/03/when_bad_hashing_means_good_caching.html

http://www.azillionmonkeys.com/qed/hash.html

Meta