本文研究的主要是Java中hashCode的正确求值方法的相关内容,具体如下。
散列表有一项优化,可以将对象的散列码(hashCode)缓存起来,如果散列码不匹配,就不会检查对象的等同性而直接认为成不同的对象。如果散列码(hashCode)相等,才会检测对象是否相等(equals)。
如果对象具有相同的散列码(hashCode),他们会被映射到同一个散列桶中。如果散列表中所有对象的散列码(hashCode)都一样,那么该散列表就会退化为链表(linked list),从而大大降低其查询效率。
一个好的散列函数通常倾向于“为不想等的对象产生不相等的散列码”。理想情况下,散列函数应该把集合中不想等的实例均匀地分布到所有可能的散列上,但是想要完全达到这种理想的情形是非常困难的,下面给出一个相对简单有效的散列方法:
1.把某个非零的常数值,比如说17,保存在一个名为result的int类型的变量中。
2.对于对象中的每个关键域f(指equals方法中涉及的每个域),完成以下步骤:
- 为该域计算int类型的散列码c
- 如果该域是boolean类型,则计算 ( f ? 1 : 0 )
- 如果该域是byte、char、short或者int类型,则计算 ( ( int ) f )
- 如果该域是long类型,则计算 ( int ) ( f ^ ( f >>> 32 ) )
- 如果该域是float类型,则计算Float.floatToIntBits(f)
- 如果该域是double类型,则计算Double.doubleToLongBits(f),然后按照上述步骤为得到的long类型值再计算散列值
- 如果该域是一个对象引用,并且该类的equals方法通过递归地调用equals的方式来比较它的域,那么同样为这个域按上述方法递归地调用hashCode
- 如果该域是一个数组,则要把每一个元素当作单独的域来处理,递归地应用上述原则,如果数组中的每一个元素都很重要,也可以直接使用Arrays.hashCode方法。
-
按照下面的公式,把上述步骤得到的散列码c依次合并到result中:
result = 31 * result + c;
乘法运算是为了得到一个更好的散列函数。比如如果String的散列函数省略了乘法,那么只是字母顺序不同的所有字符串都会有相同的散列码。这里之所以选择31,是因为它是一个奇素数。如果乘数是偶数,并且乘法溢出的话,信息就会丢失,因为与2相乘等价于位移。使用素数的好处并不是很明显,但是习惯上都使用素数来计算散列结果。31有个很好的特性,即用移位和减法来代替乘法,可以得到更好的性能:31 * i == ( i << 5 ) - i。现在的VM均可以自动实现这种优化。
如果一个类是不可变的(所有域都是final修饰,并且所有域都为基本类型或者也是不可变类),并且计算散列码的开销也比较大,那么就应该考虑把散列码缓存在对象内部。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
public class HashCodeDemo { static class HashCodeClass { private final boolean bResult; private final byte byteValue; private final char charValue; private final short shortValue; private final int intValue; private final long longValue; private final float floatValue; private final double doubleValue; private final String str; private final int [] arrayValue; //volatile表示每次均在内存中去存取该变量,以保证该变量是最新的 private volatile int hashCode; public HashCodeClass() { bResult = false ; byteValue = 1 ; charValue = 'a' ; shortValue = 1 ; intValue = 1 ; longValue = 1l; floatValue = 1 .0f; doubleValue = 1 .0d; str = getClass().getName(); arrayValue = new int [] { 1 , 2 , 3 , 4 , 5 }; } @Override public int hashCode() { if (hashCode == 0 ) { // 设置一个非零的初始值,可以增加零域的冲突性 int result = 17 ; // 如果省略乘数,那么只是字母顺序不同的所有字符串都会有相同的散列码 final int HASH_CODE = 31 ; result = HASH_CODE * result + (bResult ? 1 : 0 ); result = HASH_CODE * result + byteValue; result = HASH_CODE * result + charValue; result = HASH_CODE * result + shortValue; result = HASH_CODE * result + intValue; result = HASH_CODE * result + ( int ) (longValue ^ (longValue >>> 32 )); result = HASH_CODE * result + Float.floatToIntBits(floatValue); long doubleLongValue = Double.doubleToLongBits(doubleValue); result = HASH_CODE * result + ( int ) (doubleLongValue ^ (doubleLongValue >>> 32 )); result = HASH_CODE * result + (str == null ? 0 : str.hashCode()); System.out.println( "str=" + str + ", str.hashCode=" + str.hashCode()); result = HASH_CODE * result + arrayValue.hashCode(); return result; } return hashCode; } } public static void main(String[] args) { HashCodeClass obj = new HashCodeClass(); System.out.println( "obj.hashCode=" + obj.hashCode()); System.out.println( "obj=" +obj.toString()); } } |
输出
1
2
3
4
|
str=com.demo.test.HashCodeDemo$HashCodeClass, str.hashCode=- 205823051 obj.hashCode= 946611167 str=com.demo.test.HashCodeDemo$HashCodeClass, str.hashCode=- 205823051 obj=com.demo.test.HashCodeDemo$HashCodeClass @386c23df |
总结
以上就是本文关于浅谈Java中hashCode的正确求值方法的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!
原文链接:http://blog.csdn.net/chy555chy/article/details/53421055