原标題:兩個對象值相同(x.equals(y) == true),但是可能存在hashCode不同嗎?
你覺得咋樣?
面試官的考察點
這道題仍然是考察JVM層面的基本知識,面試官認為,基本功紮實,才能寫出健壯性和穩定性很高的代碼。
涉及到的技術知識
(x.equals(y)==true)
,這段代碼,看起來非常簡單,但其實裡面還是涉及了一些底層知識點的,首先我們基于
equals
這個方法進行探索。
equals
這個方法,在每個對象中都存在,以String類型為例,其方法定義如下
public boolean equals(Object anObject) {
if (this == anObject) {
return true;
}
if (anObject instanceof String) { //判斷對象執行個體是否是String
String anotherString = (String)anObject; //強轉成string類型
int n = value.length;
if (n == anotherString.value.length) { //如果兩個字元串相等,那麼它們的長度自然相等。
//周遊兩個比較的字元串,轉換為char類型逐個進行比較。
char v1[] = value;
char v2[] = anotherString.value;
int i = 0;
while (n-- != 0) {
if (v1[i] != v2[i]) //采用`==`進行判斷,如果不相同,則傳回false
return false;
i++;
}
return true; //否則傳回true。
}
}
return false;
}
首先來分析第一段代碼,判斷傳遞進來的這個對象和目前對象執行個體
this
是否相等,如果相等則傳回
true
。
if (this == anObject) {
return true;
}
那
==
号的處理邏輯是怎麼實作的呢?
了解 ==
判斷
==
在java語言中
==
操作符号,這個比較大家都知道,是基于引用對象的比較,具體其實還有一些其他的差別。
JVM會根據
==
兩邊互相比較的操作類型不同,在編譯時生成不同的指令。
- 對于boolean,byte、short、int、long這種整形操作數,會生成
指令,該指令用于比較整形數值是否相等。關于if_icmpne指令可以參見:Chapter 4. The class File Format,它在Hotspot VM中的bytecodeInterpreter源碼中的具體實作如下if_icmpne
可以看到實質是按照comparison表達式比較操作數棧中偏移量為-1和-2的兩個INT值。#define COMPARISON_OP(name, comparison) CASE(_if_icmp##name): { int skip = (STACK_INT(-2) comparison STACK_INT(-1)) ? (int16_t)Bytes::get_Java_u2(pc + 1) : 3; address branch_pc = pc; UPDATE_PC_AND_TOS(skip, -2); DO_BACKEDGE_CHECKS(skip, branch_pc); CONTINUE; }
- 如果操作數是對象的話,編譯器則會生成if_acmpne指令,與if_icmpne相比将i(int)改成了a(object reference)。這個指令在JVM規範中的表述:Chapter 4. The class File Format,它在Hotspot VM中相應的實作可參考:
COMPARISON_OP(name, comparison) CASE(_if_acmp##name): { int skip = (STACK_OBJECT(-2) comparison STACK_OBJECT(-1)) ? (int16_t)Bytes::get_Java_u2(pc + 1) : 3; address branch_pc = pc; UPDATE_PC_AND_TOS(skip, -2); DO_BACKEDGE_CHECKS(skip, branch_pc); CONTINUE; }
從
STACK_OBJECT(-2) comparison STACK_OBJECT(-1)
這一句即可看出比較的其實是操作數棧上兩個對象在堆中的指針。
對于JVM有一定了解的同學,必然知道
((x==y)=true)
這個判斷,如果
x
和
y
的記憶體位址相同,那麼意味着就是同一個對象,是以直接傳回
true
是以從上面的分析中,得到的結論是,判斷,比較的是兩個對象的記憶體位址,如果
==
傳回true,說明記憶體位址相同。
==
String.equals源碼
繼續分析
equals
中的源碼,剩餘部分源碼的實作邏輯是
- 比較兩個字元串的長度是否相等,如果不相等,直接傳回
false
- 把兩個String類型轉換為char[]數組,并且按照數組順序逐漸比較每一個char字元,如果不相等,同樣傳回
false
public boolean equals(Object anObject) {
//省略
if (anObject instanceof String) { //判斷對象執行個體是否是String
String anotherString = (String)anObject; //強轉成string類型
int n = value.length;
if (n == anotherString.value.length) { //如果兩個字元串相等,那麼它們的長度自然相等。
//周遊兩個比較的字元串,轉換為char類型逐個進行比較。
char v1[] = value;
char v2[] = anotherString.value;
int i = 0;
while (n-- != 0) {
if (v1[i] != v2[i]) //采用`==`進行判斷,如果不相同,則傳回false
return false;
i++;
}
return true; //否則傳回true。
}
}
return false;
}
==和equals
通過上面的分析,我們知道,在 Java 中比較兩個對象是否相等主要是通過
==
号,比較的是他們在記憶體中的存放位址。Object 類是 Java 中的超類,是所有類預設繼承的,如果一個類沒有重寫 Object 的
equals
方法,那麼通過
equals
方法也可以判斷兩個對象是否相同,因為它内部就是通過
==
來實作的。
public boolean equals(Object obj) {
return (this == obj);
}
這裡的相同,是說比較的兩個對象是否是同一個對象,即在記憶體中的位址是否相等。而我們有時候需要比較兩個對象的内容是否相同,即類具有自己特有的“邏輯相等”概念,而不是想了解它們是否指向同一個對象。
例如比較如下兩個字元串是否相同
String a = "Hello"
和
String b = new String("Hello")
,這裡的相同有兩種情形,是要比較 a 和 b 是否是同一個對象(記憶體位址是否相同),還是比較它們的内容是否相等?這個具體需要怎麼區分呢?
如果使用
==
那麼就是比較它們在記憶體中是否是同一個對象,但是 String 對象的預設父類也是 Object,是以預設的
equals
方法比較的也是記憶體位址,是以我們要重寫
equals
方法,正如 String 源碼中所寫的那樣。
- 先比較記憶體位址
- 再比較value值
public boolean equals(Object anObject) {
//省略
if (anObject instanceof String) { //判斷對象執行個體是否是String
String anotherString = (String)anObject; //強轉成string類型
int n = value.length;
if (n == anotherString.value.length) { //如果兩個字元串相等,那麼它們的長度自然相等。
//周遊兩個比較的字元串,轉換為char類型逐個進行比較。
char v1[] = value;
char v2[] = anotherString.value;
int i = 0;
while (n-- != 0) {
if (v1[i] != v2[i]) //采用`==`進行判斷,如果不相同,則傳回false
return false;
i++;
}
return true; //否則傳回true。
}
}
return false;
}
這樣當我們
a == b
時是判斷 a 和 b 是否是同一個對象,
a.equals(b)
則是比較 a 和 b 的内容是否相同,這應該很好了解。
JDK 中不止 String 類重寫了equals 方法,還有資料類型 Integer,Long,Double,Float等基本也都重寫了
equals
方法。是以我們在代碼中用 Long 或者 Integer 做業務參數的時候,如果要比較它們是否相等,記得需要使用
equals
方法,而不要使用
==
因為使用
==
号會有意想不到的坑出現,像這種資料類型很多都會在内部封裝一個常量池,例如 IntegerCache,LongCache 等等。當資料值在某個範圍内時會直接從常量池中擷取而不會去建立對象。
如果要使用
==
,可以将這些資料包裝類型轉換為基本類型之後,再通過
==
來比較,因為基本類型通過
==
比較的是數值,但是在轉換的過程中需要注意 NPE(NullPointException)的發生。
了解Class中的HashCode
回過頭再看一下面試題:兩個對象值相同(x.equals(y) == true),但是可能存在hash code不同嗎?
這個結果傳回
true
,假設
x
y
是String類型,意味着它滿足兩個點。
-
和x
有可能是同一個記憶體位址。y
-
x
這兩個字元串的值是相同的。y
基于這兩個推斷,我們還沒辦法和hash code聯系上,也就是說,這兩個對象的引用位址相同,和hashCode是否有關系?
在Java中,任何一個對象都是派生自Object,而在Object中,有一個
native
方法
hashCode()
public native int hashCode();
為什麼要有hashCode?
對于包含容器結構的程式語言來說,基本上都會涉及到hashCode,它的主要作用是為了配合基于散列的集合一起工作,比如HashSet、HashTable、ConcurrentHashMap、HashMap等。
在這類的集合中添加元素時,首先需要判斷添加的元素是否存在(不允許存在重複元素),也許大多數人都會想到調用equals方法來逐個進行比較,這個方法确實可行。但是如果集合中已經存在一萬條資料或者更多的資料,如果采用equals方法去逐一周遊每個元素的值進行比較,效率會非常低。
此時hashCode方法的作用就展現出來了,當集合要添加新的對象時,先調用這個對象的hashCode方法,得到對應的hashcode值,實際上在HashMap的具體實作中會用一個table儲存已經存進去的對象的hashcode值:
- 如果table中沒有該hashcode值,它就可以直接存進去,不用再進行任何比較了;
- 如果存在該hashcode值, 就調用它的equals方法與新元素進行比較,相同的話就不存了,不相同就散列其它的位址,是以這裡存在一個沖突解決的問題,這樣一來實際調用equals方法的次數就大大降低了.
說通俗一點:Java中的hashCode方法就是根據一定的規則将與對象相關的資訊(比如對象的存儲位址,對象的字段等)映射成一個數值,這個數值稱作為散列值。下面這段代碼是java.util.HashMap的中put方法的具體實作:
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
是以通過
hashCode
,減少了查詢比較的次數,優化了查詢的效率同時也就減少了查詢的時間。
hashCode方法的實作
下面是hashCode這個方法的完整注釋說明。
/**
* Returns a hash code value for the object. This method is
* supported for the benefit of hash tables such as those provided by
* {@link java.util.HashMap}.
* <p>
* The general contract of {@code hashCode} is:
* <ul>
* <li>Whenever it is invoked on the same object more than once during
* an execution of a Java application, the {@code hashCode} method
* must consistently return the same integer, provided no information
* used in {@code equals} comparisons on the object is modified.
* This integer need not remain consistent from one execution of an
* application to another execution of the same application.
* <li>If two objects are equal according to the {@code equals(Object)}
* method, then calling the {@code hashCode} method on each of
* the two objects must produce the same integer result.
* <li>It is <em>not</em> required that if two objects are unequal
* according to the {@link java.lang.Object#equals(java.lang.Object)}
* method, then calling the {@code hashCode} method on each of the
* two objects must produce distinct integer results. However, the
* programmer should be aware that producing distinct integer results
* for unequal objects may improve the performance of hash tables.
* </ul>
* <p>
* As much as is reasonably practical, the hashCode method defined by
* class {@code Object} does return distinct integers for distinct
* objects. (This is typically implemented by converting the internal
* address of the object into an integer, but this implementation
* technique is not required by the
* Java™ programming language.)
*
* @return a hash code value for this object.
* @see java.lang.Object#equals(java.lang.Object)
* @see java.lang.System#identityHashCode
*/
public native int hashCode();
從注釋的描述可以知道,hashCode 方法傳回該對象的哈希碼值。它可以為像 HashMap 這樣的哈希表有益。Object 類中定義的 hashCode 方法為不同的對象傳回不同的整形值。具有迷惑異議的地方就是
This is typically implemented by converting the internal address of the object into an integer
這一句,意為通常情況下實作的方式是将對象的内部位址轉換為整形值。
如果你不深究就會認為它傳回的就是對象的記憶體位址,我們可以繼續看看它的實作,但是因為這裡是 native 方法是以我們沒辦法直接在這裡看到内部是如何實作的。native 方法本身非 java 實作,如果想要看源碼,隻有下載下傳完整的 jdk 源碼,Oracle 的 JDK 是看不到的,OpenJDK 或其他開源 JRE 是可以找到對應的 C/C++ 代碼。我們在 OpenJDK 中找到 Object.c 檔案,可以看到hashCode 方法指向
JVM_IHashCode
方法來處理。
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},
};
而
JVM_IHashCode
方法實作在 jvm.cpp中的定義為:
JVM_ENTRY(jint, JVM_IHashCode(JNIEnv* env, jobject handle))
JVMWrapper("JVM_IHashCode");
// as implemented in the classic virtual machine; return 0 if object is NULL
return handle == NULL ? 0 : ObjectSynchronizer::FastHashCode (THREAD, JNIHandles::resolve_non_null(handle)) ;
JVM_END
這裡是一個三目表達式,真正計算獲得 hashCode 值的是ObjectSynchronizer::FastHashCode,它具體的實作在synchronizer.cpp中,截取部分關鍵代碼片段。
intptr_t ObjectSynchronizer::FastHashCode (Thread * Self, oop obj) {
if (UseBiasedLocking) {
//省略代碼片段
// Inflate the monitor to set hash code
monitor = ObjectSynchronizer::inflate(Self, obj);
// Load displaced header and check it has hash code
mark = monitor->header();
assert (mark->is_neutral(), "invariant") ;
hash = mark->hash();
if (hash == 0) {
hash = get_next_hash(Self, obj);
temp = mark->copy_set_hash(hash); // merge hash code into header
assert (temp->is_neutral(), "invariant") ;
test = (markOop) Atomic::cmpxchg_ptr(temp, monitor, mark);
if (test != mark) {
// The only update to the header in the monitor (outside GC)
// is install the hash code. If someone add new usage of
// displaced header, please update this code
hash = test->hash();
assert (test->is_neutral(), "invariant") ;
assert (hash != 0, "Trivial unexpected object/monitor header usage.");
}
}
// We finally get the hash
return hash;
}
從以上代碼片段中可以發現,實際計算hashCode的是
get_next_hash
,該方法的部分代碼定義如下。
static inline intptr_t get_next_hash(Thread * Self, oop obj) {
intptr_t value = 0 ;
if (hashCode == 0) {
// This form uses an unguarded global Park-Miller RNG,
// so it's possible for two threads to race and generate the same RNG.
// On MP system we'll have lots of RW access to a global, so the
// mechanism induces lots of coherency traffic.
value = os::random() ;
} else
if (hashCode == 1) {
// This variation has the property of being stable (idempotent)
// between STW operations. This can be useful in some of the 1-0
// synchronization schemes.
intptr_t addrBits = cast_from_oop<intptr_t>(obj) >> 3 ;
value = addrBits ^ (addrBits >> 5) ^ GVars.stwRandom ;
} else
if (hashCode == 2) {
value = 1 ; // for sensitivity testing
} else
if (hashCode == 3) {
value = ++GVars.hcSequence ;
} else
if (hashCode == 4) {
value = cast_from_oop<intptr_t>(obj) ;
} else {
// Marsaglia's xor-shift scheme with thread-specific state
// This is probably the best overall implementation -- we'll
// likely make this the default in future releases.
unsigned t = Self->_hashStateX ;
t ^= (t << 11) ;
Self->_hashStateX = Self->_hashStateY ;
Self->_hashStateY = Self->_hashStateZ ;
Self->_hashStateZ = Self->_hashStateW ;
unsigned v = Self->_hashStateW ;
v = (v ^ (v >> 19)) ^ (t ^ (t >> 8)) ;
Self->_hashStateW = v ;
value = v ;
}
value &= markOopDesc::hash_mask;
if (value == 0) value = 0xBAD ;
assert (value != markOopDesc::no_hash, "invariant") ;
TEVENT (hashCode: GENERATE) ;
return value;
}
get_next_hash
的方法中我們可以看到,如果從0開始算的話,這裡提供了6種計算
hash
值的方案,有自增序列,随機數,關聯記憶體位址等多種方式,其中官方預設的是最後一種,即随機數生成。可以看出
hashCode
也許和記憶體位址有關系,但不是直接代表記憶體位址的,具體需要看虛拟機版本和設定。
上面的整體描述還是比較複雜,直接說結論:
- 一個對象的hashCode,預設情況下如果沒有重寫,則由JVM中的
方法來生成,這個生成的方式不一定和記憶體位址有關,預設是用随機數生成。兩個不同的對象,他們生成的hashCode可能會相同,如果存在這個問題,就是所謂的
get_next_hash
,在HashMap中,解決
hash沖突
的方法是鍊式尋址法。
hash沖突
- 使用
這個表達式判斷,如果傳回
==
,意味着兩個對象的hashCode一定相同。
true
問題解答
問題:兩個對象值相同(x.equals(y) == true),但是可能存在hashCode不同嗎?
基于上面背景知識的梳理,再來回答這個問題,就有思路了。
理論情況下,
x.equals(y)==true
,如果沒有重寫
equals
這個方法,這兩個對象的記憶體位址是是相同的,也就意味着hashCode必然也相等。
那有沒有可能hashCode不同呢?如果一定要做,也是可以實作的,我們來看下面這個例子。
public class App
{
public static void main( String[] args ) {
A a = new A();
B b = new B();
System.out.println(a.equals(b));
System.out.println(a.hashCode() + "," + b.hashCode());
}
}
class A {
@Override
public boolean equals(Object obj) {
return true;
}
}
class B {
}
運作結果如下
true
692404036,1554874502
從結果可以看到,
equals
傳回
true
,但是hashCode不同。
雖然我們模拟了這個可能性,但是原則上是錯誤的,因為這樣違反了hashCode的通用規定,可能會導緻該類無法結合所有基于散列集合一起正常工作,比如HashMap、HashSet等。
public class App {
public static void main( String[] args ) {
Person p1=new Person("mic",18);
Person p2=new Person("mic",18);
HashMap<Person,String> hashMap=new HashMap<>();
hashMap.put(p1,"mic");
System.out.println(hashMap.get(p2));
}
}
class Person {
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
//省略getter/setter
@Override
public boolean equals(Object obj) {
if(this==obj){
return true;
}
if(obj instanceof Person){
if(this.getName()==((Person) obj).getName()&&this.getAge()==((Person) obj).getAge()){
return true;
}
}
return false;
}
}
在上述代碼中,重寫了
equals
方法,但是沒有重寫
hashCode
方法,當調用Person類的hashCodo方法時,預設就是調用父類Object的hashCode方法,根據随機數傳回一個整數值。在
equals
方法中,我們是根據
name
age
進行判斷兩個對象是否相等。
在
main
方法中建構了兩個對象
p1
p2
,我們用
HashMap
存儲存儲,将對象作為
key
。把
p1
存入到hashMap中,再通過
p2
來擷取,在原則上,由于p1和p2相等,是以理論上是能夠拿到結果的,但是實際運作結果如下:
null
Process finished with exit code 0
熟知`HashMap 原理的同學應該知道,HashMap 是由數組 + 連結清單的結構組成,這樣的結果就是因為它們 hashCode 不相等,是以放在了數組的不同下标,當我們根據 Key 去查詢的時候結果就為 null。
得到的結果我們肯定不滿意,這裡的
p1
p2
雖然記憶體位址不同,但是它們的邏輯内容相同,我們認為它們應該是相同的。
為了避免這類問題的存在,是以約定了一條原則重寫
equals
方法的同時也需要重寫
hashCode
方法。這是一種通用約定,這個約定包含以下幾個方面。
- 方法都必須始終傳回同一個值。
- 如果兩個對象根據
方法比較是相等的,那麼調用這兩個對象中的equals
方法都必須産生同樣的整數結果。hashCode
-
方法比較是不相等的,那麼調用者兩個對象中的equals
方法,則不一定要求hashCode
方法必須産生不同的結果。但是給不相等的對象産生不同的整數散列值,是有可能提高散清單(hash table)的性能。hashCode
從理論上來說如果重寫了
equals
方法而沒有重寫
hashCode
方法則違背了上述約定的第二條,相等的對象必須擁有相等的散列值。但是規則是大家默契的約定,如果我們就喜歡不走尋常路,在重寫了
equals
方法後沒有覆寫
hashCode
方法,就會造成嚴重的後果。
問題總結
- 如果兩個對象值相同,有可能存在不同的hashCode。具體的實作方法是,隻重寫
方法,不重寫
equals
。
hashCode
- 這種處理方式會存在風險,在實際開發中,必須遵循重寫
方法的同時也需要重寫
equals
方法這一原則。否則在Java散列集合類操作中,會存在null的問題。
hashCode