數(shù)據(jù)結(jié)構(gòu)與算法-基礎(chǔ)（十八）哈希表

上期使用 紅黑樹 實(shí)現(xiàn)映射結(jié)構(gòu)，這樣的結(jié)構(gòu)滿足 Key 必須具備可比性，元素有順序地分布 這兩個(gè)特點(diǎn)。在實(shí)際的應(yīng)用場(chǎng)景中，存在結(jié)構(gòu)中的 元素是不需要有序的，并且 Key 也不具備可比較性 ，哈希表完全滿足這樣的應(yīng)用場(chǎng)景。

成都創(chuàng)新互聯(lián)專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于成都做網(wǎng)站、網(wǎng)站建設(shè)、象山網(wǎng)絡(luò)推廣、小程序開發(fā)、象山網(wǎng)絡(luò)營(yíng)銷、象山企業(yè)策劃、象山品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運(yùn)營(yíng)等，從售前售中售后，我們都將竭誠(chéng)為您服務(wù)，您的肯定，是我們最大的嘉獎(jiǎng)；成都創(chuàng)新互聯(lián)為所有大學(xué)生創(chuàng)業(yè)者提供象山建站搭建服務(wù)，24小時(shí)服務(wù)熱線：13518219792，官方網(wǎng)址：www.rwnh.cn

比如設(shè)計(jì)一個(gè)公司的通訊錄，存放所有員工的通訊信息，就可以拿手機(jī)號(hào)作為 index，員工的名稱、職位等作為 value。用哈希表的方式可以將添加、刪除和搜索的時(shí)間復(fù)雜度控制在 O(1)。

這時(shí)創(chuàng)建一個(gè)數(shù)組，手機(jī)號(hào)作為 index，然后存放 value。這樣能將復(fù)雜度控制在 O(1)，但是這種 空間換時(shí)間 的方式也造成了一些其他問題，比如空間復(fù)雜度大（需要更多的空間），空間使用率極其低，非常浪費(fèi)內(nèi)存空間。

哈希表 就是空間換時(shí)間的處理方式，但是做了優(yōu)化，在空間和時(shí)間兩個(gè)緯度中達(dá)到適當(dāng)?shù)钠胶狻?/p>

哈希表也叫做散列表，整體結(jié)構(gòu)就是一個(gè)數(shù)組 ，哈希表會(huì)將 key 用哈希函數(shù)處理之后返回 hash（哈希值），hash 就是哈希表中的 index這樣的處理方式就可以滿足搜索時(shí)間是 O(1)，這樣的處理方式就可以滿足搜索時(shí)間是 O(1)。因?yàn)楣１碇械?key 可能不具備可比較性，所以要做哈希處理。

在執(zhí)行哈希函數(shù)之后返回的 hash，可能會(huì)出現(xiàn)相同的情況 ，這樣的情況就是 哈希沖突 。解決哈希沖突常見的方法有這三種：

JDK1.8 解決哈希沖突的方式就是使用鏈地址法，其中的鏈表就是通過(guò)鏈表+紅黑樹的組合來(lái)實(shí)現(xiàn) 。比如當(dāng)哈希表中的容量大于等于 64，并且單向鏈表的節(jié)點(diǎn)數(shù)大于 8 時(shí)，轉(zhuǎn)換為紅黑樹，不滿足這個(gè)條件時(shí)就使用單向鏈表。

哈希函數(shù) 是生成哈希值的實(shí)現(xiàn)方法，哈希函數(shù)的實(shí)現(xiàn)步驟大致分為兩步：

hash_code 是生成哈希值的函數(shù)，也可以直接用 JAVA 中的標(biāo)準(zhǔn)函數(shù) hashCode() 。

這里可以用 位運(yùn)算替換 % 運(yùn)算，來(lái)提高效率。因?yàn)? 位運(yùn)算是二進(jìn)制運(yùn)算，所以在設(shè)計(jì)數(shù)組的時(shí)候，需要將數(shù)組的長(zhǎng)度設(shè)計(jì)為 2 的冪次方。

一個(gè)良好的哈希函數(shù)，可以讓生成的哈希值分布更加均勻，減少哈希沖突的次數(shù)，最終可以提升哈希表的性能。

Key 的常見類型可能有證書、浮點(diǎn)數(shù)、字符串或者自定義對(duì)象，不同的類型生成哈希值的方式也會(huì)不一樣，但是目標(biāo)是一致的，就是 盡量讓每個(gè) Key 的哈希值唯一，盡量讓 Key 中的所有信息參與運(yùn)算 。

比如在 Java 中， Long 的哈希值實(shí)現(xiàn)如下代碼：

這里的 和 ^ 就是將高 32 bit 和低 32 bit 混合計(jì)算出 32 bit 的哈希值。

在計(jì)算字符串的哈希值時(shí)，可以將字符串拆解成若干個(gè)字符，比如 jack，將它拆解成 j、a、c、k（字符的本質(zhì)就是一個(gè)整數(shù)，所以 jack 的哈希值可以表示為 j * n3 + a * n2 + c * n1 + k * n0，表達(dá)式也可以寫成 [(j * n + a) * n + c] * n + k，代碼實(shí)現(xiàn)如下：

看上面代碼時(shí)，可以發(fā)現(xiàn)，表達(dá)式中的 n 使用的是 31 這個(gè)數(shù)字，那么為什么用 31 呢？

因?yàn)?31 不僅符合 22 - 1 , 而且它還是個(gè)奇素?cái)?shù)（既是技術(shù)，又是素?cái)?shù)，還是質(zhì)數(shù)），素?cái)?shù)和其他數(shù)相乘的結(jié)果比其他方式更容易產(chǎn)生唯一性，減少哈希沖突。

JDK 中，乘數(shù) n 也是用 31，31 也是經(jīng)過(guò)觀測(cè)分布結(jié)果后的選擇，關(guān)于 31 的變體可以有以下幾種：

31 * i = (25 - 1) * i = i * 25 - i = (i 5) - i

關(guān)于Java的地址值和哈希值？

1、hashCode的存在主要是用于查找的快捷性，如Hashtable，HashMap等，hashCode是用來(lái)在散列存儲(chǔ)結(jié)構(gòu)中確定對(duì)象的存儲(chǔ)地址的；

2、如果兩個(gè)對(duì)象相同，就是適用于equals(java.lang.Object) 方法，那么這兩個(gè)對(duì)象的hashCode一定要相同；

3、如果對(duì)象的equals方法被重寫，那么對(duì)象的hashCode也盡量重寫，并且產(chǎn)生hashCode使用的對(duì)象，一定要和equals方法中使用的一致，否則就會(huì)違反上面提到的第2點(diǎn)；

4、兩個(gè)對(duì)象的hashCode相同，并不一定表示兩個(gè)對(duì)象就相同，也就是不一定適用于equals(java.lang.Object) 方法，只能夠說(shuō)明這兩個(gè)對(duì)象在散列存儲(chǔ)結(jié)構(gòu)中，如Hashtable，他們“存放在同一個(gè)籃子里”

JAVA中哈希碼具體是什么？

哈希其實(shí)只是一個(gè)概念，沒有什么真實(shí)的指向。它的目的是保證數(shù)據(jù)均勻的分布到一定的范圍內(nèi)。所以不同數(shù)據(jù)產(chǎn)生相同的哈希碼是完全可以的。

java中哈希一般是希望自己寫算法的。隨便返回什么都可以。如果什么也不寫的話就會(huì)返回地址。如果自己寫，最簡(jiǎn)單的做法是把所有字段拼起一個(gè)長(zhǎng)串做個(gè)hash值。

關(guān)于java的哈希值

HASH

是散列表的基礎(chǔ)計(jì)算方法，Java

內(nèi)置了

hash

的支持，java.lang.Object

默認(rèn)是通過(guò)對(duì)象在內(nèi)存的地址計(jì)算出來(lái)的，所以每個(gè)對(duì)方都是唯一的

hash，但是當(dāng)我們創(chuàng)建我們自己的對(duì)象類時(shí)，我們根據(jù)需要和業(yè)務(wù)邏輯來(lái)決定是否提供自己的

hashcode

和

equals

方法。

多個(gè)對(duì)象的

hash

可能重復(fù)，這是正常的，重復(fù)的對(duì)象在

hash

table

中是分配在同一個(gè)槽

(一個(gè)可以通過(guò)計(jì)算直接跳過(guò)那個(gè)位置的數(shù)組)中，會(huì)再通過(guò)

equals

對(duì)比

(在這個(gè)槽中的

hash

code

都相同的一個(gè)鏈表中逐一

equals

比較

key)

找到那個(gè)對(duì)象。

所以邏輯上是否相同是通過(guò)

equals

來(lái)計(jì)算的，而且

equals

相同的兩個(gè)對(duì)象，它們的

hash

也應(yīng)該相同，如果你不能保證這點(diǎn)，那就說(shuō)明你的

hashcode

和

equals

方法不是使用相同的算法。

一個(gè)對(duì)象是否存在不是通過(guò)

hash

code

來(lái)判斷的，而是

equals。

a

==

b

的話，a.equals

(b)

肯定成立，但反過(guò)來(lái)就不一定。因?yàn)?/p>

a

==

b

比較的是對(duì)象的地址，只有同一個(gè)對(duì)象才能成立，equals

比較的是邏輯角度上的相等性。

看

String

或其它一個(gè)

JRE

自帶的類的

hashcode

和

equals

方法是怎么做到的。

文章標(biāo)題：java計(jì)算哈希值代碼 java的哈希值
網(wǎng)頁(yè)網(wǎng)址：http://www.rwnh.cn/article28/ddosijp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站建設(shè)、網(wǎng)站排名、用戶體驗(yàn)、關(guān)鍵詞優(yōu)化、面包屑導(dǎo)航、

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)