【算法學習】ELFhash算法

1.字元串哈希：

我們先從字元串哈希說起

在很多的情況下，我們有可能會獲得大量的字元串，每個字元串有可能重複也有可能不重複

C不像Python有字典類型的資料結構，我們沒有辦法吧字元串當做是鍵值來儲存，是以說我們需要一種hash函數将每個字元串都盡可能減少沖突的情況下去應設一個唯一的整形資料，友善我們的儲存，這裡我們就引入了字元串hash算法

現在，有非常多的字元串hash算法都很優秀，本文主要面對ELFhash算法來表述，相對來說比較的清晰

2.ELFhash

首先我需要聲明，字元串hash算法ELFhash的算法的形成的三列的均勻性我不會證明

根據其他的大牛的描述，ELFhash算法對于長字元串和短字元串都有優良的效率，以下的資料援引劉愛貴大神的實驗資料：

Hash應用中，字元串是最為常見的關鍵字，應用非常普通，現在的程式設計語言中基本上都提供了字元串hash表的支援。字元串hash函數非常多，常見的主要有Simple_hash, RS_hash, JS_hash, PJW_hash, ELF_hash, BKDR_hash, SDBM_hash, DJB_hash, AP_hash, CRC_hash等。它們的C語言實作見後面附錄代碼: hash.h, hash.c。那麼這麼些字元串hash函數，誰好熟非呢？評估hash函數優劣的基準主要有以下兩個名額：

(1) 散列分布性

即桶的使用率backet_usage = (已使用桶數) / (總的桶數)，這個比例越高，說明分布性良好，是好的hash設計。

(2) 平均桶長

即avg_backet_len，所有已使用桶的平均長度。理想狀态下這個值應該=1，越小說明沖突發生地越少，是好的hash設計。

hash函數計算一般都非常簡潔，是以在耗費計算時間複雜性方面判别甚微，這裡不作對比。

評估方案設計是這樣的：

(1) 以200M的視訊檔案作為輸入源，以4KB的塊為大小計算MD5值，并以此作為hash關鍵字;

(2) 分别應用上面提到的各種字元串hash函數，進行hash散列模拟；

(3) 統計結果，用散列分布性和平均桶長兩個名額進行評估分析。

Hash函數	桶數	Hash調用總數	最大桶長	平均桶長	桶使用率%
simple_hash	10240	47198	16	4.63	99.00%
RS_hash					98.91%
JS_hash			15	4.64	98.87%
PJW_hash
ELF_hash
BKDR_hash
SDBM_hash					98.90%
DJB_hash					98.85%
AP_hash					98.96%
CRC_hash					98.77%

是以實際應用中我們可以随便的選取，本文針對ELFhash

3.原理：

首先，我們在開始之前需要明确幾點

1.unsigned int有4個位元組，32個比特位

2.異或操作中0是機關元，任何數與1異或相當于取反

3.unsigned無符号類型的資料右移操作均是執行邏輯右移（左高位自動補0）

4.ELFhash算法的核心在于“影響“

先附上代碼：

[cpp]  view plain  copy

1. unsigned int ELFhash(char *str)  
2. {  
3.     unsigned int hash=0;  
4.     unsigned int x=0;  
5.     while(*str)  
6.     {  
7.         hash=(hash<<4)+*str;     //1  
8.         if((x=hash & 0xf0000000)!=0)         //2  
9.         {  
10.             hash^=(x>>24);   //影響5-8位，雜糅一次   3  
11.             hash&=~x;   //清空高四位    4  
12.         }  
13.         str++;   //5  
14.     }  
15.     return (hash & 0x7fffffff);    //6   
16. }  

解釋：

首先我們的hash結果是一個unsigned int類型的資料：

0000 0000 0000 0000

1.hash左移4位，将str插入（一個char有八位）這裡我開始也一直是懷疑的态度，那麼第一個位元組的高四位不就亂了嗎

實際上這也是我們的第一次雜糅，我們是故意這麼做的，這裡我們需要注意标記一下，我們在第一個位元組的高四位做了第一次雜糅

2.x這裡用0xf0000000擷取了hash的第四個位元組的高四位，并用高四位作為掩碼做第二次雜糅

在這裡我們首先聲明一下，因為我們的ELFhash強調的是每個字元都要對最後的結構有影響，是以說我們左移到一定程度是會吞掉最高的四位的，是以說我們要将最高的四位先對串産生影響，再讓他被吞掉，之後的所有的影響都是疊加的，這就是多次的雜糅保證散列均勻，防止出現沖突的大量出現

3.x掩碼右移24位移動到剛才的5-8位哪裡在對5-8位進行第二次雜糅

4.我們定時清空高四位，實際上這部操作我們完全沒有必要，但是算法要求，因為我們下一次的左移會自動吞掉這四位//這裡存疑，不會減少我們的hash的範圍？

5.str遞增，引入下一個字元進行雜糅

6.傳回一個缺失了最高符号位的無符号數（為了之後防止用到了有符号的時候造成的溢出）作為最後的hash值

4.Code:

1. /*#include"iostream" 
2. #include"cstdio" 
3. #include"cstring" 
4. using namespace std; 
5. unsigned int a=0x80; 
6. int main() 
7. { 
8.     printf("%d\n",a>>1);   //無符号數實行邏輯右移  
9.     return 0; 
10. } */  
11. #include"iostream"  
12. #include"cstdio"  
13. #include"cstring"  
14. using namespace std;  
21.         hash=(hash<<4)+*str;  
22.         if((x=hash & 0xf0000000)!=0)  
24.             hash^=(x>>24);   //影響5-8位，雜糅一次   
25.             hash&=~x;   //清空高四位   
27.         str++;  
29.     return (hash & 0x7fffffff);   
31. int main()  
33.     char data[100];  
34.     memset(data,0,sizeof(data));  
35.     scanf("%s",data);  
36.     printf("%d\n",ELFhash(data));  
37.     return 0;  
38. }   

最後，按照我的思路來看的話，ELFhash最多可以散列的空間的大小是幾個億的資料？如果去掉hash&=~x這一句的話會不會擴大我們hash的範圍，盡可能利用空間，我下星期問問資料結構老師好了！

5.應用：

我們在對記憶體位址的進行的操作的時候，可以将資料的記憶體位址進行哈希

因為每個資料的記憶體位址都是唯一的，是以我們隻需要一步擷取記憶體位址的十六進制的表示就可以了

語句是

1. sprintf(data,"%0x",&now_data);  

第一個data儲存我們的保留字元串的記憶體空間（字元串數組）

中間的是儲存的進制的形式

最後是我們的要取位址的記憶體空間

利用這種思路，我們可以很清晰明了的對連結清單相交的問題建構一種新的解法，我們采用哈希我們的記憶體空間就可以了，可以再O(n)中完成查找