Hashing Functions
Introduction
Nowadays data processing is getting more intensive. Processing data takes considerable time. To reduce this problem hashing functions are developed.
Basics
Hash tables are just like most tables (the old-fashioned word for "arrays"). A table becomes a hash table when non-sequential access to a given element is achieved through the use of a hash function. A hash function is generally handed a data element, which it converts to an integer that is used as an index into the table. For example, if you had a hash table into which you wanted to store dates, you might take the Julian date (a positive integer assigned to every date since January 1, 4713 bc) and divide it by the size of the hash table. The remainder, termed the "hash key," would be your index into the hash table.
Some Hash Functions
a. Additive Hash
This function’s complexity is 5n+3. There isn’t a mixing step. Joining step handles one byte in each execution. Table length must be prime and not more than one byte. Here is the C source code.
int additive(char key[], int len, int prime)
{
int hash, i;
for (hash=len, i=0; i<len; ++i)
hash += key[i];
return (hash % prime);
}
b. Rotating Hash
This function’s complexity is 8n+3. Different from Additive Hash there is a mixing step and its joining step consists of XOR operation. Table length is still prime but there is not one byte limit. Complexity of this function is 6n+2 with Intel processors.
int rotating(char key[], int len, int prime)
{
int hash, i;
for (hash=len, i=0; i<len; ++i)
hash = (hash<<4)^(hash>>28)^key[i];
return (hash % prime);
}
c. One-At-A-Time Hash
This function looks like Rotating Hash but has a mixing step in deep. Complexity is 9n+9. It returns full 4-byte value.
int one_at_a_time(char key[], int len)
{
int hash, i;
for (hash=0, i=0; i<len; ++i)
{
hash += key[i];
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
return (hash & mask);
}
d. Pearson’s Hash
tab[] creates a return value using random numbers from 0 to 255. Result is one byte. Complexity is 6n+2. Bigger results are obtained by using different starting values again and again.
char pearson(char key[], int len, char tab[256])
{
char hash;
int i;
for (hash=len, i=0; i<len; ++i)
hash=tab[hash^key[i]];
return (hash);
}
e. BJ Hash
Complexity of this function is 6n+35.
Mixing step uses 4-byte registers. Joining is done by 12-byte blocks. So there is
less loops than above functions. Collusion probability is 1 over
.
typedef unsigned long int ub4; /* unsigned 4-byte quantities */
typedef unsigned char ub1; /* unsigned 1-byte quantities */
#define hashsize(n) ((ub4)1<<(n))
#define hashmask(n) (hashsize(n)-1)
/*
--------------------------------------------------------------------
mix -- mix 3 32-bit values reversibly.
For every delta with one or two bits set, and the deltas of all three
high bits or all three low bits, whether the original value of a,b,c
is almost all zero or is uniformly distributed,
* If mix() is run forward or backward, at least 32 bits in a,b,c
have at least 1/4 probability of changing.
* If mix() is run forward, every bit of c will change between 1/3 and
2/3 of the time. (Well, 22/100 and 78/100 for some 2-bit deltas.)
mix() takes 36 machine instructions, but only 18 cycles on a superscalar
machine (like a Pentium or a Sparc). No faster mixer seems to work,
that's the result of my brute-force search. There were about 2^^68
hashes to choose from. I only tested about a billion of those.
--------------------------------------------------------------------
*/
#define mix(a,b,c) \
{ \
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); \
}
/*
--------------------------------------------------------------------
hash() -- 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
initval : 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 6*len+35 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://burtleburtle.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.
--------------------------------------------------------------------
*/
ub4 hash(register ub1 k[], register ub4 length, register ub4 initval)
{
register ub4 a,b,c,len;
/* Set up the internal state */
len = length;
a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */
c = initval; /* the previous hash value */
/*---------------------------------------- handle most of the key */
while (len >= 12)
{
a += (k[0] +((ub4)k[1]<<8) +((ub4)k[2]<<16) +((ub4)k[3]<<24));
b += (k[4] +((ub4)k[5]<<8) +((ub4)k[6]<<16) +((ub4)k[7]<<24));
c += (k[8] +((ub4)k[9]<<8) +((ub4)k[10]<<16)+((ub4)k[11]<<24));
mix(a,b,c);
k += 12; len -= 12;
}
/*------------------------------------- handle the last 11 bytes */
c += length;
switch(len) /* all the case statements fall through */
{
case 11: c+=((ub4)k[10]<<24);
case 10: c+=((ub4)k[9]<<16);
case 9 : c+=((ub4)k[8]<<8);
/* the first byte of c is reserved for the length */
case 8 : b+=((ub4)k[7]<<24);
case 7 : b+=((ub4)k[6]<<16);
case 6 : b+=((ub4)k[5]<<8);
case 5 : b+=k[4];
case 4 : a+=((ub4)k[3]<<24);
case 3 : a+=((ub4)k[2]<<16);
case 2 : a+=((ub4)k[1]<<8);
case 1 : a+=k[0];
/* case 0: nothing left to add */
}
mix(a,b,c);
/*-------------------------------------------- report the result */
return c;
}