1.WHY hashCode()?
集合Set中的元素是無序不可重復的，那判斷兩個元素是否重復的依據是什么呢？ “比較對象是否相等當然用Object.equal()了”，某猿如是說。但是，Set中存在大量對象，后添加到集合Set中的對象元素比較次數會逐漸增多，大大降低了程序運行效率。 Java中采用哈希算法(也叫散列算法)來解決這個問題，將對象(或數據)依特定算法直接映射到一個地址上，對象的存取效率大大提高。這樣一來，當含有海量元素的集合Set需要添加某元素(對象)時，先調用這個元素的hashCode()，就能一下子定位到此元素實際存儲位置，如果這個位置沒有元素，說明此對象時第一次存儲到集合Set, 直接將此對象存儲在此位置上；若此位置有對象存在，調用equal()看看這兩個對象是否相等，相等就舍棄此元素不存，不等則散列到其他地址。
2.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()有可能相等，也有可能不等。
下面是一個例子。在實際的軟件開發中，最好重寫這兩個方法。
|
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
|
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; }} |
3.下面著重介紹一下常用類的hashCode()實現方法。
String類的hasCode()
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
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方法如何調用?
|
1
|
public native int hashCode(); |
Object類的Native方法類可在這里找到。 深入分析請看另外一篇博客
|
1
2
3
4
5
6
7
|
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 的實現。
