哈希表（散列表）知识点概述
引言
在查找數(shù)據(jù)過程中，有很多種方法，但是大部分都是通過數(shù)據(jù)間的比較進(jìn)行的，有沒有一種方法可以直接通過關(guān)鍵字得到要查找的數(shù)據(jù)的位置的方法呢？這就需要用到一種新的查找方法，散列查找法；
基本思想
記錄存儲位置與關(guān)鍵字之間存在的對應(yīng)關(guān)系f，使得每個關(guān)鍵字key對應(yīng)一個存儲位置f(key)；
這里的對應(yīng)關(guān)系f就是散列函數(shù)，也稱為哈希函數(shù)；
所以哈希表定義也可以是
通過 關(guān)鍵字集合 由 哈希函數(shù) 推出 存儲地址集合；
而這些集合的存儲空間就是散列表（哈希表）；
散列技術(shù)既是一種存儲方法也是一種查找方法，它所記錄的數(shù)據(jù)之間不存在什么邏輯關(guān)系，只與關(guān)鍵字有關(guān)聯(lián)，所以可以說，散列表主要是面向查找的存儲結(jié)構(gòu)；
所以散列表查找就有一個很大的優(yōu)點(diǎn)：
查找速度極快，時間復(fù)雜度為O(1)，查找效率與元素個數(shù)無關(guān)；
相關(guān)術(shù)語
哈希函數(shù)（散列函數(shù)） ：在存儲位置p和其關(guān)鍵字key之間建立的一個確定的對應(yīng)關(guān)系f，使f(key) = p，則f為哈希函數(shù)，p為哈希地址；
哈希表 ：一個有限連續(xù) 的地址空間，用以存儲按哈希函數(shù)計算得到相應(yīng)哈希地址的數(shù)據(jù)記錄。
沖突 ：不同的關(guān)鍵字映射到同一個哈希地址，即key1 不等于key2，而f(key1) = f(key2)；
同義詞 ：具有相同函數(shù)值的兩個關(guān)鍵字，即key1和key2
哈希函數(shù)構(gòu)造方法
構(gòu)造前需要考慮的因素：
同時，一個好的哈希函數(shù)需要遵循以下兩個原則
1，計算簡單
每一個關(guān)鍵字只能有一個散列地址與之對應(yīng)（減少時間）
2，哈希地址分布均勻
函數(shù)的值域需要在表長范圍內(nèi)，這樣計算出來的哈希地址分布均勻，減少沖突（減少空間）
構(gòu)造哈希函數(shù)有好幾種方法，這里就介紹最關(guān)鍵的一個方法——除留余數(shù)法
這個方法是最常用的構(gòu)建哈希函數(shù)的方法，對于哈希表長為m的哈希函數(shù)公式為：
f(key) = key mod p (p <= m)
mod是取模，其實(shí)不僅可以對關(guān)鍵字取模，還可以在折疊平方中國取中后再取模，可以很直觀的看出，這個方法運(yùn)用的好壞全都取決于p的選取；
所以一般情況下，若哈希表長為m，通常p為小于或等于表長（最好接近m）的最大質(zhì)數(shù)；
處理沖突的方法
在哈希表的實(shí)際運(yùn)用中，很難避免不出現(xiàn)沖突，這時就需要有處理沖突的方法，處理方法和哈希表的本身組織形式有關(guān)，根據(jù)組織形式的同，通常分為兩大類，開放定址法和鏈地址法；
開放定址法
基本思想：有沖突時就去尋找下一個空的哈希地址，只要哈希表足夠大，空的哈希地址總能找到，并將數(shù)據(jù)元素存入；
f(key) = (f(key) + d) mod m (d = 1,2,3,4,5,……m-1)
f為哈希函數(shù)，m為哈希表表長，d為增量序列，由d的取值不同，可以分為下列3種探測方法
這里就不詳細(xì)介紹這三種方法了，可以自行查閱；
鏈地址法
基本思想：相同哈希地址的記錄連成一個單鏈表，m個哈希地址就設(shè)m個單鏈表，然后用一個數(shù)組將m個單鏈表的表頭指針存儲起來，形成一個動態(tài)的結(jié)構(gòu)；
即不同的key有相同的p，通過相同的p為表頭將這些key連接起來
這個方法很像圖中的 鄰接表 的使用方法，可以類比理解，這里的哈希地址可以類比為鄰接表里的頂點(diǎn)表，每個頂點(diǎn)相連的點(diǎn)就類似于哈希地址相同的關(guān)鍵字key；
這里就區(qū)別一下開放定址法和鏈地址法的特點(diǎn)
| 無指針域，存儲效率高 | 有指針域，存儲效率低 |
| 有二次聚集現(xiàn)象，查找效率低 | 無二次聚集現(xiàn)象，查找效率高 |
| 不易實(shí)現(xiàn)插入和刪除操作 | 易實(shí)現(xiàn)插入和刪除操作 |
| 表的大小固定，適用于表長無變化的情況 | 節(jié)點(diǎn)動態(tài)生成，始于表長經(jīng)常變化的情況 |
總結(jié)
這只是一些基本內(nèi)容，對于哈希表的代碼實(shí)現(xiàn)以后可能會補(bǔ)充，其實(shí)現(xiàn)在有很多造好的輪子可以使用，但是底層實(shí)現(xiàn)還是需要有了解的，這也是數(shù)據(jù)結(jié)構(gòu)這門課程的存在原因。
總結(jié)
以上是生活随笔為你收集整理的哈希表（散列表）知识点概述的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 135. 分发糖果（贪心算法）
- 下一篇： 435. 无重叠区间（贪心算法）