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

?

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

先來了解一下何為哈希：

哈希表是根據(jù)設(shè)定的哈希函數(shù)H(key)和處理沖突方法將一組關(guān)鍵字映射到一個(gè)有限的地址區(qū)間上，并以關(guān)鍵字在地址區(qū)間中的象作為記錄在表中的存儲(chǔ)位置，這種表稱為哈希表或散列，所得存儲(chǔ)位置稱為哈希地址或散列地址。作為線性數(shù)據(jù)結(jié)構(gòu)與表格和隊(duì)列等相比，哈希表無疑是查找速度比較快的一種。 通過將單向數(shù)學(xué)函數(shù)（有時(shí)稱為“哈希算法”）應(yīng)用到任意數(shù)量的數(shù)據(jù)所得到的固定大小的結(jié)果。如果輸入數(shù)據(jù)中有變化，則哈希也會(huì)發(fā)生變化。哈希可用于許多操作，包括身份驗(yàn)證和數(shù)字簽名。也稱為“消息摘要”。 ? 簡(jiǎn)單解釋：哈希(Hash)算法,即散列函數(shù)。它是一種單向密碼體制,即它是一個(gè)從明文到密文的不可逆的映射,只有加密過程,沒有解密過程。同時(shí),哈希函數(shù)可以將任意長(zhǎng)度的輸入經(jīng)過變化以后得到固定長(zhǎng)度的輸出。哈希函數(shù)的這種單向特征和輸出數(shù)據(jù)長(zhǎng)度固定的特征使得它可以生成消息或者數(shù)據(jù)。 ? 個(gè)人心得：哈希就是用進(jìn)行函數(shù)映射，用key對(duì)應(yīng)此時(shí)的值，然后對(duì)這個(gè)值進(jìn)行查詢時(shí)直接對(duì)key的地址進(jìn)行查看就好了，思想簡(jiǎn)單，用起來真的復(fù)雜。我們還是簡(jiǎn)單學(xué)一下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位，把當(dāng)前字符ASCII存入hash低四位。 10 if ((x = hash & 0xF0000000L) != 0) 11 { 12 //如果最高的四位不為0，則說明字符多余7個(gè)，現(xiàn)在正在存第7個(gè)字符，如果不處理，再加下一個(gè)字符時(shí)，第一個(gè)字符會(huì)被移出，因此要有如下處理。 13 //該處理，如果最高位為0，就會(huì)僅僅影響5-8位，否則會(huì)影響5-31位，因?yàn)镃語言使用的算數(shù)移位 14 //因?yàn)?-4位剛剛存儲(chǔ)了新加入到字符，所以不能>>28 15 hash ^= (x >> 24); 16 //上面這行代碼并不會(huì)對(duì)X有影響，本身X和hash的高4位相同，下面這行代碼&~即對(duì)28-31(高4位)位清零。 17 hash &= ~x; 18 } 19 } 20 //返回一個(gè)符號(hào)位為0的數(shù)，即丟棄最高位，以免函數(shù)外產(chǎn)生影響。(我們可以考慮，如果只有字符，符號(hào)位不可能為負(fù)) 21 return (hash & 0x7FFFFFFF); 22 }

然后用一個(gè)例題實(shí)踐一下吧吧，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位，當(dāng)前字符占8位，加到h中進(jìn)行雜糅if((g = h & 0xf0000000) != 0) //取h最左四位的值，若均為0，則括號(hào)中執(zhí)行與否沒區(qū)別，故不執(zhí)行{h ^= g>>24; //用h的最左四位的值對(duì)h的右起5~8進(jìn)行雜糅h &= ~g;//清空h的最左四位}}return h; //因?yàn)槊看味记蹇樟俗钭笏奈?#xff0c;最后結(jié)果最多也就是28位二進(jìn)制整數(shù)，不會(huì)超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; }

轉(zhuǎn)載于:https://www.cnblogs.com/ilovetheworld/p/10110061.html

總結(jié)

以上是生活随笔為你收集整理的ELFhash的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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