优化哈希策略-java开发java经验技巧

《优化哈希策略-java开发java经验技巧》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、优化哈希策略・编程开发技术优化哈希策略木文由ImportNew・fzr翻译自javacodegeekso欢迎加入翻译小组。转载请见文末要求。概述散列策略会对HashMap或HashSet之类的散列集合的性能产生直接的影响。内置的散列（乂称哈希）函数都是通用的，在大多数使用情况下都能表现很好。但是我们能不能做的更好呢，特别是当你对某个用例产牛了很好的想法吋？测试一个散列策略在先前的一篇文章中，我研究了一些测试散列策略的方法，其中特别注意了一种“止交位”优化的散列策略，它仅仅只是改变一个位就能确保每个散列结果

2、尽可能的不同。.然而，如果要对一个已知的元索或关键字集合进行散列，你就可以针对具体案例进行优化，而不是寻求一个通用方案。减少冲突一个散列集合中最主耍的事情就是避免冲突了。所谓冲突，就是两个以上关键字映射到同一个散列槽中。这些冲突意味着当有多个关键字映射到同一个散列槽中时你必须要付出更多的努力来检查那些关键字是否是你想要的那个。理想状态下一个散列槽中最多有一个关键字。我只需要唯一的散列码，是吗?通常的误解是只要散列码唯一就口J以避免冲突。虽然都希望散列码是唯一的，但它还不够。假设现在有一些关键字，每一个都有

3、唯一的32位散列码。如果你有40亿散列槽,每个关键字都有口己的槽，那就没有冲突了。对于所有的散列集合，这样大的数组一般是不太现实的。事实上，HashMap和HashSet的人小都收到机器内存的限制，一般为2飞0,大概刚刚超过10亿。当你只能冇一个规模上比较实际的哈希集合时又该如何呢？散列槽的数目需要更小一些，而散列码需对散列槽数目取模。如果散列槽数是2的幕值，你可以用最低位当掩码。來看个例子，ftse350.csvo如果把第一列作为关键字或是元素，就有352个字符串。这些字符串有唯一的StringO.ha

4、shCodc()码,但是假设我们只取这些散列码的低位。会不会有冲突呢？MaskString.hashCode()maskedHashMap.hash(String.hashCodeO)masked32bitsNocollisionsNocollisions16bits1collision3collisions15bits2collisions4collisions14bits6collisions6collisions13bits11collisions9collisions12bits17collisi

5、ons15collisions11bits29collisions25collisions10bits57collisions50collisions9bits103collisions92collisions一个装载因子是0.7(默认)的HashMap的大小是512,使用哈希码的低九位作为掩码。可以看到，尽管原始的哈希码是唯一的，仍然有大约30%的关键字会冲突。•HashTcstcrMain的代码在这里。为了减少糟糕的散列策略造成的影响，HashMap使用了扰动函数。Java8里的实现相当简单。下面是來

6、自HashMap.hash的源码。想了解更多细节,可以阅读Javadoc文档。staticfinalinthash(Objectkey){inth;return(key==null)?0:(h=key.hashCode())八(h>>>16);}这个方法混合了原始哈希码的高位和低位，以此来提高低位的随机性。对于像上面的那样有相当高的冲突率的情况，这就是一个改善方法。请参看第三列。初探String类的散列函数卜面是String.hashCodcO的代码:publicinthashCode(){inth二ha

7、sh;if(h二二0&&value,length>0){charval[]=value;for(inti=0;i

8、然很重要，但是你并不想让它过丁重要；因为总是冇些时候你选的数字并不适合你的使用场景。这就是为什么你同时还需要一个即使在魔法数字选取很耕糕的情况下其最坏情况依然不是特别差的代码结构。用别的乘数代替31MultiplierCollisions12302167311349951056102793890910010911191可以看到，魔法数的选取的确很重要，但需要尝试的数字太多了。我们需要写一个测试程序，测试出一个不错的随机选择。I