文章目錄
- 相關概念介紹
- 一、直接尋址法
- 二、數字分析法
- 三、折疊法
- 四、平方取中法
- 五、除留余數法
- 六、亂數法
相關概念介紹
- 哈希:
Hash，一般翻譯做散列、雜湊，或音譯為哈希，是把任意長度的輸入（又叫通過散列演算法變換成固定長度的輸出，該輸出就是散列值，這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小于輸入的空間，不同的輸入可能會散列成相同的輸出，所以不可能從散列值來確定唯一的輸入值，簡單的說就是一種將任意長度的訊息壓縮到某一固定長度的訊息摘要的函式， - 散串列:
散串列（Hash table，也叫哈希表），是根據關鍵碼值(Key value)而直接進行訪問的資料結構，也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度，這個映射函式叫做散列函式，存放記錄的陣列叫做散串列， - 哈希沖突:
由于哈希演算法被計算的資料是無限的，而計算后的結果范圍有限，因此總會存在不同的資料經過計算后得到的值相同，這就是哈希沖突，
一、直接尋址法
- 介紹:取關鍵字或關鍵字的某個線性函式值為散列地址，即H(key)=key或者H(key)=a*key+b（a,b為常數），
- 舉例:[‘A’,‘B’,‘D’,‘A’,‘C’,‘E’,‘F’,‘C’] ,求該字符陣列里每個字符的出現次數(陣列中只有大寫字母)，
- 分析:我們可以知道’A’-'Z’的ASCLL碼是65-90,則哈希函式可以通過直接尋址法H(key)=key-‘A’（對應定義中的a=1,b=-‘A’即65）,這樣針對每一個key,都可以將它的H(key)值當成陣列下標放在一個長度為26的int陣列中統計長度
假設字符陣列為a,int陣列為b，即b[a[i]-‘A’]++(i表示a陣列的下標索引)， - 結果
b[0]=2(代表A出現兩次)；b[1]=1(代表B出現一次)，b[2]=2(代表C出現兩次)…
二、數字分析法
- 介紹:分析一組資料中相同位(個位,十位,百位…)的數字出現頻率，如果該位數字出現結果較為集中，如果取其作為構造散列地址的依據則很容易出現哈希沖突,反之，如果該位數字出現結果較為平均,則取其作為構造散列地址的依據則不容易出現哈希沖突，
- 舉例:某公司招聘了一些實習生,其生日分別為[19990104,20000910,20000315,20001128,20001014,19990413,19990920,20000517],對其進行hash處理，
- 分析
如果取8位數作為散列地址,雖然很難出現哈希沖突,但是空間浪費很大，因此考慮只取其中幾位作為散列地址,即能減少空間浪費又能降低哈希沖突的可能性,觀察上面8組資料，前4位集中在1999,2000，如果取前4位則很容易出現哈希沖突，而后四位分布相對分散，不容易出現哈希沖突，因此取后四位比較符合， - 結果
H(19990104)=104,H(20000910)=910,H(20000315)=315…
三、折疊法
- 介紹:折疊法是把關鍵字值自左向右分成位數相等的幾部分，每一部分的位數應與散串列地址的位數相同，只有最后一部分的位數可以短一些，把這些部分的資料疊加起來（去除進位），就可以得到關鍵字值的散列地址，
有兩種疊加方法：
(1)移位法(shift floding)：把各部分的最后一位對齊相加，
(2)分界法(floding at the boudaries)：沿各部分的分界來回折疊，然后對其相加， - 舉例:key=1234791，散列地址為2位
- 分析
將key分成12,34,79,1四部分
(1)移位法:12+34+79+1
(2)分界法:12+43+79+1(即第偶數個加數和移位法反過來) - 結果
(1)移位法:H(1234791)=35(相加為135，去除進位1)
(2)分界法:H(1234791)=44(相加為144，去除進位1)
四、平方取中法
- 介紹：當無法確定關鍵字中哪幾位分布較均為時，可以求出關鍵字的平方值，然后按需要取平方值的中間幾位作為散列地址，這是因為:平方后中間幾位和關鍵字中每一位都有關，故不同關鍵字會以較高的概率產生不同的散列地址，
- 舉例:關鍵字序列:{3213,3113,3212,4312}，
- 分析:
3213^2=10323369
3113^2=9690769
3212^2=10316944
4312^2=18593344
取平方值中間4位為散列地址(3113的平方值前面補0湊成8位) - 結果
H(3213)=3233,H(3113)=6907,H(3212)=3169,H(4312)=5933
五、除留余數法
- 介紹:取關鍵字被某個不大于散串列表長m的數p除后的余數作為散列地址，即H(key)=key mod p(p<=m),該方法不僅可以直接對關鍵字取模,還可以在折疊,平方取中等方法后再取模，注意:p的選擇很重要，一般選取滿足條件(即p<=m)的最大質數或者m,如果取的不好容易產生哈希沖突，
- 舉例:關鍵字序列:{16，11，19，23，2，6，10},散串列表長為11，
- 分析
該散串列表長剛好為質數，直接選擇p=11 - 結果：
H(16)=5, H(11)=0, H(19)=8, H(23)=1, H(2)=2, H(6)=6, H(10)=10
六、亂數法
- 介紹:選擇一隨機函式，取關鍵字作為隨機函式的種子,生成隨機值作為散列地址，即H(key)=random (key)，其中random為隨機函式，通常用于關鍵字長度不同的場合，
- 舉例:key=123,隨機函式為每位數字平方后連續相乘，
- 分析
隨機函式的選擇對于哈希沖突的概率很重要,這里只是簡單的選擇一個函式 - 結果
H(123)=36
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/262979.html
標籤：區塊鏈
上一篇：go反射獲取型別物件與值、go反射獲取指標名稱和型別、golang反射物件的空值處理、golang反射值物件修改變數的值