字符串hash函数的本质

前言

以前在《memcached 源码阅读之字符串 hash 与搜集的一些字符串 hash》中已经记录了一些hash函数.
现在再次记录一下.

本质

如果对算法不感兴趣的人, 只需要看看这个小节就行了, 下面小节的都是无聊的策略与公式.
hash函数的本质是扫描字符串过程中, 根据之前的结果, 当前位置,当前字符的值使用一个公式计算出当前结果.
当然稍微复杂的hash算法会考虑之前所有的的结果,位置以及字符, 甚至会迭代多次.

这篇文章提到了一些书籍, 系统和一些人, 如果想要任何书籍的人都可以加公众号要相关书籍.

核心代码如下:

while((pos, ch) = next()){
    result = cal(result, pos, ch)
}

BKDR Hash

在Brian Kernighan与Dennis Ritchie的《The C Programming Language》一书被展示而得名，是一种简单快捷的hash算法，也是Java目前采用的字符串的Hash算法。

有人说将乘法分解为位运算及加减法可以提高效率.
但其实在Intel平台上，CPU内部对二者的处理效率都是差不多的；
在ARM这类RISC系统上由于ARM内部使用Booth’s Algorithm来模拟32位整数乘法运算，它的效率与乘数有关.

size_t BKDRHash(const char *str) {
	size_t hash = 0;
	register size_t ch = 0;
	while (ch = (size_t)(*str++)) {
		hash = hash * 131 + ch;   // 也可以乘以31、131、1313、13131、131313..
        //hash = hash << 7 + hash << 1 + hash + ch;  
	}
	return hash;
}

SDBM Hash

在开源项目SDBM（一种简单的数据库引擎）中被应用而得名，它与BKDRHash思想一致，只是种子不同而已。

size_t SDBMHash(const char *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;
}

RS Hash

因Robert Sedgwicks在其《Algorithms in C》一书中展示而得名。

size_t RSHash(const char *str) {
	size_t hash = 0;
	register size_t magic = 63689;
	while (size_t ch = (size_t) * str++) {
		hash = hash * magic + ch;
		magic *= 378551;
	}
	return hash;
}

AP Hash

由Arash Partow发明的一种hash算法。

size_t APHash(const char *str) {
	register size_t hash = 0;
	size_t ch = 0;
	for (long i = 0; ch = (size_t)(*str++); i++) {
		if ((i & 1) == 0) {
			hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
		} else {
			hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
		}
	}
	return hash;
}

JS Hash

由Justin Sobel编的一种hash算法。

size_t JSHash(const char *str) {
	register size_t hash = 1315423911;
	size_t ch = 0;
	while (ch = (size_t)(*str++)) {
		hash ^= ((hash << 5) + ch + (hash >> 2));
	}
	return hash;
}

DEK hash

本算法是由于Donald E. Knuth在《Art Of Computer Programming Volume 3》中展示而得名。

size_t DEKHash(const char* str) {
	register size_t hash = 1315423911;
	size_t ch = 0;
	while (ch = (size_t)(*str++)) {
		hash = ((hash << 5) ^ (hash >> 27)) ^ ch;
	}
	return hash;
}

FNV Hash

Unix system系统中使用的一种著名hash算法，后来微软也在其hash_map中实现。

size_t FNVHash(const char* str) {
	register size_t hash = 2166136261;
	size_t ch = 0;
	while (ch = (size_t) * str++) {
		hash *= 16777619;
		hash ^= ch;
	}
	return hash;
}

DJB Hash

由Daniel J. Bernstein教授编的一种hash算法。

size_t DJBHash(const char *str) {
	register size_t hash = 5381;
	size_t ch = 0;
	while (ch = (size_t) * str++) {
		hash += (hash << 5) + ch;
	}
	return hash;
}

size_t DJB2Hash(const char *str) {
	register size_t hash = 5381;
	size_t ch = 0;
	while (ch = (size_t) * str++) {
		hash = hash * 33 ^ ch;
	}
	return hash;
}

PJW Hash

本算法是基于AT&T贝尔实验室的Peter J. Weinberger的论文而发明的一种hash算法。

size_t PJWHash(const char *str) {
	static const size_t TotalBits = sizeof(size_t) * 8;
	static const size_t ThreeQuarters = (TotalBits * 3) / 4;
	static const size_t OneEighth = TotalBits / 8;
	static const size_t HighBits = ((size_t) - 1) << (TotalBits - OneEighth);

	register size_t hash = 0;
	size_t magic = 0;
	size_t ch = 0;
	while (ch = (size_t) * str++) {
		hash = (hash << OneEighth) + ch;
		if ((magic = hash & HighBits) != 0) {
			hash = ((hash ^ (magic >> ThreeQuarters)) & (~HighBits));
		}
	}
	return hash;
}

CRC32 hash

这个就不需要介绍了.

uint32_t crc_32(unsigned char const * data, size_t length, uint32_t sed = 0) {
	uint32_t crc = sed;
	while (length--) {
		crc = crc32_table[(crc ^ *data++) & 0xFFL] ^ (crc >> 8);
	}
	return crc;
}

参考资料

General Purpose Hash Function Algorithms

其他文章

关于作者

曾是一名ACMer, 现在是鹅长视频部门的后台开发。
这里主要记录工作中的技术架构与经验，计算机相关的技术，数学、算法、生活上好玩的东西。
长按二维码关注作者, 了解作者发布的最新好玩的东西

长按图片关注公众号, 接受最新文章消息.

本文首发于公众号：天空的代码世界，微信号：tiankonguse
如果你想留言，可以在微信里面关注公众号进行留言。