2018-11-01

散列表---哈希表
基于快速存取，時間換空間
一種基于線性數(shù)組的線性表，不過元素之間并非緊密排列

散列函數(shù)--通過函數(shù)，有key關鍵碼計算地址（相當于數(shù)組下標）,函數(shù)盡可能使元素均勻分布

負載因子a：實際元素只有 n 個時，我們?yōu)槠渖暾埩?m 個元素空間（m>n），即桶的個數(shù)；
負載因子 = n/m
a > 1 碰撞頻率大
a < 1 碰撞頻率小
同義詞（synonym）：如果兩個元組通過hash函數(shù)計算得到的地址相同《沖突》，那么這兩個元素就叫做synonym

桶（bucket）：散列函數(shù)計算所得到的存儲單位，每個單位稱為一個桶，如果一個散列表有m個桶，那么散列函數(shù)的值域
為[0,m-1]

沖突主要取決于：
1.散列函數(shù)，（均勻度）
2.處理沖突的方法
3.負載因子大小（過大：浪費空間，過小，時間問題），負載因子也散列函數(shù)是聯(lián)動的

hash function:
1.取余法：
H( Key ) = Key % M
其中 ：M <= 基本區(qū)長度的最大質數(shù)(在各種進制下都必須要滿足)
即要保證一個桶不能是另一個桶的倍數(shù)
基本區(qū)長 M
8 7
16 13
2048 2039
為什么取最大質數(shù)？
1) 若取偶數(shù)，如 10，100，…., 2, 4, …, 沖突率是比較大的；
2）若取含有質因子的M，如 M=21 （3*7） 含質因子3和7，對下面的例子：
key: 28 35 63 77 105
則 7 14 0 14 0 關鍵碼中含質因子7的哈希值均為7的倍數(shù)。
2.平方取中法
H( Key ) = Key^2 的中間部分，其長度取決于表的大小。
設表長 = 2^9 = (512)10 地址 000~777(八進制）
(2061)8 4310541
(2062)8 4314704
(2161)8 4734741
(2162)8 4741304
(1100)8 1210000
3. 乘法雜湊函數(shù)
H( Key ) = |_ M * (( r * Key ) % 1 ) _| (向下取整)
例：設表長 = 29 = (512)10 地址 000~777(八進制），則
H( 1 ) = ?29 * ( 0.618 )10 ? = ? 29 * ( 0.4743…)8 ? = 474

4.直接尋址法：取關鍵字或關鍵字的某個線性函數(shù)值為散列地址。即H(key)=key或H(key) = a?key + b，其中a和b為常數(shù)（這種散列函數(shù)叫做自身函數(shù)）

5. 數(shù)字分析法：分析一組數(shù)據(jù)，比如一組員工的出生年月日，這時我們發(fā)現(xiàn)出生年月日的前幾位數(shù)字大體相 同，這
樣的話，出現(xiàn)沖突的幾率就會很大，但是我們發(fā)現(xiàn)年月日的后幾位表示月份和具體日期的數(shù)字差別很大，如果用
后面的數(shù)字來構成散列地址，則沖突的幾率會 明顯降低。因此數(shù)字分析法就是找出數(shù)字的規(guī)律，盡可能利用這些
數(shù)據(jù)來構造沖突幾率較低的散列地址。
注意：數(shù)值分析法僅適用于事先知道表中所有關鍵瑪?shù)拿恳晃坏姆植记闆r，完全依賴于關鍵碼的集合

設有 n 個d位數(shù)。每一位可能有 r 種不同的符號，這r為符號在某些位上分布均勻些，分布不均勻的不經常出現(xiàn)，
可以根據(jù)散列表，只選取其中的若干位作為散列地址，
計算各位數(shù)字中符號分布的均勻度 T 的公式

T = sum(a(ik) - n/r )^2
a(ik)表示第i位符號在k中出現(xiàn)的次數(shù)

6.折疊法：將關鍵字分割成位數(shù)相同的幾部分，最后一部分位數(shù)可以不同，然后取這幾部分的疊加和（去除進位）作為散列地址。
注意：
1.適用條件：
當關鍵碼的位數(shù)很多，而且關鍵碼上的數(shù)字的分布大致均勻時
2.疊加時舍去多余的位數(shù)
疊加方法：
1.移位法： 普通的加法
2.分界法

7. 隨機數(shù)法：選擇一隨機函數(shù)，取關鍵字的隨機值作為散列地址，通常用于關鍵字長度不同的場合。


散列表的查找過程基本上和造表過程相同。一些關鍵碼可通過散列函數(shù)轉換的地址直接找到，另一些關鍵碼在散列函數(shù)得到的地址上產生了沖突，需要按 處理沖突的方法進行查找。在介紹的三種處理沖突的方法中，產生沖突后的查找仍然是給定值與關鍵碼進行比較的過程。所以，對散列表查找效率的量度，依然用平 均查找長度來衡量。
查找過程中，關鍵碼的比較次數(shù)，取決于產生沖突的多少，產生的沖突少，查找效率就高，產生的沖突多，查找效率就低。因此，影響產生沖突多少的因素，也就是影響查找效率的因素。影響產生沖突多少有以下三個因素：
　　1. 散列函數(shù)是否均勻；
　　2. 處理沖突的方法；
　　3. 散列表的裝填因子。
　　散列表的裝填因子定義為：α= 填入表中的元素個數(shù) / 散列表的長度
　　α是散列表裝滿程度的標志因子。由于表長是定值，α與“填入表中的元素個數(shù)”成正比，所以，α越大，填入表中的元素較多，產生沖突的可能性就越大；α越小，填入表中的元素較少，產生沖突的可能性就越小。
　　實際上，散列表的平均查找長度是裝填因子α的函數(shù)，只是不同處理沖突的方法有不同的函數(shù)。

著名的hash算法：MD5 和 SHA-1 可以說是目前應用最廣泛的Hash算法，而它們都是以 MD4 為基礎設計的
hash在信息安全：文件校驗、數(shù)字簽名、授權協(xié)議




關于查找不成功：
address 0 1 2 3 4 5 6 7 8 9
key 7 14 8 11 30 18 9
查找不成功，說明要查找的數(shù)字肯定不在上述的散列表中。
因為這里哈希函數(shù)的模為7，所以要查找的數(shù)只可能位于0~6的位置上。
（1）若要查找的數(shù)key對應的地址為0，有(key * 3) % 7 = 0。
因為key不屬于{7, 8, 30, 11, 18, 9, 14}，可設key = 28。
第一次查找，address = 0時key = 7，不是要找的28，
第二次查找，往后挪移一位，address = 1時key = 14，不是要找的28；
第三次查找，往后再挪移一位，address = 2時key為空?？芍檎也怀晒?#xff0c;否則28應該放在adress = 2的位置上。
結論：查找3次可知查找不成功。
---------------------


解決沖突的方式：

閉散列方法(開地址法)：
1.線性探查法 linear probing
Hi = (H0+i)%m
缺點：1.閉散列的情形下不能物理刪除表中已有的元素
2.僅適用于散列表不經常變化
3.線性探查法容易產生堆積cluster（不同的探查序列的關鍵碼占據(jù)了可利用的bullet，使得為了尋找某一關鍵碼需要經歷不同的探查序列的元素，導致搜索時間增加
2.二次探查法 quadratic probing
Hi = (H0 +/- i^2 )%m
優(yōu)點：當表的長度為質數(shù)且負載因子 不超過 0.5 時，新的表項一定能夠插入，而且任何一個位置不會被探查兩次
3.雙散列方法：
兩個散列函數(shù)，hash（）計算第一次的地址 ， rehash()是在發(fā)生沖突時用于計算下一個空桶所在的 位移量。
于是，它解決了線性探查的堆積問題，
Hi = (H0 +i*rehash(key))%m;

開散列方法（鏈地址法）：
將根據(jù)散列表函數(shù)計算的地址將其分為m個子集合，同一詞位于相同的子集合中，每一個子集合稱為一個桶
采用的是鏈表實現(xiàn)
優(yōu)點：速度快


性能分析：
開散列方法 優(yōu)于 閉散列
hash：
取余法最好，折疊法最差

散列表有很好的平衡性能，優(yōu)于如平衡樹的傳統(tǒng)技術，但是在最壞的情況下性能不好，執(zhí)行插入/搜索
在最壞情況下是 O(n)；

轉載于:https://www.cnblogs.com/XT-xutao/p/9890257.html

總結

以上是生活随笔為你收集整理的hashtable——散列表的全部內容，希望文章能夠幫你解決所遇到的問題。

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