java hashcode() 方法深入理解-mile米乐体育
java.lang.object 有一个hashcode()和一个equals()方法，这两个方法在软件设计中扮演着举足轻重的角色。在一些类中覆写这两个方法以完成某些重要功能。本文描述了为什么要用hashcode(), 如何使用，以及其他的一些扩展。阅读本文需要有基本的hash算法知识以及基本的java集合知识，本文属于菜鸟入门级讲解，大神读至此请点击右上角的x，以免浪费您的时间^_^。
why hashcode()?
集合set中的元素是无序不可重复的，那判断两个元素是否重复的依据是什么呢？ “比较对象是否相等当然用object.equal()了”，某猿如是说。但是，set中存在大量对象，后添加到集合set中的对象元素比较次数会逐渐增多，大大降低了程序运行效率。 java中采用哈希算法(也叫散列算法)来解决这个问题，将对象(或数据)依特定算法直接映射到一个地址上，对象的存取效率大大提高。这样一来，当含有海量元素的集合set需要添加某元素(对象)时，先调用这个元素的hashcode()，就能一下子定位到此元素实际存储位置，如果这个位置没有元素，说明此对象时第一次存储到集合set, 直接将此对象存储在此位置上；若此位置有对象存在，调用equal()看看这两个对象是否相等，相等就舍弃此元素不存，不等则散列到其他地址。
how use hashcode()?
java语言对猿设计equal()有五个必须遵循的要求。
- 对称性。若 a.equal(b) 返回”true”, 则 b.equal(a) 也必须返回 “true”.
- 反射性。a.equal(a) 必须返回”true”.
- 传递性。若a.equal(b) 返回 “true”, 且 b.equal(c)返回 “true”, 则c.equal(a)必返回”true”.
- 一致性。若a.equal(b) 返回”true”, 只要a, b内容不变，不管重复多少次a.equal(b)必须返回”true”.
- 任何情况下，a.equals(null)，永远返回是“false”；a.equals(和a不同类型的对象)永远返回是“false”.
hashcode()的返回值和equals()的关系.
- 如果a.equals(b)返回“true”，那么a和b的hashcode()必须相等。
- 如果a.equals(b)返回“false”，那么a和b的hashcode()有可能相等，也有可能不等。
下面是一个例子。在实际的软件开发中，最好重写这两个方法。
public class employee { int employeeid; string name; // other methods would be in here @override public boolean equals(object obj) { if(obj==this) return true; employee emp=(employee)obj; if(employeeid.equals(emp.getemployeeid()) && name==emp.getname()) return true; return false; } @override public int hashcode() { int hash = 1; hash = hash * 17 employeeid; hash = hash * 31 name.hashcode(); return hash; } } 下面着重介绍一下常用类的hashcode()实现方法。
string类的hascode()
java代码
public int hashcode() { int h = hash; if (h == 0) { int off = offset; char val[] = value; int len = count; for (int i = 0; i < len; i ) { h = 31*h val[off ]; } hash = h; } return h; } 这段代码最有意思的还是hash的实现方法了。最终计算的hash值为：
s[0]31n-1 s[1]31n-2 … s[n-1]
s[i]是string的第i个字符，n是string的长度。那为什么这里用31，而不是其它数呢?
31是个奇素数，如果乘数是偶数，并且乘法溢出的话，信息就会丢失，因为与2相乘等价于移位运算。使用素数的好处并不是很明显，但是习惯上都使用素数来计算散列结果。31有个很好的特性，就是用移位和减法来代替乘法，可以得到更好的性能：31*i==(i<<5)-i。现在的vm可以自动完成这种优化。(from effective java)
object类的hascode()
object类中hashcode()是一个native方法。native方法如何调用?
public native int hashcode();
object类的native方法类可在这里找到。 深入分析请看另外一篇博客
static jninativemethod methods[] = { {"hashcode", "()i", (void *)&jvm_ihashcode}, {"wait", "(j)v", (void *)&jvm_monitorwait}, {"notify", "()v", (void *)&jvm_monitornotify}, {"notifyall", "()v", (void *)&jvm_monitornotifyall}, {"clone", "()ljava/lang/object;", (void *)&jvm_clone}, }; 源代码包括getclass()(see line58)等, hashcode()(see line43)被定义为一个指向jvm_ihashcode指针。
jvm.cpp中定义了jvm_ihashcode(line 504)函数, 此函数里调用objectsynchronizer::fasthashcode，其定在 synchronizer.cpp, 可参考576行的fasthashcode 和 530行的 get_next_hash 的实现。