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

See http://burtleburtle.net/bob/c/lookup3.c

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[0];
		b += k[1];
		c += k[2];
		mix (a, b, c);
		length -= 3;
		k += 3;
	}
 
	/* handle the last 3 unsigned ints */
	switch(length) {
	case 3:
		c += k[2];
	case 2:
		b += k[1];
	case 1:
		a += k[0];
		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