江苏网站推广公司哪家好,微信公众号影视网站怎么做,网页升级访问请自觉离开,专业排名优化工具字符串哈希算法#xff08;以ELFHash详解#xff09; 更多字符串哈希算法请参考#xff1a;http://blog.csdn.net/AlburtHoffman/article/details/19641123 先来了解一下何为哈希#xff1a; 哈希表是根据设定的哈希函数H(key)和处理冲突方法将一组关键字映射到一个有限的地…字符串哈希算法以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 (h4) *str; //h左移4位当前字符占8位加到h中进行杂糅if((g h 0xf0000000) ! 0) //取h最左四位的值若均为0则括号中执行与否没区别故不执行{h ^ g24; //用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;
} 转载于:https://www.cnblogs.com/ilovetheworld/p/10110061.html
