大数的hash：
这种题目比较灵活，怎么用的都有，有用一个进制的，又用取模的，等等等等 ，具体问题具体分析吧。
所见过的用于取模的素数：55457， 112927， 100003， 40001.
字符串函数：
BKDRHash（有肯多都说这个函数比下面的准确率高，数组开多大还没有掌握）：
unsigned int BKDRHash(char *str)
{
unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
unsigned int hash = 0;
while (*str)
{
hash = hash * seed + (*str++);
}
return (hash & 0x7FFFFFFF);
}
ELFHash（最常用的字符串函数）：
long elfhash(char *str) {
int i=0;
long g,sum=0;
while (*str)
{
sum=(sum<<4)+((*str++)-97+1);//将hash值左移4位后加上字符ascii
g=sum & 0xf0000000;//取出hash值的高4位
if (g) sum^=g>>24;//因为下一步仍要左移4位，所以如果高4位不为0，进行下面处理，防止丢失信息 将高4位与5~8位xor
sum&=~g;//消除下次可能被移到符号位的4个位
i++;
}
return sum%M;
}
int型数组hash函数:
//其中k是这个数字二进制的位数
int hash(int v[])
{
int h = 0;
for(int i = 0; i < k; i++)
h = ((h<<2) + (v[i]>>4)) ^ (v[i]<<10);
h = h % MOD;
h = h < 0 ? h + MOD : h;
return h;
}
全排列的hash函数：
//其中seq传入一个int型数组
//fac中存储的是各个全排列的进制，如这个函数有9个数字，fac就是
//{0！，1！，2！，3！，4！，5！，6！，7！，8！}（0！是1）
int getkey(int *seq)
{
int i,j,cnt,key=0;
for(i=0;i<9;i++)
{
cnt=0;
for(j=0;j<i;j++)         
if(seq[j]>seq[i])
cnt++;
key+=cnt*fac[i];      // cnt<=i
}
return key;
}
附：对全排列函数的理解：
首先介绍变进制概念：
  所谓变进制，就是一个数字串的不同位置的进制不同。也就是说，和十进制或者二进制不同，变进制数并不是每逢一个常数（例如10或者2）进一，而可能在个位逢2进1，在十位逢6进一等等。
八数码状态一定是一个全排列数。而全排列数有一个非常完美的变进制Hash方法。
全排列变进制数表是{8!, 7!, 6!, 5!, 4!, 3!, 2!, 1!, 0!}
(在这里最后一个0!实际上是用不着的)
下面来说明变进制数码的获得方法
对于一个全排列数的第i位，遍历第(j = i+1 ~ 9)位，统计逆序数（也就是a[i]>a[j]的情况），而这个逆序数恰恰就是第i个变进制数码。根据n进制hash的规则，只要将一个变进制数的每一位变进制数码（也就
是之前求得的逆序数）乘以那一位所对应的进制数（从变进制数表中获得），累加即可。
这里构造可以类比十进制的构造：每一位所能得到的逆序对数乘以这一位的进制正好是下一位的进制。对十进制
来说关心的是数量，而对全排列来说关心的是排列组合（可以通过比较大小来形象刻画），故这里的系数是逆序对的个数。而对每一个排列来说都有一个固定的相对大小的值，故用逆序这种判定大小的对数做系数是合理的。
构造的过程：假设当前序列是三个数字，则加上第四个数字，则得到的全排列的个数是在前三个数的基础上插入第四个数字，而以从小到大排列顺序来考虑，则求出逆序对 即可。
字符串函数怎么用由这个全排列的方法联想一般进制构造的方法：每一个基数都是前面的所有可能的个数，而系数则根据不同的情况确定

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。