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