一个好的散列函数通常倾向于“为不相等的对象产生不相等的散列码”。理想情况下,散列函数应该把集合中不相等的实例均匀地分布到所有可能的散列值上。要想完全达到这种理想的情形是非常困难的。幸运的是,相对接近这种理想情形则并不太困难。
由Daniel J. Bernstein教授多年前在comp.lang.c发表的Times 33算法。 它是有史以来发布的最有效的哈希函数之一。
算法介绍
首先,引用一段关于Times 33的介绍:
DJBX33A (Daniel J. Bernstein, Times 33 with Addition)
This is Daniel J. Bernstein's popular `times 33' hash function as
posted by him years ago on comp.lang.c. It basically uses a function
like ``hash(i) = hash(i-1) * 33 + str[i]''. This is one of the best
known hash functions for strings. Because it is both computed very
fast and distributes very well.
The magic of number 33, i.e. why it works better than many other
constants, prime or not, has never been adequately explained by
anyone. So I try an explanation: if one experimentally tests all
multipliers between 1 and 256 (as RSE did now) one detects that even
numbers are not useable at all. The remaining 128 odd numbers
(except for the number 1) work more or less all equally well. They
all distribute in an acceptable way and this way fill a hash table
with an average percent of approx. 86%.
If one compares the Chi^2 values of the variants, the number 33 not
even has the best value. But the number 33 and a few other equally
good numbers like 17, 31, 63, 127 and 129 have nevertheless a great
advantage to the remaining numbers in the large set of possible
multipliers: their multiply operation can be replaced by a faster
operation based on just one shift plus either a single addition
or subtraction operation. And because a hash function has to both
distribute good and has to be very fast to compute, those few
numbers should be preferred and seems to be the reason why Daniel J.
Bernstein also preferred it.-- Ralf S. Engelschall rse@engelschall.com
理解:
Times 33是Daniel J. Bernstein多年前在comp.lang.c上发表的哈希算法,这个算法已被广泛应用,是目前最好的字符串哈希算法之一。因为它不仅计算速度很快,而且分布比较均匀。
核心逻辑是这段代码:
hash(i) = hash(i-1) * 33 + str[i]
这个神奇的数字33,为什么用来计算哈希的效果会比其他许多常数(无论是否为质数)更有效,并没有人给过足够充分的解释。因此,Ralf S. Engelschall尝试通过自己的方法解释其原因。通过对1到256中的每个数字进行测试,发现偶数的哈希效果非常差,根据用不了。而剩下的128个奇数,除了1之外,效果都差不多。这些奇数在分布上都表现不错,对哈希表的填充覆盖大概在86%。
从哈希效果来看(Chi^2应该是指卡方分布),虽然33并不一定是最好的数值。但17、31、33、63、127和129等相对其他的奇数的一个很明显的优势是,由于这些奇数与16、32、64、128只相差1,可以通过移位(如1 << 4 = 16)和加减1来代替乘法,速度更快。
算法实现
DJB Hash Function
An algorithm produced by Professor Daniel J. Bernstein and shown first to the world on the usenet newsgroup comp.lang.c. It is one of the most efficient hash functions ever published.
unsigned int DJBHash(const char* str, unsigned int length)
{
unsigned int hash = 5381;
unsigned int i = 0;
for (i = 0; i < length; ++str, ++i)
{
hash = ((hash << 5) + hash) + (*str);
}
return hash;
}
http://www.partow.net/programming/hashfunctions/
djb2
this algorithm (k=33) was first reported by dan bernstein many years ago in comp.lang.c. another version of this algorithm (now favored by bernstein) uses xor: hash(i) = hash(i - 1) * 33 ^ str[i]; the magic of number 33 (why it works better than many other constants, prime or not) has never been adequately explained.
unsigned long
hash(unsigned char *str)
{
unsigned long hash = 5381;
int c;
while (c = *str++)
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
return hash;
}
http://www.cse.yorku.ca/~oz/hash.html
Java版本
以下是我实现的java版本
/**
* 乘法运算版本
*
* @param value
* @return
*/
public static int time33V1(String value) {
int hash = 0;
for (int i = 0; i < value.length(); i++) {
hash = 33 * hash + value.charAt(i);
}
return hash;
}
/**
* 位运算版本
*
* @param value
* @return
*/
public static int time33V2(String value) {
int hash = 0;
for (int i = 0; i < value.length(); i++) {
hash = ((hash << 5) + hash) + value.charAt(i);
}
return hash;
}
/**
* 5381版本
*
* @param value
* @return
*/
public static int time33V3(String value) {
int hash = 5381;
for (int i = 0; i < value.length(); i++) {
hash = ((hash << 5) + hash) + value.charAt(i);
}
return hash;
}
Java 1.8 String哈希方法
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
几个常用实现选项
values chosen to initialize h and a for some of the popular implementations
其中
- INITIAL_VALUE:哈希初始值
- a:哈希乘数
至于为何选择这些数字的更详细分析,请见下回分解。
题图:azquotes
参考
http://www.partow.net/programming/hashfunctions/
http://www.cse.yorku.ca/~oz/hash.html
https://en.wikipedia.org/wiki/Universal_hashing
《Effective Java中文版本》第2版
转载请注明来源:http://zhanjia.iteye.com/blog/2426782
个人公众号
二进制之路
相关推荐
参考网上博客的感知哈希算法的理论知识,实现基本的感知哈希算法,内有几张图片用来测试,程序可参考。
针对分布式存储系统中如何实现数据在物理存储上的均匀分布和高效定位的问题,对多种哈希算法展开研究,提出了衡量分布式存储系统哈希算法优劣的标准;从散列分布性、哈希冲突和计算效率等多个维度对这些哈希算法进行...
基于python与哈希算法实现图像去重
php-perl哈希实现算法–DJBX33A(Daniel J. Bernstein, Times 33 with Addition)APR哈希默认算法
哈希算法应用领域非常广泛, 现在的web工程密码存储方面基本上都得使用哈希算法
弱哈希算法签名的SSL证书(CVE-2004-2761)。 远程服务使用SSL证书链,该证书链已使用加密弱哈希算法(例如MD2、MD4、MD5或SHA1)签名。这些签名算法很容易受到碰撞攻击。攻击者可以利用这一点生成另一个具有相同数字...
一致性哈希算法
VB6.0语言,SHA256哈希算法源码,做成函数,可以直接调用!!
对已有的负载平衡的改进算法,通过一致性哈希算法,负载平衡更加的有效。
哈希算法C语言实现
Android的感知哈希算法
几个比较著名的哈希算法,还有哈希算法的概念以及如何优化哈希值的分布,在日常软件开发中十分有用
多种哈希算法代码,用于文件校验、简单加密等场合。
相似图搜索原理的简单介绍,内附感知哈希算法的代码
delphi下面开发的国产哈希算法SM3可以直接调用接口 里面的代码注释写的很明白 我自己做项目测试了可以使用 没得问题
sm3哈希算法.rar
哈希表算法C++实现 SGI 哈希表是一个线性存储结构,其关键是哈希函数与哈希值算法
C语言下很实用的哈希算法,你可以将这个头文件加入C函数库中,也可以放入自己编写的程序文件夹中,直接#include即可使用。
本文将全面介绍哈希算法的相关知识,帮助读者了解其在信息安全领域的重要性。 二、哈希算法的基本概念 哈希算法是一种将任意长度的输入数据映射到固定长度输出的单向加密函数。它具有以下特性: 确定性:相同的...
对于原地哈希算法的一些案例应用,三个,分别是查找缺失的最小整数,寻找数组中错误的元素和给出对应的正确元素,寻找重复数。