【轉(zhuǎn)載】哈希表的原理，真的很難弄懂么？
劉小愛v
發(fā)布時(shí)間：05-0909:06科技達(dá)人
轉(zhuǎn)載路徑：
https://baijiahao.baidu.com/s?id=1666172942887109917&wfr=spider&for=pc

以下為轉(zhuǎn)載內(nèi)容，原網(wǎng)站有較多方便理解的圖

---

昨天學(xué)習(xí)了幾種簡單數(shù)據(jù)結(jié)構(gòu)，為何要了解數(shù)據(jù)結(jié)構(gòu)？一方面的原因是因?yàn)榧系牡讓泳褪桥c其息息相關(guān)的。

?ArrayList的底層數(shù)據(jù)結(jié)構(gòu)：數(shù)組。

?LinkedList的底層數(shù)據(jù)結(jié)構(gòu)：鏈表。

?TreeSet的底層數(shù)據(jù)結(jié)構(gòu)：紅黑樹。

?HashSet的底層數(shù)據(jù)結(jié)構(gòu)：哈希表。
前天學(xué)習(xí)了Collection集合，其繼承體系圖如下：

今天就來了解Collection的子接口List，Set，以及它們各自的實(shí)現(xiàn)類。

一、List接口

List，翻譯就是列表的意思，列表有何特點(diǎn)？

?它的元素是有序的。

?它是有索引的（Collection沒索引）。

?它的元素是可以重復(fù)的。
Collection是List的父接口，那么Collection中的所有方法，List都能直接拿來用。

List因?yàn)閹饕?#xff0c;所以它相對于Collection的特有方法基本都是索引相關(guān)的。

集合

中有四類方法是最常見的：

也就是增加元素，刪除元素，修改元素，查詢元素，簡稱就是增刪改查。

①增：add方法

可以直接添加元素，也可以根據(jù)索引添加元素。

②刪：remove方法

Collection中的remove方法是刪除對應(yīng)的元素，List中可以根據(jù)索引來刪除元素。

③改：set方法

修改對應(yīng)索引位的元素。

④查：get方法

得到對應(yīng)索引位的元素。

1.ArrayList

這個(gè)集合很早前就學(xué)習(xí)過了，因?yàn)樘Ｒ娏恕?/p>

ArrayList是List的實(shí)現(xiàn)類，看名字就能看出來，其中Array就是數(shù)組的意思，顯而易見，ArrayList的底層就是數(shù)組。數(shù)組查詢快，故ArrayList常用來查詢數(shù)據(jù)。

那么問題來了，數(shù)組長度不可變，ArrayList怎么又可變了呢？

ArrayList默認(rèn)是長度為10的數(shù)組，如果超過了，就會(huì)擴(kuò)容。

如何擴(kuò)容?

創(chuàng)建一個(gè)新的數(shù)組，再將舊數(shù)組復(fù)制進(jìn)去，這樣長度就增加了。

所以本質(zhì)上ArrayList長度可變是因?yàn)榈讓訐Q了數(shù)組。

2.LinkedList

和ArrayList一樣，LinkedLIst也是List的實(shí)現(xiàn)類，其底層是鏈表。鏈表增刪快，故LinkedList常用來增刪數(shù)據(jù)。

集合中重要的是增刪改查四種方法，linkedList有幾種特殊的方法：

①addFirst方法：將元素添加到開頭。

其中push方法和addFirst方法一樣。

②addLast方法：將元素添加到結(jié)尾。

③removeFirst方法：將開頭元素移除并返回。

其中pop方法和removeFirst方法一樣。

④removeLast方法：將結(jié)尾元素移除并返回。

⑤getFirst方法：查詢獲取開頭元素。

⑥getLast方法：查詢獲取結(jié)尾元素。

這幾個(gè)方法都非常簡單，理解其中文意思也就知道其作用了。

其中有兩個(gè)方法比較特殊，官方解釋如下：

?pop方法：從此列表所表示的堆棧處彈出一個(gè)元素。

?push方法：將元素推入此列表所表示的堆棧。
不要看它解釋的這么復(fù)雜，其實(shí)就是堆棧結(jié)構(gòu)，堆棧有什么特點(diǎn)？

先進(jìn)先出，所以無論是增加還是刪除，都是最上面的元素。

二、Set接口

Set和List一樣，都是Collection的子接口。

特點(diǎn)和List剛好相反：

?它的元素是無序的。

?它是沒有索引的。

?它的元素是不能重復(fù)的。
集合有沒有索引的依據(jù)是什么?

如果元素可以重復(fù)，比如說一個(gè)集合存了兩個(gè)元素，都是“劉小愛”，系統(tǒng)要如何判斷它們？所以就需要索引，這樣就能區(qū)分開：1索引位的劉小愛和2索引位的劉小愛，就算元素一樣，索引也不一樣。

故：元素可以重復(fù)，就有索引；元素不可以重復(fù)，就不需要索引。

Set因?yàn)闆]有索引，所以和父接口Collection的方法一樣，沒有特殊方法。

那如何保證元素不重復(fù)？這就得依賴于hashCode和equals方法。

1.Object類的hashCode(哈希值)

Object類有一個(gè)toString方法，代碼如下：

toHexString：是轉(zhuǎn)換成十六進(jìn)制的意思。

也就是說，我們直接打印Object對象得到的一串地址值就是hashCode的十六進(jìn)制。

但是一個(gè)對象它真正的地址值，Java是不會(huì)輕易告訴我們的，一是我們知道了也沒啥用；二是黑客會(huì)拿它做壞事。于是Java就想了個(gè)辦法，對真正的地址進(jìn)行加密，也就是hashCode的由來。

所以什么叫hashCode?

hashCode是對真正的地址進(jìn)行一種加密手段而得到的一串?dāng)?shù)字（什么手段也不用去了解，除非你要去做黑客)。

那么現(xiàn)在問題來了，有沒有可能存在多個(gè)對象地址，對應(yīng)同一個(gè)hashCode呢？

答案是有的，只不過這種情況非常少見。也就是說：

?不同的對象的真正地址是不可能相同的，

?不同對象的hashCode是有可能相同的。
如何理解這句話呢？

就是我們理論上是可以創(chuàng)建無數(shù)多個(gè)對象的，可以不停地在電腦上new對象，但是hashCode值是有限的，它是一個(gè)int類型的數(shù)據(jù)，最多也只有42億（2的32次方）多種可能。

所以不同的對象是有可能出現(xiàn)同一hashCode的，這種情況就叫哈希碰撞，只不過遇到這種情況概率微乎其微。

Object有一個(gè)方法就是hashCode，按照繼承的原則，所有類都有這個(gè)方法。

2.String的hashCode

String的hashCode方法是重寫過了的，跟真正的地址其實(shí)是沒關(guān)系的。

為何要這么做？為了保證Set的元素不可重復(fù)。

?hashCode值若是不相等，那這兩個(gè)元素必定不重復(fù)。

?hashCode值若是相等，這兩個(gè)元素大概率是重復(fù)的，但也有例外。
如下圖幾種情況：

三、哈希表

Set的元素不可重復(fù)，這個(gè)問題該如何解決？

若是我的話，我肯定會(huì)想：將新的元素和Set中的每一個(gè)元素比較一遍不就可以了？如果有相等的，就不添加；如果有不相等的，就添加。

這樣做有問題么，理論上是沒問題的，但是效率太低太低了，每次添加一個(gè)元素就要將元素遍歷一遍。

那些程序員大神為了解決這個(gè)問題，就弄出了哈希表。

所以什么叫哈希表？

哈希表可以用來高效率解決元素不可重復(fù)這個(gè)問題，其本質(zhì)就是：數(shù)組+鏈表+紅黑樹。

①哈希值就有點(diǎn)類似于數(shù)組中的索引，因?yàn)楣Ｖ挡煌湓乇囟ú煌?/p>

數(shù)組查詢快，如果現(xiàn)在添加進(jìn)來了一個(gè)元素，我根本不用遍歷，我就看有沒有相同的哈希值（相當(dāng)于索引），直接就可以定位：

?如果沒有相同的哈希值，直接添加進(jìn)集合。

?如果有相同的哈希值，我再比較內(nèi)容是否一樣。
數(shù)組有一個(gè)問題，就是長度是一定的，所以若是元素過多時(shí)，需要擴(kuò)容。但是哈希表數(shù)據(jù)結(jié)構(gòu)比較復(fù)雜，還要提前擴(kuò)容：哈希表中數(shù)組默認(rèn)長度16，如果數(shù)組中的元素超過了75%就開始擴(kuò)容。

②雖然哈希值一樣，但我還會(huì)比較它們的內(nèi)容是否一樣，用equals方法比較內(nèi)容是否一樣。

?如果內(nèi)容也一樣，重復(fù)元素，不添加進(jìn)集合。

?如果內(nèi)容不一樣，不是重復(fù)元素，添加進(jìn)集合。
③如果鏈表元素?cái)?shù)量超過8，就將鏈表重構(gòu)成紅黑樹。

鏈表查詢是很慢的，所以為了查詢效率，鏈表元素?cái)?shù)量過多，就會(huì)重構(gòu)成紅黑樹，紅黑樹查詢效率比鏈表要快。

這里面涉及就到了兩個(gè)方法：hashCode方法和equals方法，它們一起能很好地判斷元素是否重復(fù)。

所以如果新建了一個(gè)對象，需要重寫hashCode方法和equals方法，這個(gè)在開發(fā)工具中直接使用Alt+Insert自動(dòng)重寫方法。

HashSet的底層原理就是哈希表。

其中LinkedHashSet又是HashSet的一個(gè)子類，其特點(diǎn)主要是有序的Set集合，存儲(chǔ)和取出的順序一致。

總結(jié)

以上是生活随笔為你收集整理的【转载】哈希表的原理，真的很难弄懂么？的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。