IT博客汇 | 几种Hash算法的实现

几种Hash算法的实现

armsword发表于 2015-03-02 11:23:29

哈希被广泛使用在很多领域，如数据存储，加密，计算机视觉（几何哈希），此处就简单整理下几个常见的Hash函数的实现，有空陆续补充吧。

BKDR Hash Function

// 本算法由于在Brian Kernighan与Dennis Ritchie的《The C Programming Language》一书被展示而得名，是一种简单快捷的hash算法。
// 也是Java目前采用的字符串的Hash算法（累乘因子为31）。
// 此哈希函数用的最多
template
size_t BKDRHash(const T *str)
{
	register size_t hash = 0;
	while (size_t ch = (size_t)*str++)
	{		
		hash = hash * 131 + ch;   // 也可以乘以31、131、1313、13131、131313..
		// 可将乘法分解为位运算及加减法可以提高效率，如将上式表达为：hash = hash << 7 + hash << 1 + hash + ch;
	}
	return hash;
}

其中累乘因子也可以为131、1313、13131，比如下述代码就使用了33。

unsigned int times33(char *str)
{
    unsigned int val = 0;
    while (*str) 
        val = (val << 5) + val + (*str++);
    return val;
}

此算法也会有如下变种，如：

unsigned int timesnum(char *str, int num)
{
    unsigned int val = 0;
    while (*str) 
        val = val * num + (*str++);
    return val;
}

SDBM Hash Function

// 本算法是由于在开源项目SDBM（一种简单的数据库引擎）中被应用而得名，它与BKDRHash思想一致，只是种子不同而已。
template
size_t SDBMHash(const T *str)
{
	register size_t hash = 0;
	while (size_t ch = (size_t)*str++)
	{
		hash = 65599 * hash + ch;		
		//hash = (size_t)ch + (hash << 6) + (hash << 16) - hash;
	}
	return hash;
}

AP Hash Function

// Arash Partow发明的一种hash算法 
// 比较优秀的一种哈希算法
unsigned int APhash(char *str)
{
    unsigned int val = 0;
    int i = 0;
    for (i = 0; *str; i++) 
        if ((i & 1) == 0)
            val ^= ((val << 7)^(*str++)^(val>>3));
        else
            val ^= (~((val << 11)^(*str++)^(val>>5)));
    return (val & 0x7FFFFFFF);	
}

FNV Hash Function

// Unix system系统中使用的一种著名hash算法，后来微软也在其hash_map中实现。
template
size_t FNVHash(const T* str)
{
	if(!*str)
		return 0;
	register size_t hash = 2166136261;
	while (size_t ch = (size_t)*str++)
	{
		hash *= 16777619;
		hash ^= ch;
	}
	return hash;
}

其实关于为什么要用异或，我搜索了下原因，见Why is XOR the default way to combine hashes?

MySQL中出现的字符串哈希函数

unsigned int MySQLhash(char *str)
{
    register unsigned int nr = 1, nr2 = 4;
    while(*str) {
        nr ^= (((nr & 63) + nr2)*((unsigned int)*str++)) + (nr << 8);
        nr2 += 3;	
    }
    return (unsigned int)nr;
}

参考链接：
spiderq
各种哈希函数冲突率分析