一、散列表基本概念
1、散列表(hash table) ，也叫哈希表，是根据关键码而直接进行访问的数据结构。也就是说，它通过把关键码映射到表中一个位置
来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
2、若结构中存在关键码为x的记录，则必定在hash(x)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系hash
为散列函数(hash function)，按这个思想建立的表为散列表。
举个例子：
影碟出租店维护一张表格，以电话号码作为关键码，为了提高查找速度，可以用选择哈希表进行存储
假设影碟出租店有一万张光碟，每天借出与归还均不超出500人次。因此哈希表维护500条记录即可。
我们发现真正要存储的记录比关键码总数（假设8位电话，则关键码总数2^8 个）要少得多。
散列地址冲突
3、散列函数是一个压缩映象函数。关键码集合比散列表地址集合大得多。因此有可能经过散列函数的计算，把不同的关键码映射到
同一个散列地址上，这就产生了冲突 (Collision)。即key1≠ key2，而hash(key1)=hash(key2)，这种现象称冲突。我们将key1与key2称
做同义词。
4、由于关键码集合比地址集合大得多，冲突很难避免。所以对于散列方法，需要讨论以下两个问题：
对于给定的一个关键码集合，选择一个计算简单且地址分布比较均匀的散列函数，避免或尽量减少冲突；
拟订解决冲突的方案。
散列函数选取原则
5、散列函数的选择有两条标准：简单和均匀
简单指散列函数的计算简单快速，能在较短时间内计算出结果。
均匀指散列函数计算出来的地址能均匀分布在整 个地址空间。若key是从关键字码集合中随机抽取的一个关键码，散列函数能
以等概率均匀地分布在表的地址集{0，1，…，m-1}上，以使冲突最小化。
二、散列函数构造方法
（一）、直接定址法
此类函数取关键码的某个线性函数值作为散列地址：hash ( key ) = a * key + b
{ a, b为常数 }
这类散列函数是一对一的映射，一般不会产生冲突。但是，它要求散列地址空间的大小与关键码集合的大小相同。
（二）、数字分析法
构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址。适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况。
有80个记录，关键字为8位十进制数，哈希地址为2位十进制数
（三）、平方取中法
取关键字平方后中间几位作哈希地址。适于关键字位数不定情况。
具体方法：先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的中间
几位数和乘数的每一位都相关，所以由此产生的散列地址较为均匀。（ps：不理解内码的含义）
（四）、折叠法
此方法把关键码自左到右分成位数相等的几部分，每一部分的位数应与散列表地址位数相同，只有最后一部分的位数可以短一些。
把这些部分的数据叠加起来，就可以得到具有该关键码的记录的散列地址。有两种叠加方法：
移位法 — 把各部分的最后一位对齐相加；
分界法 — 各部分不折断，沿各部分的分界来回折叠，然后对齐相加，将相加的结果当做散列地址。
一般当关键码的位数很多，而且关键码每一位上数字的分布大致比较均匀时，可用这种方法得到散列地址。
示例：设给定的关键码为 key = ，若存储空间限定 3 位, 则划分结果为每段 3 位. 上述关键码可划分为 4段：
把超出地址位数的最高位删去, 仅保留最低的3位，做为可用的散列地址。
（五）、随机数法
选择一个随机函数，取关键字的随机函数值为它的散列地址，即 hash(key) = random(key) ；其中random为伪随机函数，但要保证函
数值是在0到m-1之间。
（六）、除留余数法
设散列表中允许的地址数为 m, 散列函数为：
hash ( key ) = key % p
若p取100，则关键字159、259、359互为同义词。我们选取的p值应尽可能使散列函数计算得到的散列地址与各位相关，根据经
验，p最好取一个不大于 m，但最接近于或等于 m 的质数 p,
或选取一 个不小于 20 的质因数的合数作为除数（比如8 = 2*2*2，2 是
8 的质因数，8 是合数）
示例：有一个关键码 key = 962148，散列表大小 m = 25，即 HT[25]。取质数 p= 23。散列函数 hash ( key ) = key % p。则散列地址
为 hash ( 962148 ) = 962148 % 23 = 12
可以按计算出的地址存放记录。需要注意的是，使用上面的散列函数计算出来的地址范围是 0到 22，因此，从23到24这几个散列地
址实际上在一开始是不可能用散列函数计算出来的，只可能在处理溢出时达到这些地址。
（七）、乘余取整法
使用此方法时，先让关键码 key 乘上一个常数
A (0 & A & 1)，提取乘积的小数部分。然后，再用整数 n 乘以这个值，对结果向下取
整，把它做为散列的地址。散列函数为：
三、常见字符串哈希函数
下面列出常见的8个字符串哈希函数，这些都是计算机科学家们研究出来的，计算出来的哈希地址比较平均，冲突较少，但还是会存
在冲突，另外在使用这些函数时，记得在return 的值后面再 % 地址总数，这样得出的地址才会在范围内。
unsigned int SDBMHash(char *str)
unsigned int hash = 0;
while (*str)
// equivalent to: hash = 65599*hash + (*str++);
hash = (*str++) + (hash && 6) + (hash && 16) -
return (hash & 0x7FFFFFFF) % BUCKETS;
}unsigned int RSHash(char *str)
unsigned int b = 378551;
unsigned int a = 63689;
unsigned int hash = 0;
while (*str)
hash = hash * a + (*str++);
return (hash & 0x7FFFFFFF);
}unsigned int JSHash(char *str)
unsigned int hash = ;
while (*str)
hash ^= ((hash && 5) + (*str++) + (hash && 2));
return (hash & 0x7FFFFFFF);
}unsigned int PJWHash(char *str)
unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) * 8);
unsigned int ThreeQuarters
= (unsigned int)((BitsInUnignedInt
* 3) / 4);
unsigned int OneEighth
= (unsigned int)(BitsInUnignedInt / 8);
unsigned int HighBits
= (unsigned int)(0xFFFFFFFF) && (BitsInUnignedInt - OneEighth);
unsigned int hash
unsigned int test
while (*str)
hash = (hash && OneEighth) + (*str++);
if ((test = hash & HighBits) != 0)
hash = ((hash ^ (test && ThreeQuarters)) & (~HighBits));
return (hash & 0x7FFFFFFF);
}unsigned int ELFHash(char *str)
unsigned int hash = 0;
unsigned int x
while (*str)
hash = (hash && 4) + (*str++);
if ((x = hash & 0xF0000000L) != 0)
hash ^= (x && 24);
hash &= ~x;
return (hash & 0x7FFFFFFF);
}unsigned int BKDRHash(char *str)
unsigned int seed = 131; // 31 131
131313 etc..
unsigned int hash = 0;
while (*str)
hash = hash * seed + (*str++);
return (hash & 0x7FFFFFFF);
}unsigned int DJBHash(char *str)
unsigned int hash = 5381;
while (*str)
hash += (hash && 5) + (*str++);
return (hash & 0x7FFFFFFF);
}unsigned int APHash(char *str)
unsigned int hash = 0;
for (i = 0; * i++)
if ((i & 1) == 0)
hash ^= ((hash && 7) ^ (*str++) ^ (hash && 3));
hash ^= (~((hash && 11) ^ (*str++) ^ (hash && 5)));
return (hash & 0x7FFFFFFF);
下面使用第一个哈希函数，写个小程序测试一下是否会产生冲突：
#include&stdio.h&#define BUCKETS 101unsigned int SDBMHash(char *str)
unsigned int hash = 0;
while (*str)
// equivalent to: hash = 65599*hash + (*str++);
hash = (*str++) + (hash && 6) + (hash && 16) -
return (hash & 0x7FFFFFFF) % BUCKETS;
}int main(void)
char *keywords[] =
"auto", "break", "case", "char", "const", "continue", "default", "do",
"double", "else", "enum", "extern", "float", "for", "goto", "if",
"int", "long", "register", "return", "short", "signed", "sizeof", "static",
"struct", "switch", "typedef", "union", "unsigned", "void", "volatile", "while"
// 哈希表每个地址的映射次数
// 0地址的映射次数用count[0]表示
int count[BUCKETS] = {0};
int size = sizeof(keywords) / sizeof(keywords[0]);
for (i = 0; i & i++)
int pos = SDBMHash(keywords[i]);
count[pos]++;
for (i = 0; i & i++)
int pos = SDBMHash(keywords[i]);
printf("%-10s %d %d\n", keywords[i], pos, count[pos]);
可以看出，确实会产生冲突，比如有3个词语 default、extern、for 都映射到了地址16上。
散列表之散列函数
什么是好的散列函数
将关键字转化为自然数
散列函数的三种设计方法
除法散列法
乘法散列法
全域散列法散列表之散列函数我们在之前的文章《散列表之链接法》中已经提到过，散列函数是散列表的...
1、散列：理想的散列表数据结构只不过是一个包含有关键字的具有固定大小的数组。典型情况下，一个关键字就是带有相关值的字符串。2、散列的基本思想：以关键字key为自变量，通过一个确定的函数 h（散列函数）...
1.散列函数的构造方法
1.1 直接定址法
去关键字的某个线性函数值为散列地址：f(key)=a*key+b(a、b为常数)...
由于哈希表的查找高效性，在平时的算法中用的也是比较多。例如：字符串、单词个数的统计，只出现一次字符或者数字的统计，两个集合相同元素的查找等等，还有插入删除的高效（链地址法）都可以用哈希表来解决。所以这...
前面介绍的查找是建立在比较的基础上，查找效率由比较次数决定，不仅与被查数据整体的存储结构有关，还与逻辑上可被查找的数据集合所含的数据个数有关，同时与待查记录在查找表中位置以及查找策略如查找方向有关...
题目： 已知关键字序列为{30，25，72，38，8，17，59}，设散列表表长为15.散列函数是H(key)=key MOD 13,处理冲突的方法为二次探测法Hi= ( H(key) + di )m...
1、散列函数的选择有两条标准：简单和均匀。
　简单指散列函数的计算简单快速；
1. 散列函数如果输入的关键字是整数，则一般合理方法是直接返回对表大小取模（Key mod TableSize）的结果，除非 Key 碰巧具有一些不太理想的特质。如，表的大小为 10，而关键字都是 1...
开放定址法：当冲突发生时，使用某种探测技术在散列表中形成一个探测序列。沿此序列逐个单元地查找，直到碰到一个开放的地址（即该地址单元为空）为止，然后插入。
基本公式...
没有更多推荐了，本文转自：http://www.cnblogs.com/uvsjoh/archive//2420120.html
所谓完美哈希函数，就是指没有冲突的哈希函数，即对任意的 key1 != key2 有h(key1) != h(key2)。设定义域为X，值域为Y, n=|X|,m=|Y|，那么肯定有m&=n,如果对于不同的key1,key2属于X,有h(key1)!=h(key2)，那么称h为完美哈希函数，当m=n时，h称为最小完美哈希函数（这个时候就是一一映射了）。
在处理大规模字符串数据时，经常要为每个字符串分配一个整数ID。这就需要一个字符串的哈希函数。怎么样找到一个完美的字符串hash函数呢？有一些常用的字符串hash函数。像BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash等等。都是比较经典的。
下面是转载的对几个常用字符串hash函数的分析：
常用的字符串Hash函数还有ELFHash，APHash等等，都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数，这些函数几乎不可能找到碰撞。
常用字符串哈希函数有 BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash等等。对于以上几种哈希函数，我对其进行了一个小小的评测。
其中数据1为100000个字母和数字组成的随机串哈希冲突个数。数据2为100000个有意义的英文句子哈希冲突个数。数据3为数据1的哈希值与 1000003(大素数)求模后存储到线性表中冲突的个数。数据4为数据1的哈希值与(更大素数)求模后存储到线性表中冲突的个数。
经过比较，得出以上平均得分。平均数为平方平均数。可以发现，BKDRHash无论是在实际效果还是编码实现中，效果都是最突出的。APHash也是较为优秀的算法。DJBHash,JSHash,RSHash与SDBMHash各有千秋。PJWHash与ELFHash效果最差，但得分相似，其算法本质是相似的。
unsigned int SDBMHash(char *str)
unsigned int hash = 0;
while (*str)
// equivalent to: hash = 65599*hash + (*str++);
hash = (*str++) + (hash && 6) + (hash && 16) -
return (hash & 0x7FFFFFFF);
// RS Hash Function
unsigned int RSHash(char *str)
unsigned int b = 378551;
unsigned int a = 63689;
unsigned int hash = 0;
while (*str)
hash = hash * a + (*str++);
return (hash & 0x7FFFFFFF);
// JS Hash Function
unsigned int JSHash(char *str)
unsigned int hash = ;
while (*str)
hash ^= ((hash && 5) + (*str++) + (hash && 2));
return (hash & 0x7FFFFFFF);
// P. J. Weinberger Hash Function
unsigned int PJWHash(char *str)
unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) * 8);
unsigned int ThreeQuarters
= (unsigned int)((BitsInUnignedInt
* 3) / 4);
unsigned int OneEighth
= (unsigned int)(BitsInUnignedInt / 8);
unsigned int HighBits
= (unsigned int)(0xFFFFFFFF) && (BitsInUnignedInt - OneEighth);
unsigned int hash
unsigned int test
while (*str)
hash = (hash && OneEighth) + (*str++);
if ((test = hash & HighBits) != 0)
hash = ((hash ^ (test && ThreeQuarters)) & (~HighBits));
return (hash & 0x7FFFFFFF);
// ELF Hash Function
unsigned int ELFHash(char *str)
unsigned int hash = 0;
unsigned int x
while (*str)
hash = (hash && 4) + (*str++);
if ((x = hash & 0xF0000000L) != 0)
hash ^= (x && 24);
hash &= ~x;
return (hash & 0x7FFFFFFF);
// BKDR Hash Function
unsigned int BKDRHash(char *str)
unsigned int seed = 131; // 31 131
131313 etc..
unsigned int hash = 0;
while (*str)
hash = hash * seed + (*str++);
return (hash & 0x7FFFFFFF);
// DJB Hash Function
unsigned int DJBHash(char *str)
unsigned int hash = 5381;
while (*str)
hash += (hash && 5) + (*str++);
return (hash & 0x7FFFFFFF);
// AP Hash Function
unsigned int APHash(char *str)
unsigned int hash = 0;
for (i=0; * i++)
if ((i & 1) == 0)
hash ^= ((hash && 7) ^ (*str++) ^ (hash && 3));
hash ^= (~((hash && 11) ^ (*str++) ^ (hash && 5)));
return (hash & 0x7FFFFFFF);
阅读(...) 评论()下次自动登录
现在的位置:
各种Hash函数冲突率分析
字符串Hash函数对比
今天根据自己的理解重新整理了一下几个字符串hash函数，使用了模板，使其支持宽字符串，代码如下:
/// @brief BKDR Hash Function
/// @detail 本由于在Brian Kernighan与Dennis Ritchie的《The C Programming Language》一书被展示而得名，是一种简单快捷的hash算法，也是Java目前采用的字符串的Hash算法（累乘因子为31）。
template&class T&
size_t BKDRHash(const T *str)
register size_t hash = 0;
while (size_t ch = (size_t)*str++)
hash = hash * 131 +
// 也可以乘以31、131、、131313..
// 有人说将乘法分解为位运算及加减法可以提高效率，如将上式表达为：hash = hash && 7 + hash && 1 + hash +
// 但其实在Intel平台上，CPU内部对二者的处理效率都是差不多的，
// 我分别进行了100亿次的上述两种运算，发现二者时间差距基本为0（如果是Debug版，分解成位运算后的耗时还要高1/3）；
// 在ARM这类RISC系统上没有测试过，由于ARM内部使用Booth's Algorithm来模拟32位整数乘法运算，它的效率与乘数有关：
// 当乘数8-31位都为1或0时，需要1个时钟周期
// 当乘数16-31位都为1或0时，需要2个时钟周期
// 当乘数24-31位都为1或0时，需要3个时钟周期
// 否则，需要4个时钟周期
// 因此，虽然我没有实际测试，但是我依然认为二者效率上差别不大
/// @brief SDBM Hash Function
/// @detail 本算法是由于在开源项目SDBM（一种简单的数据库引擎）中被应用而得名，它与BKDRHash思想一致，只是种子不同而已。
template&class T&
size_t SDBMHash(const T *str)
register size_t hash = 0;
while (size_t ch = (size_t)*str++)
hash = 65599 * hash +
//hash = (size_t)ch + (hash && 6) + (hash && 16) -
/// @brief RS Hash Function
/// @detail 因Robert Sedgwicks在其《Algorithms in C》一书中展示而得名。
template&class T&
size_t RSHash(const T *str)
register size_t hash = 0;
size_t magic = 63689;
while (size_t ch = (size_t)*str++)
hash = hash * magic +
magic *= 378551;
/// @brief AP Hash Function
/// @detail 由Arash Partow发明的一种hash算法。
template&class T&
size_t APHash(const T *str)
register size_t hash = 0;
for (long i = 0; ch = (size_t)*str++; i++)
if ((i & 1) == 0)
hash ^= ((hash && 7) ^ ch ^ (hash && 3));
hash ^= (~((hash && 11) ^ ch ^ (hash && 5)));
/// @brief JS Hash Function
/// 由Justin Sobel发明的一种hash算法。
template&class T&
size_t JSHash(const T *str)
// 这是由本人添加，以保证空字符串返回哈希值0
register size_t hash = ;
while (size_t ch = (size_t)*str++)
hash ^= ((hash && 5) + ch + (hash && 2));
/// @brief DEK Function
/// @detail 本算法是由于Donald E. Knuth在《Art Of Computer Programming Volume 3》中展示而得名。
template&class T&
size_t DEKHash(const T* str)
// 这是由本人添加，以保证空字符串返回哈希值0
register size_t hash = ;
while (size_t ch = (size_t)*str++)
hash = ((hash && 5) ^ (hash && 27)) ^
/// @brief FNV Hash Function
/// @detail Unix system系统中使用的一种著名hash算法，后来微软也在其hash_map中实现。
template&class T&
size_t FNVHash(const T* str)
if(!*str) // 这是由本人添加，以保证空字符串返回哈希值0
register size_t hash = ;
while (size_t ch = (size_t)*str++)
/// @brief DJB Hash Function
/// @detail 由Daniel J. Bernstein教授发明的一种hash算法。
template&class T&
size_t DJBHash(const T *str)
if(!*str) // 这是由本人添加，以保证空字符串返回哈希值0
register size_t hash = 5381;
while (size_t ch = (size_t)*str++)
hash += (hash && 5) +
/// @brief DJB Hash Function 2
/// @detail 由Daniel J. Bernstein 发明的另一种hash算法。
template&class T&
size_t DJB2Hash(const T *str)
if(!*str) // 这是由本人添加，以保证空字符串返回哈希值0
register size_t hash = 5381;
while (size_t ch = (size_t)*str++)
hash = hash * 33 ^
/// @brief PJW Hash Function
/// @detail 本算法是基于AT&T贝尔实验室的Peter J. Weinberger的论文而发明的一种hash算法。
template&class T&
size_t PJWHash(const T *str)
static const size_t TotalBits
= sizeof(size_t) * 8;
static const size_t ThreeQuarters = (TotalBits
static const size_t OneEighth
= TotalBits / 8;
static const size_t HighBits
= ((size_t)-1) && (TotalBits - OneEighth);
register size_t hash = 0;
size_t magic = 0;
while (size_t ch = (size_t)*str++)
hash = (hash && OneEighth) +
if ((magic = hash & HighBits) != 0)
hash = ((hash ^ (magic && ThreeQuarters)) & (~HighBits));
/// @brief ELF Hash Function
/// @detail 由于在Unix的Extended Library Function被附带而得名的一种hash算法，它其实就是PJW Hash的变形。
template&class T&
size_t ELFHash(const T *str)
static const size_t TotalBits
= sizeof(size_t) * 8;
static const size_t ThreeQuarters = (TotalBits
static const size_t OneEighth
= TotalBits / 8;
static const size_t HighBits
= ((size_t)-1) && (TotalBits - OneEighth);
register size_t hash = 0;
size_t magic = 0;
while (size_t ch = (size_t)*str++)
hash = (hash && OneEighth) +
if ((magic = hash & HighBits) != 0)
hash ^= (magic && ThreeQuarters);
我对这些hash的散列质量及效率作了一个简单测试，测试结果如下：
测试1：对100000个由大小写字母与数字随机的ANSI字符串（无重复，每个字符串最大长度不超过64字符）进行散列：
字符串函数
除1000003取余后的冲突数
测试2：对100000个由任意UNICODE组成随机字符串（无重复，每个字符串最大长度不超过64字符）进行散列：
字符串函数
除1000003取余后的冲突数
测试3：对1000000个随机ANSI字符串（无重复，每个字符串最大长度不超过64字符）进行散列：
字符串函数
耗时（毫秒）
结论：也许是我的样本存在一些特殊性，在对ASCII码字符串进行散列时，PJW与ELF Hash（它们其实是同一种算法）无论是质量还是效率，都相当糟糕；例如："b5"与“aE"，这两个字符串按照PJW散列出来的hash值就是一样的。 另外，其它几种依靠异或来散列的哈希函数，如：JS/DEK/DJB Hash，在对字母与数字组成的字符串的散列效果也不怎么好。相对而言，还是BKDR与SDBM这类简单的Hash效率与效果更好。
常用的字符串Hash函数还有ELFHash，APHash等等，都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生 影响。另外还有以MD5和SHA1为代表的杂凑函数，这些函数几乎不可能找到碰撞。
常用字符串哈希函数有 BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash等等。对于以上几种哈 希函数，我对其进行了一个小小的评测。
其中数据1为100000个字母和数字组成的随机串哈希冲突个数。数据2为100000个有意义的英文句子哈希冲突个数。数据3为数据1的哈希值与 1000003(大素数)求模后存储到线性表中冲突的个数。数据4为数据1的哈希值与(更大素数)求模后存储到线性表中冲突的个数。
经过比较，得出以上平均得分。平均数为平方平均数。可以发现，BKDRHash无论是在实际效果还是编码实现中，效果都是最突出的。APHash也 是较为优秀的算法。DJBHash,JSHash,RSHash与SDBMHash各有千秋。PJWHash与ELFHash效果最差，但得分相似，其算 法本质是相似的
unsigned int SDBMHash(char *str)
unsigned int hash = 0;
while (*str)
// equivalent to: hash = 65599*hash + (*str++);
hash = (*str++) + (hash && 6) + (hash && 16) -
return (hash & 0x7FFFFFFF);
// RS Hash Function
unsigned int RSHash(char *str)
unsigned int b = 378551;
unsigned int a = 63689;
unsigned int hash = 0;
while (*str)
hash = hash * a + (*str++);
return (hash & 0x7FFFFFFF);
// JS Hash Function
unsigned int JSHash(char *str)
unsigned int hash = ;
while (*str)
hash ^= ((hash && 5) + (*str++) + (hash && 2));
return (hash & 0x7FFFFFFF);
// P. J. Weinberger Hash Function
unsigned int PJWHash(char *str)
unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) * 8);
unsigned int ThreeQuarters
= (unsigned int)((BitsInUnignedInt
* 3) / 4);
unsigned int OneEighth
= (unsigned int)(BitsInUnignedInt / 8);
unsigned int HighBits
= (unsigned int)(0xFFFFFFFF) && (BitsInUnignedInt - OneEighth);
unsigned int hash
unsigned int test
while (*str)
hash = (hash && OneEighth) + (*str++);
if ((test = hash & HighBits) != 0)
hash = ((hash ^ (test && ThreeQuarters)) & (~HighBits));
return (hash & 0x7FFFFFFF);
// ELF Hash Function
unsigned int ELFHash(char *str)
unsigned int hash = 0;
unsigned int x
while (*str)
hash = (hash && 4) + (*str++);
if ((x = hash & 0xF0000000L) != 0)
hash ^= (x && 24);
hash &= ~x;
return (hash & 0x7FFFFFFF);
// BKDR Hash Function
unsigned int BKDRHash(char *str)
unsigned int seed = 131; // 31 131
131313 etc..
unsigned int hash = 0;
while (*str)
hash = hash * seed + (*str++);
return (hash & 0x7FFFFFFF);
// DJB Hash Function
unsigned int DJBHash(char *str)
unsigned int hash = 5381;
while (*str)
hash += (hash && 5) + (*str++);
return (hash & 0x7FFFFFFF);
// AP Hash Function
unsigned int APHash(char *str)
unsigned int hash = 0;
for (i=0; * i++)
if ((i & 1) == 0)
hash ^= ((hash && 7) ^ (*str++) ^ (hash && 3));
hash ^= (~((hash && 11) ^ (*str++) ^ (hash && 5)));
return (hash & 0x7FFFFFFF);
【上篇】【下篇】温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！&&|&&
LOFTER精选
网易考拉推荐
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
阅读(1421)|
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
历史上的今天
loftPermalink:'',
id:'fks_083',
blogTitle:'\t\t字符串经典hash函数',
blogAbstract:'常用的字符串Hash函数还有ELFHash，APHash等等，都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数，这些函数几乎不可能找到碰撞。常用字符串哈希函数有BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash等等。对于以上几种哈希函数，我对其进行了一个小小的评测。
blogTag:'',
blogUrl:'blog/static/',
isPublished:1,
istop:false,
modifyTime:0,
publishTime:7,
permalink:'blog/static/',
commentCount:0,
mainCommentCount:0,
recommendCount:0,
bsrk:-100,
publisherId:0,
recomBlogHome:false,
currentRecomBlog:false,
attachmentsFileIds:[],
groupInfo:{},
friendstatus:'none',
followstatus:'unFollow',
pubSucc:'',
visitorProvince:'',
visitorCity:'',
visitorNewUser:false,
postAddInfo:{},
mset:'000',
remindgoodnightblog:false,
isBlackVisitor:false,
isShowYodaoAd:false,
hostIntro:'',
hmcon:'1',
selfRecomBlogCount:'0',
lofter_single:''
{list a as x}
{if x.moveFrom=='wap'}
{elseif x.moveFrom=='iphone'}
{elseif x.moveFrom=='android'}
{elseif x.moveFrom=='mobile'}
${a.selfIntro|escape}{if great260}${suplement}{/if}
{list a as x}
推荐过这篇日志的人：
{list a as x}
{if !!b&&b.length>0}
他们还推荐了：
{list b as y}
转载记录：
{list d as x}
{list a as x}
{list a as x}
{list a as x}
{list a as x}
{if x_index>4}{break}{/if}
${fn2(x.publishTime,'yyyy-MM-dd HH:mm:ss')}
{list a as x}
{if !!(blogDetail.preBlogPermalink)}
{if !!(blogDetail.nextBlogPermalink)}
{list a as x}
{if defined('newslist')&&newslist.length>0}
{list newslist as x}
{if x_index>7}{break}{/if}
{list a as x}
{var first_option =}
{list x.voteDetailList as voteToOption}
{if voteToOption==1}
{if first_option==false},{/if}&&“${b[voteToOption_index]}”&&
{if (x.role!="-1") },“我是${c[x.role]}”&&{/if}
&&&&&&&&${fn1(x.voteTime)}
{if x.userName==''}{/if}
网易公司版权所有&&
{list x.l as y}
{if defined('wl')}
{list wl as x}{/list}