本文主要讨论下不同的hashCode()的实现对应用程序的性能影响。
hashCode()方法的主要目的就是使得一个对象能成为hashMap的key或者存储到hashset中。这种情况下对象还得实现equals(Object)方法，它的实现和hashCode()必须是一致的：
- 如果a.equals(b)那么a.hashCode == b.hashCode()
- 如果hashCode()在同一个对象上被调用两次，它应该返回的是同一个值，这表明这个对象没有被修改过。
hashCode的性能
从性能的角度来看的话，hashCode()方法的最主要目标就是尽量让不同的对象拥有不同的hashCode。JDK中所有的基于hash的集合都是存储在数组中的。hashcode会用来计算数组中的初始的查找位置。然后调用equals方法将给定的值和数组中存储对象的值进行比较。如果所有的值都有不同的hashCode，这会减少hash的碰撞概率。换句话说，如果所有的值都共享一个hashCode的话，hashmap(或者hashset)会蜕化成一个列表，操作的时间复杂度会变成O(n2)。
更多细节可以看下hash map碰撞的解决方案。JDK用了一个叫开放寻址的方法，不过还有一种方法叫拉链法。所有hashcode一样的值存储在一个链表里。
我们来看下不同质量的hashcode的区别是什么。我们拿一个正常的String和一个String的包装类进行比较，它重写了hashCode方法，所有的对象返回的是同一个hashCode。
private static class SlowString
{
public final String m_str;
public SlowString( final String str ) {
this.m_str = str;
}
@Override
public int hashCode() {
return 37;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
final SlowString that = ( SlowString ) o;
return !(m_str != null ? !m_str.equals(that.m_str) : that.m_str != null);
}
}
下面是一个测试方法。后面我们还会再用到它，所以这里还是简单介绍一下 。它接收一个对象列表，然后对列表中的每个元素依次调用Map.put(), Map.containsKey()方法。
private static void testMapSpeed( final List lst, final String name )
{
final Map map = new HashMap( lst.size() );
int cnt = 0;
final long start = System.currentTimeMillis();
for ( final Object obj : lst )
{
map.put( obj, obj );
if ( map.containsKey( obj ) )
++cnt;
}
final long time = System.currentTimeMillis() - start;
System.out.println( "Time for " + name + " is " + time / 1000.0 + " sec, cnt = " + cnt );
}
String和SlowString对象都是通过一个"ABCD"+i的格式生成的。处理100000个String对象的话，需要的时间是0.041秒。而处理SlowString对象的话，则需要82.5秒。
结果表明，String类的hashCode()方法的质量明显胜出。我们再做另外一个测试。我们创建一个字符串列表，前半部分的格式是"ABCdef*&"+i，后半部分的是”ABCdef*&"+i+"ghi"（确保字符串的中间部分变化而结尾不变，不会影响hashCode的质量）。我们会创建1M，5M，10M，20M个字符串，来看下有多少个字符串是共享hashcode的，同一个hashcode又被多少个字符串共享。下面是测试的结果：
Number of duplicate hashCodes for 1000000 strings = 0 Number of duplicate hashCodes for 5000000 strings = 196 Number of hashCode duplicates = 2 count = 196 Number of duplicate hashCodes for 10000000 strings = 1914 Number of hashCode duplicates = 2 count = 1914 Number of duplicate hashCodes for 20000000 strings = 17103 Number of hashCode duplicates = 2 count = 17103
可以看到，很少有字符串是共享同一个hashCode的，而一个hashcode被两个以上的字符串共享的概率则非常之小。当然了，你的测试数据可能不太一样——用这个测试程序测试你给定的key的话。
自动生成long字段的hashCode方法
值得一提的是，大多数IDE是如何自动生成long类型的hashcode方法的。下面是一个生成的hashCode方法，这个类有两个long字段。
public int hashCode() {
int result = (int) (val1 ^ (val1 >>> 32));
result = 31 * result + (int) (val2 ^ (val2 >>> 32));
return result;
}
下面给只有两个int类型的类生成的方法：
public int hashCode() {
int result = val1;
result = 31 * result + val2;
return result;
}
可以看到，long类型的处理是不一样的。java.util.Arrays.hashCode(long a[])用的也是同样的方法。事实上，如果你将long类型的高32位和低32位拆开当成int处理的话，生成的hashCode的分布会好很多。下面是两个long字段的类的改进后的hasCode方法（注意，这个方法运行起来比原来的方法要慢，不过新的hashCode的质量会高很多，这样的话hash集合的执行效率会得到提高，虽然hashCode本身变慢了）。
public int hashCode() {
int result = (int) val1;
result = 31 * result + (int) (val1 >>> 32);
result = 31 * result + (int) val2;
return 31 * result + (int) (val2 >>> 32);
}
下面是testMapSpeed 方法分别测试10M个这三种对象的结果。它们都是用同样的值进行初始化的。
| Two longs with original hashCode | Two longs with modified hashCode | Two ints |
| 2.596 sec | 1.435 sec | 0.737 sec |
可以看出，更新后的hashCode方法的效果是不太一样的。虽然不是很明显，但是对性能要求很高的地方可以考虑一下它。
高质量的String.hashCode()能做些什么
假设我们有一个map，它是由String标识符指向某个特定的值。map的key（String标识符)只会存储在这个map中（同一时间，最多有一部分是存储在别的地方）。假设我们已经收集了map的所有entry，比如说在某个两阶段算法中的第一个阶段。第二个阶段我们需要通过key来查找map。我们只会用已经map里存在的key进行查找。
我们如何能提升map的性能?前面你已经看到了，String.hashCode()返回的几乎都是不同的值，我们可以扫描所有的key，计算出它们的hashCode，找出不是唯一的那些hashcode:
Map cnt = new HashMap( max );
for ( final String s : dict.keySet() )
{
final int hash = s.hashCode();
final Integer count = cnt.get( hash );
if ( count != null )
cnt.put( hash, count + 1 );
else
cnt.put( hash, 1 );
}
//keep only not unique hash codes
final Map mult = new HashMap( 100 );
for ( final Map.Entry entry : cnt.entrySet() )
{
if ( entry.getValue() > 1 )
mult.put( entry.getKey(), entry.getValue() );
}
现在我们可以创建两个新的map。为了简单点，假设map里存的值就是Object。在这里，我们创建了Map 和Map（生产环境推荐使用TIntObjectHashMap）两个map。第一个map存的是那些唯一的hashcode以及对应的值，而第二个，存的是那些hashCode不唯一的字符串以及它们相应的值。
final Map unique = new HashMap( 1000 );
final Map not_unique = new HashMap( 1000 );
//dict - original map
for ( final Map.Entry entry : dict.entrySet() )
{
final int hashCode = entry.getKey().hashCode();
if ( mult.containsKey( hashCode )
not_unique.put( entry.getKey(), entry.getValue() );
else
unique.put( hashCode, entry.getValue() );
}
//keep only not unique hash codes
final Map mult = new HashMap( 100 );
for ( final Map.Entry entry : cnt.entrySet() )
{
if ( entry.getValue() > 1 )
mult.put( entry.getKey(), entry.getValue() );
}
现在，为了查找某个值，我们得先查找第一个hashcode唯一的map，如果没找到，再查找第二个不唯一的map：
public Object get( final String key )
{
final int hashCode = key.hashCode();
Object value = m_unique.get( hashCode );
if ( value == null )
value = m_not_unique.get( key );
return value;
}
在一些不太常见的情况下，你的不唯一的map里的对象可能会很多。遇见这种情况的话，先尝试用java.util.zip.CRC32或者是java.util.zip.Adler32来替换掉hashCode的实现方法（Adler32比CRC32要快，不过它的分布较差些）。如果实在不行，尝试用两个不同的函数来计算hashcode：低32位和高32位分别用不同的函数生成。hash函数就用Object.hashCode, java.util.zip.CRC32或者java.util.zip.Adler32。
（译注：这么做的好处就是压缩了map的存储空间，比如你有一个map，它的KEY存100万个字符串的话，压缩了之后就只剩下long类型以及很少的字符串了）
set的压缩效果更明显
前面那个例子中，我们讨论了如何去除map中的key值。事实上,优化set的话效果会更加明显。set大概会有这么两个使用场景：一个是将原始的set拆分成多个子set，然后依次查询标识符是否属于某个子set；还有一个是写一个拼写检查器（spellchecker ）——有些要查询的值是预想不到的值（比如拼写错误了），而就算出了些错误的话影响也不是很大（如果碰巧另一个单词也有同样的hashCode，你会认为这个单词是拼写正确的)。这两种场景set都非常适用。
如果我们延用前面的方法的话，我们会得到一个唯一的hashcode组成的Set,不唯一的hashCode得到的是一个Set。这里至少能优化掉不少字符串的空间。
如果我们可以把hashCode的取值限制在一定的区间内（比如说2^20)，那么我们可以用一个BitSet来代替Set，这个在BitSet一文中已经提到了。一般来说如果我们提前知道原始set的大小的话，hashcode的范围是有足够的优化空间的。
下一步就是确定有多少个标识符是共享相同的hashcode的。如果碰撞的hashcode比较多的话，改进你的hashCode方法，或者增加hashcode的取值范围。最完美的情况就是你的标记符全都有唯一的hashcode( 这其实不难实现）。优化完的好处就是，你只需要一个BitSet就够了，而不是存储一个大的字符串集合。
总结
改进你的hashCode算法的分布。优化它比优化这个方法的执行速度要重要多了。千万不要写一个返回常量的hashCode方法。
String.hashCode的实现已经相当完美了，因此很多时候你可以用String的hashCode来代替字符串本身了。如果你使用的是字符串的set，试着把它优化成BitSet。这将大大提升你程序的性能。
原创文章转载请注明出处：http://it.deepinmind.com
英文原文链接