ELFhash

字符串哈希算法（以ELFHash詳解）

?

更多字符串哈希算法請參考：http://blog.csdn.net/AlburtHoffman/article/details/19641123

先來了解一下何為哈希：

哈希表是根據設定的哈希函數H(key)和處理沖突方法將一組關鍵字映射到一個有限的地址區間上，并以關鍵字在地址區間中的象作為記錄在表中的存儲位置，這種表稱為哈希表或散列，所得存儲位置稱為哈希地址或散列地址。作為線性數據結構與表格和隊列等相比，哈希表無疑是查找速度比較快的一種。

通過將單向數學函數（有時稱為“哈希算法”）應用到任意數量的數據所得到的固定大小的結果。如果輸入數據中有變化，則哈希也會發生變化。哈希可用于許多操作，包括身份驗證和數字簽名。也稱為“消息摘要”。

?

簡單解釋：哈希(Hash)算法,即散列函數。它是一種單向密碼體制,即它是一個從明文到密文的不可逆的映射,只有加密過程,沒有解密過程。同時,哈希函數可以將任意長度的輸入經過變化以后得到固定長度的輸出。哈希函數的這種單向特征和輸出數據長度固定的特征使得它可以生成消息或者數據。

?

個人心得：哈希就是用進行函數映射，用key對應此時的值，然后對這個值進行查詢時直接對key的地址進行查看就好了，思想簡單，用起來真的復雜。我們還是簡單學一下ELFHash吧

// ELF Hash Function2 unsigned int ELFHash(char *str)3 {4     unsigned int hash = 0;5     unsigned int x = 0;6 7     while (*str)8     {9         hash = (hash << 4) + (*str++);//hash左移4位，把當前字符ASCII存入hash低四位。 
10         if ((x = hash & 0xF0000000L) != 0)
11         {
12             //如果最高的四位不為0，則說明字符多余7個，現在正在存第7個字符，如果不處理，再加下一個字符時，第一個字符會被移出，因此要有如下處理。
13             //該處理，如果最高位為0，就會僅僅影響5-8位，否則會影響5-31位，因為C語言使用的算數移位
14             //因為1-4位剛剛存儲了新加入到字符，所以不能>>28
15             hash ^= (x >> 24);
16             //上面這行代碼并不會對X有影響，本身X和hash的高4位相同，下面這行代碼&~即對28-31(高4位)位清零。
17             hash &= ~x;
18         }
19     }
20     //返回一個符號位為0的數，即丟棄最高位，以免函數外產生影響。(我們可以考慮，如果只有字符，符號位不可能為負)
21     return (hash & 0x7FFFFFFF);
22 }

然后用一個例題實踐一下吧吧，hdu1800

#include <bits/stdc++.h>
using namespace std;typedef unsigned int ui;
const int N = 7003, MOD = 7003;
int Hash[N], num[N];
int res;
int ELFhash(char *str)//思想就是一直雜糅，使字符之間互相影響
{ui h = 0, g;while(*str){h = (h<<4) + *str++; //h左移4位，當前字符占8位，加到h中進行雜糅if((g = h & 0xf0000000) != 0) //取h最左四位的值，若均為0，則括號中執行與否沒區別，故不執行{h ^= g>>24; //用h的最左四位的值對h的右起5~8進行雜糅h &= ~g;//清空h的最左四位}}return h; //因為每次都清空了最左四位，最后結果最多也就是28位二進制整數，不會超int
}
void hash_table(char *str)
{int k = ELFhash(str);int t = k % MOD;while(Hash[t] != k && Hash[t] != -1) t = (t + 1) % MOD;//開放地址法處理hashif(Hash[t] == -1) num[t] = 1, Hash[t] = k;else res = max(res, ++num[t]);
}
int main()
{int n;char str[100];while(~ scanf("%d", &n)){getchar();res = 1;memset(Hash, -1, sizeof Hash);for(int i = 1; i <= n; i++){scanf("%s", str);int j = 0;while(str[j] == '0') j++;hash_table(str + j);}printf("%d\n", res);}return 0;
}