漫畫:HashCode簡談
equals&hashCode
equals方法在Java的Object類中聲明,直接通過比較地址來判斷對象是否相等
當然Object的子類可以通過重寫equals的方法,實現子類自身的對象是否相等的邏輯;
String是Object的子類,查看下它的equals方法
Integer類的equals方法又是如何實現的呢?
hashCode也跟equals一樣聲明定義在Object類里
大家可以自行查閱該hashCode方法具體分析,
參考文章:
https://www.cnblogs.com/godtrue/p/6395098.html
String類的hashCode進行了重寫
Integer的hashCode也進行了重寫
那麼
為何重寫equals建議同時重寫hashCode呢?
hashCode是什麼?
hashCode有什麼作用?
讓我們查看下Object的源碼里的hashCode的註解(部分截取)
翻譯:
hashCode方法返回一個hash code值,且這個方法是為了更好的支持hash表,比如HashTable、HashMap;
這裡又有了新的疑問,
hash code值是什麼?
hash表是什麼?
為何它對hash表有作用呢?
而我們首先必須先知道的是hash值以及hash表
Hash
我們先看看百度百科對hash的定義
定義
散列(哈希)函數
把任意長度的輸入(又叫做預映射pre-image)通過散列演算法變換成固定長度的輸出,該輸出就是散列值,是一種壓縮映射。
或者說一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。
從定義里我們可以知道,Hash是個函數,且它的特性如下:
h(k1)≠h(k2)則k1≠k2,即散列值不相同,則輸入值即預映射不同
如果k1≠k2,h(k1)=h(k2) 則發生碰撞;
如果h(k1)=h(k2),k1不一定等於k2;
作用
壓縮和加密(單向)的功能
既然是函數,那麼函數的具體演算法有哪些呢?
演算法
基礎演算法
進行加法、乘法、移位、除法、mod等
Java中的String.hashCode
常見經典的Hash演算法
MD4,MD5,SHA-1或SHA-2等其他
衝突(碰撞)
hash是存在碰撞的,如果k1≠k2,h(k1)=h(k2) 則發生碰撞;
碰撞例子
譬如作為輸入值
則h(1)=1,h(2)=2…h(5)=0,h(6)=1,h(7)=2…會出現h(1)=h(6),h(2)=h(7) 等
即k1≠k2,h(k1)=h(k2) ,這種情況就是發生了碰撞
處理衝突
影響衝突三要素
散列函數是否均勻;
處理衝突的方法;
散列表的裝填因子。
散列表的裝填因子定義為:
α= 填入表中的元素個數 / 散列表的長度;
α越大,填入表中的元素較多,產生衝突的可能性就越大;
α越小,填入表中的元素較少,產生衝突的可能性就越小。
處理衝突的方法
再散列法
開放定址法
鏈地址法
公共溢出區
這裡不做具體講解,可參考本文文章的末尾的參考連接
Hash表
依舊百度百科定義
定義
根據關鍵碼值(KEY-VALUE)而直接進行訪問的數據結構;
它通過把關鍵碼值(KEY-VALUE)映射到表中一個位置來訪問記錄,以加快查找的速度。
這個映射函數叫做散列函數,存放記錄的數組叫做散列表。
將k作為輸入值,h(k)輸出值作為內存地址,該內存地址用來存放value
然後可以通過k獲取到value存放的地址,從而獲取value信息
以下圖片是hash表的鏈地址法實現
h(496) =0,h(896)=0則將其插入到h(496)結點後面,避免了衝突
此時我們已經大概知道了Hash與HashTable到底是什麼,又有何作用之後,再回頭講HashCode
HashCode
hashCode是什麼
前面已經提到過了
HashCode是Object的一個方法
hashCode方法返回一個hash code值,且這個方法是為了更好的支持hash表,比如HashTable、HashMap;
HashCode的作用
減少查找次數,提高程序效率
例如查找是否存在重複值
h(k1)≠h(k2)則k1≠k2
首先查看h(k2)輸出值(內存地址),查看該內存地址是否存在值;
如果無,則表示該值不存在重複值;
如果有則進行值比較,相同則表示該值已經存在散列列表中,如果不相同則再進行一個一個值比較;
而無需一開始就一個一個值的比較,減少了查找次數
equals重寫建議同時重寫hashCode
為什麼會建議同時重寫hahCode?
(注意:hashCode要使得兩個相同的對象hash值一樣哦,不然你要hashCode做撒子用?)
讓我們先查看下HashMap的put方法
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
如果這個key對應的鍵值對已經存在,就用新的value代替老的value;
此時如果equals更改,而hashCode不變,則無法確保equals相同hashCode也相同;
那麼e.hash!=hash則無法將已經存在的值進行替換,出現重複值;
所以equals重寫的時候建議同時重寫hashCode,確保相同的值有相同的hashCode
equals與hashCode有兩個注意點
equals相同,則hashCode相同
而hashCode相同,equals不一定相同
如果equals相同,hashCode不相同,有可能會造成上述重複值等情況,這種情況是不允許的;
而hasCode相同,但是equals不一定相同,有可能是因為發生了碰撞而碰撞是有可能性發生的
剩下這2個問題
hashCode方法對hash表有益處?hashCode方法對不是hash表是否有益處?
是否也明了了?
最後附上我啃hashCode的時候,閱覽的不錯的文章,感謝這些作者
參考
哈希表
https://www.cnblogs.com/s-b-b/p/6208565.html
Java hashCode() 和 equals()的若干問題解答
https://www.cnblogs.com/skywang12345/p/3324958.html
簡單通俗地理解Hash哈希存儲
https://blog.csdn.net/nanamasuda/article/details/52087981
淺談Java中的hashcode方法
https://www.cnblogs.com/dolphin0520/p/3681042.html
常見hash演算法的原理
http://www.cnblogs.com/mengfanrong/p/4034950.html
Hash哈希(一)
https://www.cnblogs.com/coder2012/p/3954736.h
TAG:程序員七貓 |