从加密的角度讲，一个良好的的哈希函数f应当满足以下三个条件：
- 任意y，找x，使得f(x)=y，非常困难
- 给定x1，找x2，使得f(x1)=f(x2)，非常困难
- 找x1，x2，使得f(x1)=f(x2)，非常困难
从检索访问上来讲，O(1)时间复杂度，一个良好的哈希函数f应当满足：
- f(x)计算常数时间O(1)，非常迅速
- f(x)=y，y是均匀的
- 装载因子尽量小
根据哈希函数是否碰撞，以及哈希值的分布，可以将哈希函数分为四类：
- 普通哈希函数，存在哈希值碰撞
- 完美哈希函数，不存在碰撞，但哈希值域比输入键的域要大(Perfect Hash Function, PHF)
- 最小完美哈希函数，不存在碰撞，但哈希值域与输入键的域一样大(Minimal Perfect Hash Function, MPHF)
- 保续最小完美哈希函数，满足最小完美哈希函数的性质时，还满足若x1<x2，则f(x1)<f(x2)(Order Preserving Minimal Perfect Hash Function, OPMPHF)
下面汇总一些各类软件中使用到的一些普通哈希函数。
Linux中使用的哈希函数：
unsigned long hash_long(unsigned long val,unsigned int bits)
{
unsigned long hash = val * 0x9e370001UL;
return hash >> (32 - bits);
}使用得比较多的是字符串哈希函数。教科书式经典:
unsigned int hash(char *str)
{
register unsigned int h;
register unsigned char *p;
for(h=0, p = (unsigned char *)str; *p ; p++)
h = 31 * h + *p;
return h;
}MySQL中使用的哈希函数:
#ifndef NEW_HASH_FUNCTION
/* Calc hashvalue for a key */
static uint calc_hashnr(const byte *key,uint length)
{
register uint nr=1, nr2=4;
while (length–)
{
nr^= (((nr & 63)+nr2)*((uint) (uchar) *key++))+ (nr << 8);
nr2+=3;
}
return((uint) nr);
}
/* Calc hashvalue for a key, case indepenently */
static uint calc_hashnr_caseup(const byte *key,uint length)
{
register uint nr=1, nr2=4;
while (length–)
{
nr^= (((nr & 63)+nr2)*((uint) (uchar) toupper(*key++)))+ (nr << 8);
nr2+=3;
}
return((uint) nr);
}
#else
/*
* Fowler/Noll/Vo hash
*
* The basis of the hash algorithm was taken from an idea sent by email to the
* IEEE Posix P1003.2 mailing list from Phong Vo (kpv@research.att.com) and
* Glenn Fowler (gsf@research.att.com). Landon Curt Noll (chongo@toad.com)
* later improved on their algorithm.
*
* The magic is in the interesting relationship between the special prime
* 16777619 (2^24 + 403) and 2^32 and 2^8.
*
* This hash produces the fewest collisions of any function that we’ve seen so
* far, and works well on both numbers and strings.
*/
uint calc_hashnr(const byte *key, uint len)
{
const byte *end=key+len;
uint hash;
for (hash = 0; key < end; key++)
{
hash *= 16777619;
hash ^= (uint) *(uchar*) key;
}
return (hash);
}
uint calc_hashnr_caseup(const byte *key, uint len)
{
const byte *end=key+len;
uint hash;
for (hash = 0; key < end; key++)
{
hash *= 16777619;
hash ^= (uint) (uchar) toupper(*key);
}
return (hash);
}
#endif- RS Hash Function
- JS Hash Function
- PJW Hash Function
- ELF Hash Function
- BKDR Hash Function
- SDBM Hash Function
- DJB Hash Function
- DEK Hash Function
- AP Hash Function
http://www.partow.net/programming/hashfunctions/index.html
参考资料：
