# 字符串哈希函数比较

BKDRHash

BKDRHash是Kernighan和Dennis在《The C programming language》中提出的。这个算法的常数131是如何选取的，尚未可知，有知情者可以留言。

public static int bkdrhash(String str) {
final int seed = 131;

```int hash = 0;

for (int i = 0; i < str.length(); i++) {
hash = hash * seed + (int)str.charAt(i);
}

return hash & 0x7FFFFFFF;```

}

APHash

Arash Partow提出了这个算法，声称具有很好地分布性。

public static int aphash(String str) {
int hash = 0;

```for (int i = 0; i < str.length(); i++) {
if ((i & 1) == 0) {
hash ^= (hash << 7) ^ (str.charAt(i)) ^ (hash >> 3);
} else {
hash ^= ~((hash << 11) ^ (str.charAt(i)) ^ (hash >> 5));
}
}

return hash & 0x7FFFFFFF;```

}

JSHash

Justin Sobel提出的基于位的函数函数。

public static int jshash(String str) {
int hash = 0;

```for (int i = 0; i < str.length(); i++) {
hash ^= (hash << 5) + (int)str.charAt(i) + (hash >> 2);
}

return hash & 0x7FFFFFFF;```

}

RSHash

public static int rshash(String str) {
int hash = 0;

```int a = 63689;
final int b = 378551;

for (int i = 0; i < str.length(); i++) {
hash = hash * a + (int)str.charAt(i);
a *= b;
}

return hash & 0x7FFFFFFF;```

}

SDBMHash

SDBM项目使用的哈希函数，声称对所有的数据集有很好地分布性。

public static int sdbmhash(String str) {
int hash = 0;

```for (int i = 0; i < str.length(); i++) {
hash = (int)str.charAt(i) + (hash << 6) + (hash << 16) - hash;
}

return hash & 0x7FFFFFFF;```

}

PJWHash

Peter J. Weinberger在其编译器著作中提出的。

public static int pjwhash(String str) {
int BitsInUnignedInt = 32;
int ThreeQuarters = 24;
int OneEighth = 4;
int HighBits = (int)(0xFFFFFFFF) << (BitsInUnignedInt - OneEighth);
int hash = 0;
int test = 0;

```for (int i = 0; i < str.length(); i++) {
hash = (hash << OneEighth) + (int)str.charAt(i);
if ((test = hash & HighBits) != 0)
{
hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
}
}

return hash & 0x7FFFFFFF;```

}

ELFHash

Unix系统上面广泛使用的哈希函数。

public static int elfhash(String str) {
int hash = 0;
int x = 0;

```for (int i = 0; i < str.length(); i++) {
hash = (hash << 4) + (int)str.charAt(i);

if ((x & hash & 0xF0000000L) != 0) {
hash ^= x >> 24;
hash &= ~x;
}
}

return hash & 0x7FFFFFFF;```

}

DJBHash

Daniel J. Bernstein在comp.lang.c邮件列表中发表的，是距今为止比较高效的哈希函数之一。

public static int djbhash(String str) {
int hash = 5381;

```for (int i = 0; i < str.length(); i++) {
hash += (hash << 5) + (int)str.charAt(i);
}

return hash & 0x7FFFFFFF;```

}

DEKHash

Donald E. Knuth在《计算机程序设计的艺术》中提出的哈希函数。

public static int dekhash(String str) {
int hash = str.length();

```for (int i = 0; i < str.length(); i++) {
hash = (hash << 5) ^ (hash >> 27) ^ (int)str.charAt(i);
}

return hash & 0x7FFFFFFF;```

}

BPHash

public static int bphash(String str) {
int hash = str.length();

```for (int i = 0; i < str.length(); i++) {
hash = (hash << 7) ^ (int)str.charAt(i);
}

return hash & 0x7FFFFFFF;```

}

FNVHash

public static int fnvhash(String str) {
int fnvprime = 0x811C9DC5;
int hash = 0;

```for (int i = 0; i < str.length(); i++) {
hash *= fnvprime;
hash ^= (int)str.charAt(i);
}

return hash & 0x7FFFFFFF;```

}

Java String Hashcode

public static int javahash(String str) {
int hash = 0;

```for (int i = 0; i < str.length(); i++) {
hash = hash * 31 + (int)str.charAt(i);
}

return hash & 0x7FFFFFFF;```

}

bkdrhash 509 72 14
aphash 519 72 15
jshash 494 66 15
rshash 505 74 15
sdbmhash 518 67 15
pjwhash 756 131 34
elfhash 801 158 91
djbhash 512 64 17
dekhash 536 75 22
bphash 1391 696 690
fnvhash 516 65 14
javahash 523 69 16