    # General purpose hash function algorithms library

Variants RS–AP are taken from Arash Partow collection: http://www.partow.net/programming/hashfunctions.

## RS Hash Function

```unsigned int RSHash (char *str, unsigned int len)
{
unsigned int b = 378551;
unsigned int a = 63689;
unsigned int hash = 0;
unsigned int i = 0;

for (i = 0; i < len; str++, i++) {
hash = hash * a + (unsigned char)(*str);
a = a * b;
}
return hash;
}```

## JS Hash Function

```unsigned int JSHash (char *str, unsigned int len)
{
unsigned int hash = 1315423911;
unsigned int i = 0;

for (i = 0; i < len; str++, i++) {
hash ^= ((hash << 5) + (unsigned char)(*str) + (hash >> 2));
}
return hash;
}```

## P. J. Weinberger Hash Function

```unsigned int PJWHash (char *str, unsigned int len)
{
unsigned int BitsInUnsignedInt = (unsigned int) (sizeof (unsigned int) * 8);
unsigned int ThreeQuarters = (unsigned int) ((BitsInUnsignedInt * 3) / 4);
unsigned int OneEighth = (unsigned int) (BitsInUnsignedInt / 8);
unsigned int HighBits = (unsigned int) (0xFFFFFFFF) <<
(BitsInUnsignedInt - OneEighth);
unsigned int hash = 0;
unsigned int test = 0;
unsigned int i = 0;

for (i = 0; i < len; str++, i++) {
hash = (hash << OneEighth) + (unsigned char)(*str);

if ((test = hash & HighBits) != 0) {
hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
}
}
return hash;
}```

## ELF Hash Function

```unsigned int ELFHash (char *str, unsigned int len)
{
unsigned int hash = 0;
unsigned int x = 0;
unsigned int i = 0;

for (i = 0; i < len; str++, i++) {
hash = (hash << 4) + (unsigned char)(*str);
if ((x = hash & 0xF0000000L) != 0) {
hash ^= (x >> 24);
hash &= ~x;
}
}
return hash;
}```

## BKDR Hash Function

```unsigned int BKDRHash (char *str, unsigned int len)
{
unsigned int seed = 131313; /* 31 131 1313 13131 131313 etc.. */
unsigned int hash = 0;
unsigned int i = 0;

for (i = 0; i < len; str++, i++) {
hash = (hash * seed) + (unsigned char)(*str);
}
return hash;
}```

## SDBM Hash Function

```unsigned int SDBMHash (char *str, unsigned int len)
{
unsigned int hash = 0;
unsigned int i = 0;

for (i = 0; i < len; str++, i++) {
hash = (unsigned char)(*str) + (hash << 6) +
(hash << 16) - hash;
}
return hash;
}```

## DJB Hash Function

```unsigned int DJBHash (char *str, unsigned int len)
{
unsigned int hash = 5381;
unsigned int i = 0;

for (i = 0; i < len; str++, i++) {
hash = ((hash << 5) + hash) + (unsigned char)(*str);
}
return hash;
}```

## DEK Hash Function

```unsigned int DEKHash (char *str, unsigned int len)
{
unsigned int hash = len;
unsigned int i = 0;

for (i = 0; i < len; str++, i++) {
hash = ((hash << 5) ^ (hash >> 27)) ^ (unsigned char)(*str);
}
return hash;
}```

## AP Hash Function

```unsigned int APHash (char *str, unsigned int len)
{
unsigned int hash = 0;
unsigned int i = 0;

for (i = 0; i < len; str++, i++) {
hash ^= ((i & 1) == 0) ?
((hash << 7) ^ (unsigned char)(*str) ^ (hash >> 3)) :
(~((hash << 11) ^ (unsigned char)(*str) ^ (hash >> 5)));
}
return hash;
}```

## LY Hash Function

Congruential generator proposed by Leonid Yuriev. Multiplier constant suggested by M.Lavaux & F.Janssens.

```unsigned int LYHash (char *str, unsigned int len)
{
unsigned int hash = 0;
unsigned int i = 0;

for (i = 0; i < len; str++, i++) {
hash = (hash * 1664525) + (unsigned char)(*str) + 1013904223;
}
return hash;
}```

## ROT13 Hash Function

No multiplication, by Serge Vakulenko. Two shifts are converted by GCC 4 to a single rotation instruction.

```unsigned int ROT13Hash (char *str, unsigned int len)
{
unsigned int hash = 0;
unsigned int i = 0;

for (i = 0; i < len; str++, i++) {
hash += (unsigned char)(*str);
hash -= (hash << 13) | (hash >> 19);
}
return hash;
}```

## FAQ6 Hash Function

From Bob Jenkins Hash Function FAQ: http://burtleburtle.net/bob/hash/hashfaq.html

```unsigned int bob_faq6_hash (char *str, unsigned int len)
{
unsigned int hash = 0;
unsigned int i = 0;

for (i = 0; i < len; str++, i++) {
hash += (unsigned char)(*str);
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
return hash;
}```

## LOOKUP3 Hash Function

Slightly modified for byte data.

```#define rot(x,k) (((x)<<(k)) ^ ((x)>>(32-(k))))

#define mix(a,b,c) { \
a -= c;  a ^= rot (c,  4);  c += b; \
b -= a;  b ^= rot (a,  6);  a += c; \
c -= b;  c ^= rot (b,  8);  b += a; \
a -= c;  a ^= rot (c, 16);  c += b; \
b -= a;  b ^= rot (a, 19);  a += c; \
c -= b;  c ^= rot (b,  4);  b += a; }

#define final(a,b,c) { \
c ^= b; c -= rot (b, 14); \
a ^= c; a -= rot (c, 11); \
b ^= a; b -= rot (a, 25); \
c ^= b; c -= rot (b, 16); \
a ^= c; a -= rot (c, 4);  \
b ^= a; b -= rot (a, 14); \
c ^= b; c -= rot (b, 24); }

unsigned int bob_lookup3_hash (char *str, unsigned int len8)
{
unsigned int a, b, c;

/* the key, an array of unsigned int values */
unsigned int *k = (unsigned int*) str;

/* the length of the key, in unsigned ints */
unsigned int length = (len8 + 3) / 4;

/* tail pad with zeros */
str [len8] = 0;
str [len8 + 1] = 0;
str [len8 + 2] = 0;

/* Set up the internal state */
a = b = c = 0xdeadbeef + len8;

/* handle most of the key */
while (length > 3) {
a += k;
b += k;
c += k;
mix (a, b, c);
length -= 3;
k += 3;
}

/* handle the last 3 unsigned ints */
switch(length) {
case 3:
c += k;
case 2:
b += k;
case 1:
a += k;
final (a, b, c);
case 0:
/* nothing left to add */
break;
}
return c;
}```

## CRC32 Function

```unsigned int crc32 (char *buf, unsigned int len)
{
unsigned int crc;

crc = 0xffffffff;
while (len--) {
crc = crc_table [(crc ^ (unsigned char)*buf++) & 0xff] ^ (crc >> 8);
}
return crc ^ 0xffffffff;
}```

proj/hash/sources.txt · Последние изменения: 2008/06/05 10:54 vak     Copyright (C) 1996-2013 Serge Vakulenko serge@vak.ru 