jenkinshash.C File Reference

#include "Util/jenkinshash.H"
#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
#include "rutz/trace.h"

Include dependency graph for jenkinshash.C:

Go to the source code of this file.

Defines
#define	hashsize(n)   ((ub4)1<<(n))
#define	hashmask(n)   (hashsize(n)-1)
#define	mix(a, b, c)
#define	mix2(a, b, c)
#define	HASHSTATE   1
#define	HASHLEN   1
#define	MAXPAIR   80
#define	MAXLEN   70
Functions
uint32	jenkinshash (const byte *key, uint32 length, uint32 initval)
	hash a variable-length key into a 32-bit value
uint32	jenkinshash2 (const uint32 *key, uint32 length, uint32 initval)
	Hash a variable-length key into a 32-bit value.

---

Detailed Description

32-bit hash functions (NOT CRYPTOGRAPHIC!)

Definition in file jenkinshash.C.

---

Define Documentation

#define mix	(	a,
		b,
		c		)

Value:

{ \
  a -= b; a -= c; a ^= (c>>13); \
  b -= c; b -= a; b ^= (a<<8); \
  c -= a; c -= b; c ^= (b>>13); \
  a -= b; a -= c; a ^= (c>>12);  \
  b -= c; b -= a; b ^= (a<<16); \
  c -= a; c -= b; c ^= (b>>5); \
  a -= b; a -= c; a ^= (c>>3);  \
  b -= c; b -= a; b ^= (a<<10); \
  c -= a; c -= b; c ^= (b>>15); \
}

Definition at line 68 of file jenkinshash.C.

#define mix2	(	a,
		b,
		c		)

Value:

{ \
  a -= b; a -= c; a ^= (c>>13); \
  b -= c; b -= a; b ^= (a<< 8); \
  c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
  a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
  b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
  c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
  a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
  b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
  c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
}

Definition at line 82 of file jenkinshash.C.

---

Function Documentation

uint32 jenkinshash	(	const byte *	key,
		uint32	length,
		uint32	initval = 0
	)

hash a variable-length key into a 32-bit value

k : the key (the unaligned variable-length array of bytes) len : the length of the key, counting by bytes level : can be any 4-byte value Returns a 32-bit value. Every bit of the key affects every bit of the return value. Every 1-bit and 2-bit delta achieves avalanche. About 36+6len instructions.

The best hash table sizes are powers of 2. There is no need to do mod a prime (mod is sooo slow!). If you need less than 32 bits, use a bitmask. For example, if you need only 10 bits, do h = (h & hashmask(10)); In which case, the hash table should have hashsize(10) elements.

If you are hashing n strings (ub1 **)k, do it like this: for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h);

By Bob Jenkins, 1996. bob_jenkins@burtleburtle.net. You may use this code any way you wish, private, educational, or commercial. It's free.

See http://burlteburtle.net/bob/hash/evahash.html Use for hash table lookup, or anything where one collision in 2^32 is acceptable. Do NOT use for cryptographic purposes.

Definition at line 441 of file jenkinshash.C.

uint32 jenkinshash2	(	const uint32 *	key,
		uint32	length,
		uint32	initval = 0
	)

Hash a variable-length key into a 32-bit value.

This works on all machines. jenkinshash2() is identical to jenkinshash() on little-endian machines, except that the length has to be measured in ub4s instead of bytes. It is much faster than hash(). It requires -- that the key be an array of ub4's, and -- that all your machines have the same endianness, and -- that the length be the number of ub4's in the key

Definition at line 447 of file jenkinshash.C.