HashMap中hash()函數(shù)如何使用

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

一、hashcode是什么

要理解hashcode首先要理解hash表這個(gè)概念。

1. 哈希表

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

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

簡(jiǎn)單理解就是：在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系f，使每個(gè)關(guān)鍵字和結(jié)構(gòu)中一個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)。

具有快速查找和插入操作的優(yōu)點(diǎn)。

2. hashcode

hashcode 通過hash函數(shù)計(jì)算得到，hashcode就是在hash表中有對(duì)應(yīng)的位置

每個(gè)對(duì)象都有hashcode，通過將對(duì)象的物理地址轉(zhuǎn)換為一個(gè)整數(shù)，將整數(shù)通過hash計(jì)算就可以得到hashcode

二、hashcode的作用

HashCode的存在主要是為了查找的快捷性，HashCode是用來在散列存儲(chǔ)結(jié)構(gòu)中確定對(duì)象的存儲(chǔ)地址的

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

在對(duì)集合進(jìn)行插入操作時(shí)，集合內(nèi)時(shí)是不允許存在重復(fù)元素的，這樣就引發(fā)了一個(gè)問題

如何判別在集合中是否已經(jīng)存在該對(duì)象了?

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

這也就解釋了為什么equals()相等，則hashCode()必須相等。如果兩個(gè)對(duì)象equals()相等，則它們?cè)诠１?如HashSet、HashMap等)中只應(yīng)該出現(xiàn)一次;如果hashCode()不相等，那么它們會(huì)被散列到哈希表的不同位置，哈希表中出現(xiàn)了不止一次。

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

三、 hashCode()和equals()

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

1. equals方法

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

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

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

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

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

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

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

2. hashCode 方法

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

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

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

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

(3)如果兩個(gè)對(duì)象使用equals()方法判斷為相等，則hashCode()方法也應(yīng)該相等。

(4)如果兩個(gè)對(duì)象使用equals()方法判斷為不相等，則不要求hashCode()也必須不相等;但是開發(fā)人員應(yīng)該認(rèn)識(shí)到，不相等的對(duì)象產(chǎn)生不相同的hashCode可以提高哈希表的性能。

重寫hashcode()的原則

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

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

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

hashCode()重寫方法

《Effective Java》中提出了一種簡(jiǎn)單通用的hashCode算法：

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

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

四、HashMap中的hash()函數(shù)

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

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

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

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

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

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

這時(shí)候 “hash”函數(shù)作用就出來了

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

設(shè)計(jì)者考慮到現(xiàn)在的hashCode分布的已經(jīng)很不錯(cuò)了，而且當(dāng)發(fā)生較大碰撞時(shí)也用樹形存儲(chǔ)降低了沖突。僅僅異或一下，少了系統(tǒng)的開銷，也不會(huì)造成因?yàn)楦呶粵]有參與下標(biāo)的計(jì)算(table長(zhǎng)度比較小時(shí))，從而引起的碰撞。

根據(jù)研究結(jié)果顯示，當(dāng)HashMap數(shù)組長(zhǎng)度為512的時(shí)候，也就是用掩碼取低9位的時(shí)候，在沒有使用hash()的情況下，發(fā)生了103次碰撞，接近30%。而在使用了hash()之后只有92次碰撞。碰撞減少了將近10%?？磥頂_hash()函數(shù)在將降低碰撞上還是有功效的。

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