文章目錄

• 引入：TreeMap的局限性
• 哈希表概念
• 哈希沖突 以及JDK1.8的哈希沖突是如何解決的
• 哈希函數(shù)
• 不同數(shù)據(jù)類型對應(yīng)的哈希函數(shù)
• • int 和 float
  • long 和 double
  • 字符串的哈希值計算
  • 關(guān)于自定義對象的哈希值計算方法
  • 區(qū)分Key與哈希值與索引與Value！！！

---

引入：TreeMap的局限性

---

哈希表概念

如下：說實(shí)話第一次看到這個，直接用Key值當(dāng)索數(shù)組引，我尋思這不就一大型數(shù)組嗎，確實(shí)是做到了添加刪除搜索全部O1，但是也真是浪費(fèi)了很多空間

看到后面，哦，原來上面是開玩笑的，哈希表通過引入哈希函數(shù)的概念，解決了浪費(fèi)空間的問題，哈希函數(shù)就是通過Key值通過函數(shù)計算這個元素在數(shù)組中的真實(shí)索引，這樣就可以做到既是數(shù)組存儲，又一個Key對應(yīng)一個數(shù)組元素，并不浪費(fèi)空間

---

哈希沖突 以及JDK1.8的哈希沖突是如何解決的

如圖

JDK1.8使用鏈地址法解決哈希沖突，在添加元素時，計算索引，若索引處已經(jīng)有一個或多個元素，則比較新添加元素的Key與索引處元素鏈表里的Key，比較直到鏈表尾部，若Key不重合則直接在鏈表尾部添加。所以自然不用雙向鏈表

---

哈希函數(shù)

就是計算哈希值的函數(shù)
哈希函數(shù)通過Key計算數(shù)組內(nèi)的索引，所以要求計算出來的索引一定是要在數(shù)組的最大長度以內(nèi)的，所以下面的%運(yùn)算和與（&&）運(yùn)算都可以做到，最后計算出來的結(jié)果在數(shù)組長度以內(nèi)，但是與運(yùn)算對于計算機(jī)而言效率更高

---

不同數(shù)據(jù)類型對應(yīng)的哈希函數(shù)

int 和 float

如下圖為 int 類型和 float類型的哈希函數(shù)
在選擇哈希函數(shù)時，要盡量遵守兩個原則：

盡量讓生成的哈希值彼此唯一

盡量讓Key的所有信息參與運(yùn)算生成哈希值

long 和 double

long和double屬于轉(zhuǎn)換成二進(jìn)制屬于64位，而java中規(guī)定hash函數(shù)的返回值只能是一個32位的int值，所以這兩位的哈希函數(shù)要通過64位的計算，生成一個32位的哈希值

小尖尖是亦或運(yùn)算，二者相同則為1，二者相反則為0
就是先把long和double轉(zhuǎn)換成64位二進(jìn)制表達(dá)，然后取前32位和后32位進(jìn)行亦或運(yùn)算，生成一個32位的哈希值，這樣64位就都參與生成了哈希值。

字符串的哈希值計算

字符串的哈希值就是用類似把二進(jìn)制轉(zhuǎn)換成十進(jìn)制的過程，每個字符×31的位數(shù)減一次冪，加上后面的字符同樣如此，其中字符在運(yùn)算過程中被轉(zhuǎn)換成為對應(yīng)的ASCII碼

為什么是31呢，這是一個數(shù)學(xué)問題，我們只需要知道i×31可以表達(dá)為位運(yùn)算左移5位在減去i就可以了，位運(yùn)算效率比較高，而java內(nèi)部也確實(shí)是這么轉(zhuǎn)化的，關(guān)于為什么是31可以看下面這張更具體

關(guān)于自定義對象的哈希值計算方法

默認(rèn)自定義對象在的哈希函數(shù)的參數(shù)是 對象實(shí)體的地址 ，也就是說哈希值是通過地址計算出來的。
但這導(dǎo)致了一個問題，兩個內(nèi)容相同的對象因?yàn)榈刂凡煌?#xff0c;而在哈希表中被視為兩個不同的元素，想要解決這個問題就需要自己重寫一個hashcode函數(shù)，重寫的函數(shù)計算方法類似字符串，是每個元素的哈希值*31的n次冪加起來的和：如下圖
同時又導(dǎo)致了一個問題，就是如果對象插入時索引處已經(jīng)有了元素，這時候就要在索引處單鏈表進(jìn)行比較，比較已經(jīng)有的元素與插入的元素Key是否相同，而官方的比較方法是比較地址，這樣就會造成索引處有可能存儲兩個內(nèi)容相同但是地址不同的自定義對象，為了解決這個問題，我們可以自己寫一個對象比較equal函數(shù)
只有同時自己實(shí)現(xiàn)了hashCode函數(shù)與equal函數(shù)，才能保證哈希表中不會存儲兩個內(nèi)容相同但地址不同的自定義對象Key。

只重寫equal函數(shù)，會導(dǎo)致

區(qū)分Key與哈希值與索引與Value！！！

學(xué)著學(xué)著總把這三個搞混，Key是一個對象，對應(yīng)一個value，一個Key只能對應(yīng)一個哈希值和一個索引，而一個哈希值或一個索引可能對應(yīng)多個key和value，哈希值是哈希函數(shù)通過Key計算出來的值，盡力做到一個Key對應(yīng)一個哈希值，但依然有可能給多個Key計算出來哈希值一樣，而索引=哈希值%哈希表長度，也就是數(shù)組中的真實(shí)下標(biāo)。

總結(jié)

以上是生活随笔為你收集整理的2021-10-20 哈希表 恋上数据结构笔记的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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