算法介绍

/*
* 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]

算法实现

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版本

    /**
* 乘法运算版本
*
* @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;
}
`

几个常用实现选项

• INITIAL_VALUE：哈希初始值
• a：哈希乘数

参考

http://www.partow.net/programming/hashfunctions/

http://www.cse.yorku.ca/~oz/hash.html

https://en.wikipedia.org/wiki/Universal_hashing

《Effective Java中文版本》第2版

---转载本站文章请注明作者和出处 二进制之路（binarylife.icu），请勿用于任何商业用途---

《Times 33 哈希算法》有2条留言

1. 其实 C++ 编译器对于能在编译时确定的常数（比如 33），会自动进行这个拆成位运算的优化，所以手写位运算的必要性不大？

回复
• 这个没绝对吧。如果是偏业务开发，在不追求性能极致的情况下，一般会考虑代码可读性和其他成员之间的协作。如果是偏底层技术，会更加关注性能，尽量做各种优化。
在明确知道效果相同的情况下，我觉得怎么用都可以。
不过像一些语言的基础库，基本能用位运算的都会用位运算。

回复