建站
咨詢
售后
建站咨詢
新聞中心
隨著互聯(lián)網(wǎng)和大數(shù)據(jù)時代的來臨，數(shù)據(jù)庫管理系統(tǒng)（DBMS）越來越受到重視。哈希表在DBMS中得到了廣泛應(yīng)用，它可以快速地執(zhí)行插入、刪除、查找等操作，使數(shù)據(jù)的訪問速度得到了極大的提升。但是，哈希表在大量數(shù)據(jù)存儲的情況下，存在哈希碰撞的問題。本文將介紹。
創(chuàng)新互聯(lián)公司-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價比潼南網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式潼南網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋潼南地區(qū)。費用合理售后完善，十多年實體公司更值得信賴。
一、哈希碰撞的原因
哈希碰撞是指當(dāng)哈希函數(shù)將多個不同的數(shù)據(jù)映射到同一個哈希值時，就會發(fā)生哈希碰撞。哈希函數(shù)的好壞決定了哈希碰撞的概率大小。以下是幾種常見的哈希碰撞的原因：
1. 哈希函數(shù)的設(shè)計不合理：設(shè)計哈希函數(shù)時，我們需要考慮到哈希值的分布要盡量均勻。如果哈希函數(shù)存在很多沖突，那么查詢數(shù)據(jù)的速度就會變慢。一些常用的哈希函數(shù)，如MD5和SHA，就存在碰撞的風(fēng)險。
2. 數(shù)據(jù)輸入的相關(guān)性：如果輸入的數(shù)據(jù)存在相關(guān)性，即它們的哈希值可能互相碰撞，那么就有可能出現(xiàn)哈希碰撞。例如，如果我們將所有的姓名首字母作為哈希值，那么姓氏相同的人就會產(chǎn)生碰撞。
3. 哈希表容量不足：如果哈希表的容量太小，就會導(dǎo)致哈希碰撞的概率大大增加。當(dāng)哈希表中的元素數(shù)量達(dá)到哈希表容量的70%時，就需要重新調(diào)整哈希表容量，以減少哈希碰撞的發(fā)生。
二、哈希碰撞的解決方法
1. 更好的哈希函數(shù)：我們可以設(shè)計更好的哈希函數(shù)，以減少哈希碰撞的概率。哈希函數(shù)的設(shè)計可以考慮到輸入數(shù)據(jù)的分布情況、哈希表容量的大小以及數(shù)據(jù)輸入的相關(guān)性等多個因素。
2. 哈希表的優(yōu)化：我們可以優(yōu)化哈希表的容量，以降低哈希碰撞的發(fā)生率。通常情況下，哈希表的容量應(yīng)該為元素數(shù)量的兩倍，以保證哈希表中的元素的分布情況盡量均勻。
3. 開放尋址法和鏈?zhǔn)椒ǎ洪_放尋址法和鏈?zhǔn)椒ㄊ枪１碇袃煞N常用的解決哈希碰撞的方法。開放尋址法是指在哈希碰撞時，將數(shù)據(jù)插入到下一個空閑的位置，而鏈?zhǔn)椒ㄊ菍⒐Ｅ鲎驳脑亟M成一個鏈表進(jìn)行存儲。開放尋址法在內(nèi)存中的利用率更高，而鏈?zhǔn)椒ǜ屿`活，可以適應(yīng)不同規(guī)模的數(shù)據(jù)表。
4. 拉鏈法：拉鏈法是一種常用的解決哈希碰撞的方法。在拉鏈法中，每個哈希槽位都是一個鏈表，存儲哈希碰撞的元素。當(dāng)需要查詢或刪除某個元素時，首先需遍歷哈希槽位的鏈表，然后在其中查找或刪除指定的元素。拉鏈法的優(yōu)點是易于實現(xiàn)和維護(hù)，同時也穩(wěn)定且效率高。
數(shù)據(jù)庫哈希碰撞是DBMS中常見的問題之一，但是只要我們設(shè)計合理的哈希函數(shù)和優(yōu)化哈希表容量，結(jié)合使用開放尋址法、鏈?zhǔn)椒ê屠湻ǖ冉鉀Q哈希碰撞的方法，我們就可以有效地提高數(shù)據(jù)庫的性能和安全性。
相關(guān)問題拓展閱讀：
- HashMap實現(xiàn)原理
- 如果redis中放入多個數(shù)據(jù)庫表，怎么區(qū)分
HashMap實現(xiàn)原理
HashMap在實際開發(fā)中用到的頻率非常高，面試中也是熱點。所以決定寫一篇文章進(jìn)行分析，希望對想看源碼的人起到一些幫助，看之前需要對鏈表比較熟悉。
以下都是我自己的理解，歡迎討論，寫的不好輕噴。
HashMap中的數(shù)據(jù)結(jié)構(gòu)為散列表，又名哈希表。在這里我會對核彎散列表進(jìn)行一個簡單的介紹，在此之前我們需要先回顧一下
數(shù)組
、
鏈表
的優(yōu)缺點。
數(shù)組和鏈表的優(yōu)缺點取決于他們各自在內(nèi)存中存儲的模式，也就是直接使用
順序存儲
或
鏈?zhǔn)酱鎯?/p>
導(dǎo)致的。無論是數(shù)組還是鏈表，都有明顯的缺點。而在實際業(yè)務(wù)中，我們想要的往往是尋址、刪除、插入性能都很好的數(shù)據(jù)結(jié)構(gòu)，散列表就是這樣一種結(jié)構(gòu)，它巧妙的結(jié)合了數(shù)組與鏈表的優(yōu)點，并將其缺點弱化（并不是完全消除）
散列表的做法是將key映射到數(shù)組的某個下標(biāo)，存取的時候通過key獲取到下標(biāo)（index）然后通過下標(biāo)直接存取。速度極快，而將key映射到下標(biāo)需要使用
散列函數(shù)
，又名
哈希函數(shù)
。說到哈希函數(shù)可能有人已經(jīng)想到了，如何將key映射到數(shù)組的下標(biāo)。
圖中計算下標(biāo)使用到了以下兩個函數(shù)：
值得注意的是，下標(biāo)并不是通過hash函數(shù)直接得到的，計算下標(biāo)還要對hash值做index()處理。
Ps：在散列表中，數(shù)組的格子叫做
桶
，下標(biāo)叫做
桶號
，桶可以包含一個key-value對，為了方便理解，后文不會使用這兩個名詞。
以下是哈希碰撞相關(guān)的說明：
以下是下標(biāo)沖突相關(guān)的說明：
很多人認(rèn)為哈希值的碰撞和下標(biāo)沖突是同一個東西，其實不是的，它們的正確關(guān)系是這樣的，
hashCode發(fā)生碰撞，則下標(biāo)一定沖突；而下標(biāo)沖突，hashCode并不一定碰撞
上文提到，在jdk1.8以前HashMap的實現(xiàn)是
散列表 = 數(shù)組 + 鏈表
，但是到目前為止我們還沒有看到鏈表起到的作用。事實上，HashMap引入鏈表的用意就是解決下標(biāo)沖突。
下圖是引入鏈表后的散列表：
如上圖所示，左邊的豎條，是一個大小為16的數(shù)組，其中存儲的是鏈表的頭結(jié)點，我們知道，擁有鏈表的頭結(jié)點即可訪問整個鏈表，所以認(rèn)為這個數(shù)組中的每個下標(biāo)都存儲著一個鏈表。其具體做法是，如果發(fā)現(xiàn)下標(biāo)沖突，則
后插入的節(jié)點以鏈表的形式追加到前一個節(jié)點的后面
。
這種使用鏈表解決沖突的方法叫做：
拉鏈法
（又叫鏈地址法）。HashMap使用的就是拉鏈法，拉鏈法是沖突發(fā)生以后的解決方案。
Q：有了拉鏈法，就不用擔(dān)心發(fā)生沖突嗎？
A：并不是！由于沖突的節(jié)點會不停的在鏈表上追加，大量的沖突會導(dǎo)致單個鏈表過長，使查詢性能降低。所以一個好的散列表的實現(xiàn)應(yīng)該從源頭上減少沖突發(fā)生的可能性，沖突發(fā)生的概率和哈希函數(shù)返回值的均勻程度有直接關(guān)系，得到的哈希值越均勻，沖突發(fā)生的可能性越小。為了使哈希值更均勻，HashMap內(nèi)部單獨實現(xiàn)了hash()方法。
以上是散列表的存儲結(jié)構(gòu)，但是在被運用到HashMap中時還有其他需要注意的地方，這里會詳細(xì)說明。
現(xiàn)在我們清楚了散列表的存儲結(jié)構(gòu)，細(xì)心的人應(yīng)該已經(jīng)發(fā)現(xiàn)了一個問題：Java中數(shù)組的長度是固定的，
無論哈希函數(shù)是否均勻，隨著插入到散列表中數(shù)據(jù)的增多，在數(shù)組長度不變的情況下，鏈表的長度會不斷增加
。這會導(dǎo)致鏈表查詢性能不佳的缺點出現(xiàn)在散列表上，從而使散列表失去原本的意義。為了解決這個問題，HashMap引入了擴(kuò)容與負(fù)載因子。
以下改虧悶是和擴(kuò)容相關(guān)的一些概念和解釋：
Ps：
擴(kuò)容要重新計算下標(biāo)
，
擴(kuò)容要重新計算下標(biāo)
，
擴(kuò)容要重新計算下標(biāo)
，因為下標(biāo)空純的計算和數(shù)組長度有關(guān)，長度改變，下標(biāo)也應(yīng)當(dāng)重新計算。
在1.8及其以上的jdk版本中，HashMap又引入了紅黑樹。
紅黑樹的引入被用于替換鏈表，上文說到，如果沖突過多，會導(dǎo)致鏈表過長，降低查詢性能，均勻的hash函數(shù)能有效的緩解沖突過多，但是并不能完全避免。所以HashMap加入了另一種解決方案，在往鏈表后追加節(jié)點時，如果發(fā)現(xiàn)鏈表長度達(dá)到8，就會將鏈表轉(zhuǎn)為紅黑樹，以此提升查詢的性能。
如果redis中放入多個數(shù)據(jù)庫表，怎么區(qū)分
1、redis
中的每一個數(shù)據(jù)庫，都由一個
redisDb
的結(jié)構(gòu)存儲。其中畝握，redisDb.id
存儲著
redis
數(shù)據(jù)庫以整數(shù)表示的號碼。redisDb.dict
存儲著該庫所有的鍵值對數(shù)據(jù)。redisDb.expires
保存著每一個鍵的過期或耐鬧時間。
2、當(dāng)redis
服務(wù)器初始化時，會預(yù)先分配
個數(shù)據(jù)庫衫罩（該數(shù)量可以通過
配置文件
配置），所有數(shù)據(jù)庫保存到結(jié)構(gòu)
redisServer
的一個成員
redisServer.db
數(shù)組中。當(dāng)我們選擇數(shù)據(jù)庫
select
number
時，程序直接通過
redisServer.db
來切換數(shù)據(jù)庫。有時候當(dāng)程序需要知道自己是在哪個數(shù)據(jù)庫時，直接讀取
redisDb.id
即可。
1、redis
中的每一個數(shù)據(jù)庫，都由一個
redisdb
的結(jié)構(gòu)存儲。其中，redisdb.id
存儲著
redis
數(shù)據(jù)庫以整數(shù)表示的號碼。redisdb.dict
存儲著該庫所有的鍵值對數(shù)據(jù)。redisdb.expires
保存著每一個鍵的過期時間。
2、當(dāng)redis
服務(wù)器初始化時，會預(yù)先分配
個數(shù)據(jù)庫（該數(shù)量可以通過配置文件配置），所有數(shù)據(jù)庫保存到結(jié)構(gòu)
redisserver
的一個成員
redisserver.db
數(shù)組中。當(dāng)我們選擇數(shù)據(jù)庫
select
number
時，程序直接通過
redisserver.db
來切換數(shù)據(jù)庫。有時候當(dāng)程序需要知道自己是在哪個數(shù)據(jù)庫時，直接讀取
redisdb.id
即可。
3、既然我們知道一個數(shù)據(jù)庫的所有鍵值都存儲在redisdb.dict中，那么我們要知道如果找到key的位置，就有必要了解一下dict
的結(jié)構(gòu)了：
typedef
struct
dict
{
//
特定于類型的處理函數(shù)
dicttype
*type;
//
類芹沒型處理函數(shù)的私有數(shù)據(jù)
void
*privdata;
//
哈希表（2個）
dictht
ht;
//
記錄
rehash
進(jìn)度的標(biāo)志，值為-1
表示
rehash
未進(jìn)行
int
rehashidx;
//
當(dāng)前正在運作的安全迭代器數(shù)量
int
iterators;
}
dict;
由上述的結(jié)構(gòu)可以看出，redis
的字典使用哈希表作為其底層實現(xiàn)。dict
類型使用的兩個指向哈希表的指針，其中
號哈希表（ht）主要用于存儲數(shù)據(jù)庫的所有鍵值，而1號哈希表主要用于程序?qū)?/p>
號哈希表進(jìn)行
rehash
時使用，rehash
一般是在添加新值時會觸發(fā)，這里不做過多的贅述。所以redis
中查找一個key，其實就是對進(jìn)行該dict
結(jié)構(gòu)中的
ht
進(jìn)行查找操作。
4、既然是哈希，那么我們知道就會有哈希碰撞，那么當(dāng)多個鍵哈希之后為同一個值怎么辦呢？redis采取鏈表的方式來存儲多個哈希碰撞的鍵。也就是說，當(dāng)根據(jù)key的哈希值找到該列表后，如果列表的長度大于1，那么我們需要遍歷該鏈表來找到我們所查找的key。當(dāng)然，一般情況下鏈表長度都為是1，所以時間復(fù)雜度可看作o(1)。
二、當(dāng)redis
拿到一個key
時，如果找到該key的位置。
了解了上述知識之后，我們就可以來分析redis如果在內(nèi)存找到一個key了。
1、當(dāng)舉首返拿到一個key后，
redis
先判斷當(dāng)前庫的0號哈希表是否為空，即：if
(dict->ht.size
==
0)。如果為true直接返回null。
2、判斷該0號哈希表是否需要rehash，因為如果在進(jìn)行rehash，那么兩個表中者有可能存正饑儲該key。如果正在進(jìn)行rehash，將調(diào)用一次_dictrehashstep方法，_dictrehashstep
用于對數(shù)據(jù)庫字典、以及哈希鍵的字典進(jìn)行被動
rehash，這里不作贅述。
3、計算哈希表，根據(jù)當(dāng)前字典與key進(jìn)行哈希值的計算。
4、根據(jù)哈希值與當(dāng)前字典計算哈希表的索引值。
5、根據(jù)索引值在哈希表中取出鏈表，遍歷該鏈表找到key的位置。一般情況，該鏈表長度為1。
6、當(dāng)
ht
查找完了之后，再進(jìn)行了次rehash判斷，如果未在rehashing，則直接結(jié)束，否則對ht重復(fù)345步驟。
關(guān)于數(shù)據(jù)庫 哈希碰撞的介紹到此就結(jié)束了，不知道你從中找到你需要的信息了嗎 ？如果你還想了解更多這方面的信息，記得收藏關(guān)注本站。
香港服務(wù)器選創(chuàng)新互聯(lián)，2H2G首月10元開通。
創(chuàng)新互聯(lián)（www.cdcxhl.com）互聯(lián)網(wǎng)服務(wù)提供商,擁有超過10年的服務(wù)器租用、服務(wù)器托管、云服務(wù)器、虛擬主機(jī)、網(wǎng)站系統(tǒng)開發(fā)經(jīng)驗。專業(yè)提供云主機(jī)、虛擬主機(jī)、域名注冊、VPS主機(jī)、云服務(wù)器、香港云服務(wù)器、免備案服務(wù)器等。
網(wǎng)站欄目：數(shù)據(jù)庫哈希碰撞的原因及解決方法(數(shù)據(jù)庫哈希碰撞)
URL網(wǎng)址：http://www.dlmjj.cn/article/dpejeph.html
