哈希函数
写代码的时候hashmap或者hashtable必不可少，下面总结了一些hash函数的C实现。
1. Additive hash
unsigned add_hash(void *key, int len)
{
unsigned char *p = key;
unsigned h = 0;
int i;
for (i = 0; i < len; i++)
{
h += p[i];
}
return h;
}
2. XOR hash
unsigned xor_hash(void *key, int len)
{
unsigned char *p = key;
unsigned h = 0;
int i;
for (i = 0; i < len; i++)
{
h ^= p[i];
}
return h;
}
3. Rotating hash
unsigned rot_hash(void *key, int len)
{
unsigned char *p = key;
unsigned h = 0;
int i;
for (i = 0; i < len; i++)
{
h = (h << 4) ^ (h >> 28) ^ p[i];
}
return h;
}
4. Bernstein hash
unsigned djb_hash(void *key, int len)
{
unsigned char *p = key;
unsigned h = 0;
int i;
for (i = 0; i < len; i++)
{
h = 33 * h + p[i];
}
return h;
}
5. Modified Bernstein
unsigned djb_hash(void *key, int len)
{
unsigned char *p = key;
unsigned h = 0;
int i;
for (i = 0; i < len; i++)
{
h = 33 * h ^ p[i];
}
return h;
}
6. Shift-Add-XOR hash
unsigned sax_hash(void *key, int len)
{
unsigned char *p = key;
unsigned h = 0;
int i;
for (i = 0; i < len; i++)
{
h ^= (h << 5) + (h >> 2) + p[i];
}
return h;
}
7. FNV hash
unsigned fnv_hash(void *key, int len)
{
unsigned char *p = key;
unsigned h = 2166136261;
int i;
for (i = 0; i < len; i++)
{
h = (h * 16777619) ^ p[i];
}
return h;
}
8. One-at-a-Time hash
unsigned oat_hash(void *key, int len)
{
unsigned char *p = key;
unsigned h = 0;
int i;
for (i = 0; i < len; i++)
{
h += p[i];
h += (h << 10);
h ^= (h >> 6);
}
h += (h << 3);
h ^= (h >> 11);
h += (h << 15);
return h;
}
9. JSW hash
unsigned jsw_hash(void *key, int len)
{
unsigned char *p = key;
unsigned h = 16777551;
int i;
for (i = 0; i < len; i++)
{
h = (h << 1 | h >> 31) ^ tab[p[i]];
}
return h;
}
10. ELF hash
unsigned elf_hash(void *key, int len)
{
unsigned char *p = key;
unsigned h = 0, g;
int i;
for (i = 0; i < len; i++)
{
h = (h << 4) + p[i];
g = h & 0xf0000000L;
if (g != 0)
{
h ^= g >> 24;
}
h &= ~g;
}
return h;
}
11. Jenkins hash
#define hashsize(n) (1U << (n))
#define hashmask(n) (hashsize(n) - 1)
#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); \
}
unsigned jen_hash(unsigned char *k, unsigned length, unsigned initval)
{
unsigned a, b;
unsigned c = initval;
unsigned len = length;
a = b = 0x9e3779b9;
while (len >= 12)
{
a += (k[0] + ((unsigned)k[1] << 8) + ((unsigned)k[2] << 16) + ((unsigned)k[3] << 24));
b += (k[4] + ((unsigned)k[5] << 8) + ((unsigned)k[6] << 16) + ((unsigned)k[7] << 24));
c += (k[8] + ((unsigned)k[9] << 8) + ((unsigned)k[10] << 16) + ((unsigned)k[11] << 24));
mix(a, b, c);
k += 12;
len -= 12;
}
c += length;
switch (len)
{
case 11: c += ((unsigned)k[10] << 24);
case 10: c += ((unsigned)k[9] << 16);
case 9: c += ((unsigned)k[8] << 8);
/* First byte of c reserved for length */
case 8: b += ((unsigned)k[7] << 24);
case 7: b += ((unsigned)k[6] << 16);
case 6: b += ((unsigned)k[5] << 8);
case 5: b += k[4];
case 4: a += ((unsigned)k[3] << 24);
case 3: a += ((unsigned)k[2] << 16);
case 2: a += ((unsigned)k[1] << 8);
case 1: a += k[0];
}
mix(a, b, c);
return c;
}