HashMap中hash()函數如何使用

這篇文章給大家介紹HashMap中hash()函數如何使用，內容非常詳細，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。

一、hashcode是什么

要理解hashcode首先要理解hash表這個概念。

1. 哈希表

hash表也稱散列表(Hash table)，是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散列表。

給定表M，存在函數f(key)，對任意給定的關鍵字值key，代入函數后若能得到包含該關鍵字的記錄在表中的地址，則稱表M為哈希(Hash)表，函數f(key)為哈希(Hash) 函數。

簡單理解就是：在記錄的存儲位置和它的關鍵字之間建立一個確定的對應關系f，使每個關鍵字和結構中一個唯一的存儲位置相對應。

具有快速查找和插入操作的優點。

2. hashcode

hashcode 通過hash函數計算得到，hashcode就是在hash表中有對應的位置

每個對象都有hashcode，通過將對象的物理地址轉換為一個整數，將整數通過hash計算就可以得到hashcode

二、hashcode的作用

HashCode的存在主要是為了查找的快捷性，HashCode是用來在散列存儲結構中確定對象的存儲地址的

對于容器類設計 基本上都會涉及到hashCode。在Java中也一樣，hashCode方法的主要作用是為了配合基于散列的集合一起正常運行，這樣的散列集合包括HashSet、HashMap以及HashTable。

在對集合進行插入操作時，集合內時是不允許存在重復元素的，這樣就引發了一個問題

如何判別在集合中是否已經存在該對象了?

首先想到的方法就是調用equals()方法，這個方法確實可行。但是如果集合中已經存在大量的數據或者更多的數據，如果采用equals方法去逐一比較，效率必然是一個問題。 此時hashCode方法的作用就體現出來了，當集合要添加新的對象時，先調用這個對象的hashCode方法，得到對應的hashcode值，實際上在HashMap的具體實現中會一個表保存已經存進去的對象的hashcode值，如果table中沒有該hashcode值，它就可以直接存進去，不用再進行任何比較了;如果存在該hashcode值， 就調用它的equals方法與新元素進行比較，相同的話就不存了，不相同就散列其它的地址，所以這里存在一個沖突解決的問題，這樣一來實際調用equals方法的次數就大大降低了。

這也就解釋了為什么equals()相等，則hashCode()必須相等。如果兩個對象equals()相等，則它們在哈希表(如HashSet、HashMap等)中只應該出現一次;如果hashCode()不相等，那么它們會被散列到哈希表的不同位置，哈希表中出現了不止一次。

所以說hashCode方法的存在是為了減少equals方法的調用次數，從而提高程序效率。

三、 hashCode()和equals()

Java的基類Object中的 equals()方法用于判斷兩個對象是否相等，hashCode()方法用于計算對象的哈希碼。equals()和hashCode()都不是final方法，都可以被重寫(overwrite)

1. equals方法

通過該實現可以看出，Object類的實現采用了區分度最高的算法，即只要兩個對象不是同一個對象，那么equals()一定返回false。

雖然可以重寫equals()方法，但是有一些注意事項;JDK中說明了實現equals()方法應該遵守的約定

自反性：x.equals(x)必須返回true。

對稱性：x.equals(y)與y.equals(x)的返回值必須相等。

傳遞性：x.equals(y)為true，y.equals(z)也為true，那么x.equals(z)必須為true。

一致性：如果對象x和y在equals()中使用的信息都沒有改變，那么x.equals(y)值始終不變。

非null：x不是null，y為null，則x.equals(y)必須為false。

2. hashCode 方法

hashCode()是一個native方法，而且返回值類型是整形;實際上，該native方法將對象在內存中的地址作為哈希碼返回，可以保證不同對象的返回值不同。

與equals()方法類似，hashCode()方法可以被重寫。JDK中對hashCode()方法的作用，以及實現時的注意事項做了說明：

(1)hashCode()在哈希表中起作用，如java.util.HashMap。

(2)如果對象在equals()中使用的信息都沒有改變，那么hashCode()值始終不變。

(3)如果兩個對象使用equals()方法判斷為相等，則hashCode()方法也應該相等。

(4)如果兩個對象使用equals()方法判斷為不相等，則不要求hashCode()也必須不相等;但是開發人員應該認識到，不相等的對象產生不相同的hashCode可以提高哈希表的性能。

重寫hashcode()的原則

(1)如果重寫了equals()方法，檢查條件“兩個對象使用equals()方法判斷為相等，則hashCode()方法也應該相等”是否成立，如果不成立，則重寫hashCode ()方法。

(2)hashCode()方法不能太過簡單，否則哈希沖突過多。

(3)hashCode()方法不能太過復雜，否則計算復雜度過高，影響性能

hashCode()重寫方法

《Effective Java》中提出了一種簡單通用的hashCode算法：

初始化一個整形變量，為此變量賦予一個非零的常數值，比如int result = 17;

選取equals方法中用于比較的所有域(之所以只選擇equals()中使用的域，是為了保證上述原則的第1條)，然后針對每個域的屬性進行計算：

四、HashMap中的hash()函數

HashMap中并沒有直接使用KV中K原有的hash值; 在HashMap的put、get操作時也未直接使用K中原有的hash值，而使用了一個hash()方法。讓我們一起看一下這個方法

這段代碼類似作用是為了增加hashcode的隨機性

key.hashCode()的作用是返回鍵值key所屬類型自帶的hashcode，返回的類型是int，如果直接拿散列值作為下標訪問HashMap的主數組的話，考慮到int類型值的范圍[-2^31 , 2^31 -1]，雖然只要hash表映射比較松散的話，碰撞幾率很小，但是映射空間太大，內存放不下，所以先做對數組的長度取模運算，得到的余數才能用來訪問數組下標。

hashMap源碼中模運算是在這個indexFor( )函數里完成的把散列值和數組長度-1做一個"與"操作

這也正好解釋了為什么HashMap的數組長度要取2的整數冪。因為數組長度-1相當于一個“低位掩碼”。“與”操作的結果就是散列值的高位全部歸零，只保留低位值.以初始長度16為例，16-1=15。2進制表示是00000000 00000000 00001111。和某散列值做“與”操作如下，結果就是截取了最低的四位值。h & (length - 1) 和 h % length，它倆是等價不等效的，明顯位運算效率非常高。

but 只取后四位，即使散列值分布再松散，碰撞幾率還是很大。更糟糕的是如果散列函數做的比較差吧，分布上成個等差數列啥的，恰好使最后幾個低位呈現規律性重復，就比較蛋疼。

這時候 “hash”函數作用就出來了

右位移16位，正好是32bit的一半，高半區和低半區做異或，就是為了混合原始哈希碼的高位和低位，以此來加大低位的隨機性。而且混合后的低位摻雜了高位的部分特征，這樣高位的信息也被變相保留下來。

設計者考慮到現在的hashCode分布的已經很不錯了，而且當發生較大碰撞時也用樹形存儲降低了沖突。僅僅異或一下，少了系統的開銷，也不會造成因為高位沒有參與下標的計算(table長度比較小時)，從而引起的碰撞。

根據研究結果顯示，當HashMap數組長度為512的時候，也就是用掩碼取低9位的時候，在沒有使用hash()的情況下，發生了103次碰撞，接近30%。而在使用了hash()之后只有92次碰撞。碰撞減少了將近10%。看來擾hash()函數在將降低碰撞上還是有功效的。

關于HashMap中hash()函數如何使用就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。