避免hashcode重复

避免hashcode重复

众所周知，Java中如果用String的hashcode作为key，将String保存到HashSet中，这样做是不太可靠的。原因就在于，String的hashcode有可能会重复。比如有这样一个场景，一个网络爬虫需要将所有爬取过的URL保存下来，以便于判断新获取的URL是否已经被访问过，这时就需要有一块内存空间来保存URL，或是保存能够唯一标识URL的ID，比如URL的MD5值或hashcode。如果用hashcode作为URL的ID进行保存的话，当然肯定会比较省内存，但是它带来的一个问题就是，URL通常比较长，其hashcode重复的可能性比较高（我测试了20w个真实的网站URL，结果hashcode重复了2～3个）。一旦出现hashcode重复，这就意味着后面得到的URL会被当成之前访问过的URL，从而被丢弃掉，如果这是一个比较顶层的URL，那也就意味着，可能有大批的子URL无法被获取。这样的话，爬虫爬取的内容肯定是很不完整的，某些情况下，这是无法容忍的。

String.hashCode()方法的算法如下：str.charAt(0) * 31^n-1 + str.charAt(1) * 31^n-2 + ... + str.charAt(n-1)

据说算法中31这个数字是对英文字符进行优化后产生的一个最佳数字，但是碰上字母大小写或是一些特殊字符，再或者是中文字符，它就不灵了，很容易重复，举个例子：

"Aa" = 'A' * 31 + 'a' = 2112
"BB" = 'B' * 31 + 'B' = 2112

要想hashcode不重复，一个简单的做法就是扩大hashcode的取值范围，由原来4个字节的int型，变为8个字节的long型，这样算出来的hashcode重复率大大降低，低到几乎可以忽略不计。以下是改进后的hashcode算法：

	static final long[] byteTable = createLookupTable();static final long HSTART = 0xBB40E64DA205B064L;static final long HMULT = 7664345821815920749L;private static final long[] createLookupTable() {long[] byteTable = new long[256];long h = 0x544B2FBACAAF1684L;for (int i = 0; i < 256; i++) {for (int j = 0; j < 31; j++) {h = (h >>> 7) ^ h;h = (h << 11) ^ h;h = (h >>> 10) ^ h;}byteTable[i] = h;}return byteTable;}public static long hashCode(CharSequence cs) {long h = HSTART;final long hmult = HMULT;final long[] ht = byteTable;final int len = cs.length();for (int i = 0; i < len; i++) {char ch = cs.charAt(i);h = (h * hmult) ^ ht[ch & 0xff];h = (h * hmult) ^ ht[(ch >>> 8) & 0xff];}return h;}

不过该方法有待测试验证。。。