java中的hash函数，常见的hash函数：-D⾮常经典！！
Hash表算法的详细解析
什么是Hash
Hash，⼀般翻译做“散列”，也有直接⾳译为“哈希”的，就是把任意长度的输⼊(⼜叫做预映射， pre-image)，通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是⼀种压缩映射，也就是，散列值的空间通常远⼩于输⼊的空间，不同的输⼊可能会散列成相同的输出，⽽不可能从散列值来唯⼀的确定输⼊值。简单的说就是⼀种将任意长度的消息压缩到某⼀固定长度的消息摘要的函数。
Hash主要⽤于信息安全领域中加密算法，它把⼀些不同长度的信息转化成杂乱的128位的编码，这些编码值叫做HASH值. 也可以
说，Hash就是到⼀种数据内容和数据存放地址之间的映射关系。
数组的特点是：寻址容易，插⼊和删除困难；⽽链表的特点是：寻址困难，插⼊和删除容易。那么我们能不能综合两者的特性，做出⼀种寻址容易，插⼊删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表，哈希表有多种不同的实现⽅法，我接下来解释的是最常⽤的⼀种⽅法——拉链法，我们可以理解为“链表的数组”，如图：
左边很明显是个数组，数组的每个成员包括⼀个指针，指向⼀个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的⼀些特征把元素分配到不同的链表中去，也是根据这些特征，到正确的链表，再从链表中出这个元素。
元素特征转变为数组下标的⽅法就是散列法。散列法当然不⽌⼀种，下⾯列出三种⽐较常⽤的：
1，除法散列法
最直观的⼀种，上图使⽤的就是这种散列法，公式：
index = value % 16
学过汇编的都知道，求模数其实是通过⼀个除法运算得到的，所以叫“除法散列法”。
2，平⽅散列法
求index是⾮常频繁的操作，⽽乘法的运算要⽐除法来得省时(对现在的CPU来说，估计我们感觉不出来)，所以我们考虑把除法换成乘法和⼀个位移操作。公式：
index = (value * value) >> 28 (右移，除以2^28。记法：左移变⼤，是乘。右移变⼩，是除。)
如果数值分配⽐较均匀的话这种⽅法能得到不错的结果，但我上⾯画的那个图的各个元素的值算出来的index都是0——⾮常失败。也许你还有个问题，value如果很⼤，value * value不会溢出吗？答案是会的，但我们这个乘法不关⼼溢出，因为我们根本不是为了获取相乘结果，⽽是为了获取index。
3，斐波那契(Fibonacci)散列法
平⽅散列法的缺点是显⽽易见的，所以我们能不能出⼀个理想的乘数，⽽不是拿value本⾝当作乘数呢？答案是肯定的。
1，对于16位整数⽽⾔，这个乘数是40503。
2，对于32位整数⽽⾔，这个乘数是2654435769。
3，对于64位整数⽽⾔，这个乘数是11400714819323198485。
这⼏个“理想乘数”是如何得出来的呢？这跟⼀个法则有关，叫黄⾦分割法则，⽽描述黄⾦分割法则的最经典表达式⽆疑就是著名的斐波那契数列，即如此形式的序列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,233, 377, 610， 987, 1597, 2584, 4181, 6765, 10946，…。另外，斐波那契数列的值和太阳系⼋⼤⾏星的轨道半径的⽐例出奇吻合。
对我们常见的32位整数⽽⾔，公式：
index = (value * 2654435769) >> 28
如果⽤这种斐波那契散列法的话，那上⾯的图就变成这样了：
很明显，⽤斐波那契散列法调整之后要⽐原来的取摸散列法好很多。
适⽤范围
快速查，删除的基本数据结构，通常需要总数据量可以放⼊内存。
基本原理及要点
hash函数选择，针对字符串、整数、排列，具体相应的hash⽅法。
碰撞处理，⼀种是open hashing，也称为拉链法；另⼀种就是closed hashing，也称开地址法，opened addressing。
扩展
d-left hashing中的d是多个的意思，我们先简化这个问题，看⼀看2-left hashing。2-left hashing指的是将⼀个哈希表分成长度相等的两半，分别叫做T1和T2，给T1和T2分别配备⼀个哈希函数，h1和h2。
在存储⼀个新的key时，同时⽤两个哈希函数进⾏计算，得出两个地址h1[key]和h2[key]。这时需要检查T1中的h1[key]位置和T2中的h2[key]位置，哪⼀个位置已经存储的(有碰撞的)key⽐较多，然后将新key存储在负载少的位置。如果两边⼀样多，⽐如两个位置都为空或者都存储了⼀个key，就把新key存储在左边的T1⼦表中，2-left也由此⽽来。在查⼀个key时，必须进⾏两次hash，同时查两个位置。
问题实例(海量数据处理)
我们知道hash 表在海量数据处理中有着⼴泛的应⽤，下⾯，请看另⼀道百度⾯试题：
题⽬：海量⽇志数据，提取出某⽇访问百度次数最多的那个IP。
⽅案：IP的数⽬还是有限的，最多2^32个，所以可以考虑使⽤hash将IP直接存⼊内存，然后进⾏统计。
第三部分、最快的Hash表算法
接下来，咱们来具体分析⼀下⼀个最快的Hash表算法。
我们由⼀个简单的问题逐步⼊⼿：有⼀个庞⼤的字符串数组，然后给你⼀个单独的字符串，让你从这
个数组中查是否有这个字符串并到它，你会怎么做？有⼀个⽅法最简单，⽼⽼实实从头查到尾，⼀个⼀个⽐较，直到到为⽌，我想只要学过程序设计的⼈都能把这样⼀个程序作出来，但要是有程序员把这样的程序交给⽤户，我只能⽤⽆语来评价，或许它真的能⼯作，但...也只能如此了。
最合适的算法⾃然是使⽤HashTable(哈希表)，先介绍介绍其中的基本知识，所谓Hash，⼀般是⼀个整数，通过某种算法，可以把⼀个字符串"压缩" 成⼀个整数。当然，⽆论如何，⼀个32位整数是⽆法对应回⼀个字符串的，但在程序中，两个字符串计算出的Hash值相等的可能⾮常⼩，下⾯看看在MPQ中的Hash算法：
函数⼀、以下的函数⽣成⼀个长度为0x500(合10进制数：1280)的cryptTable[0x500]
voidprepareCryptTable()
{
unsignedlong seed = 0x00100001, index1 = 0, index2 = 0, i;for( index1 = 0; index1 < 0x100; index1++)
{for( index2 = index1, i = 0; i < 5; i++, index2 += 0x100)
{
unsignedlongtemp1, temp2;
seed= (seed * 125 + 3) % 0x2AAAAB;
temp1= (seed & 0xFFFF) << 0x10;
seed= (seed * 125 + 3) % 0x2AAAAB;
temp2= (seed & 0xFFFF);
cryptTable[index2]= ( temp1 |temp2 );
}
}
}
函数⼆、以下函数计算lpszFileName字符串的hash值，其中dwHashType为hash的类型(在下⾯的函数三GetHashTablePos函数中调⽤此函数⼆)，其可以取的值为0、1、2；该函数返回lpszFileName 字符串的hash值：
unsigned long HashString( char *lpszFileName, unsigned longdwHashType )
{
unsignedchar *key = (unsigned char *)lpszFileName;
unsignedlong seed1 = 0x7FED7FED;
unsignedlong seed2 = 0xEEEEEEEE;intch;while(*key != 0)
{
ch= toupper(*key++);
seed1= cryptTable[(dwHashType << 8) + ch] ^ (seed1 +seed2);
seed2= ch + seed1 + seed2 + (seed2 << 5) + 3;
}returnseed1;
}
Blizzard的这个算法是⾮常⾼效的，被称为"One-Way Hash"(A one-way hash is a an algorithm that is constructed in such a way that deriving the original string (set of strings, actually) is virtually impossible)。举个例⼦，字符串"p"通过这个算法得到的结果是0xA26067F3。
是不是把第⼀个算法改进⼀下，改成逐个⽐较字符串的Hash值就可以了呢？答案是，远远不够。要想得到最快的算法，就不能进⾏逐个的⽐较，通常是构造⼀个哈希表(Hash Table)来解决问题。哈希表是⼀个⼤数组，这个数组的容量根据程序的要求来定义，例如1024，每⼀个Hash值通过取模运算 (mod) 对应到数组中的⼀个位置。这样，只要⽐较这个字符串的哈希值对应的位置有没有被占⽤，就可以得到最后的结果了，想想这是什么速度？是的，是最快的O(1)，现在仔细看看这个算法吧：
typedef struct{intnHashA;intnHashB;charbExists;
......
} SOMESTRUCTRUE;
⼀种可能的结构体定义？java中index是什么意思
函数三、下述函数为在Hash表中查是否存在⽬标字符串，有则返回要查字符串的Hash值，⽆则，return -1.
int GetHashTablePos( har *lpszString, SOMESTRUCTURE *lpTable )//lpszString要在Hash表中查的字符串，lpTable为存储字符串Hash值的Hash表。
{int nHash = HashString(lpszString); //调⽤上述函数⼆，返回要查字符串lpszString的Hash值。
int nHashPos = nHash %nTableSize;if ( lpTable[nHashPos].bExists && !strcmp( lpTable[nHashPos].pString, lpszString ) )//如果到的Hash值在表中存在，且要查的字符串与表中对应位置的字符串相同
{return nHashPos; //则返回上述调⽤函数⼆后，到的Hash值
}else{return -1;
}
}
看到此，我想⼤家都在想⼀个很严重的问题：“如果两个字符串在哈希表中对应的位置相同怎么办？”，毕竟⼀个数组容量是有限的，这种可能性很⼤。解决该问题的⽅法很多，我⾸先想到的就是⽤“链表”，感谢⼤学⾥学的数据结构教会了这个百试百灵的法宝，我遇到的很多算法都可以转化成链表来解决，
只要在哈希表的每个⼊⼝挂⼀个链表，保存所有对应的字符串就OK了。事情到此似乎有了完美的结局，如果是把问题独⾃交给我解决，此时我可能就要开始定义数据结构然后写代码了。
然⽽Blizzard的程序员使⽤的⽅法则是更精妙的⽅法。基本原理就是：他们在哈希表中不是⽤⼀个哈希值⽽是⽤三个哈希值来校验字符串。
MPQ使⽤⽂件名哈希表来跟踪内部的所有⽂件。但是这个表的格式与正常的哈希表有⼀些不同。⾸先，它没有使⽤哈希作为下标，把实际的⽂件名存储在表中⽤于验证，实际上它根本就没有存储⽂件名。⽽是使⽤了3种不同的哈希：⼀个⽤于哈希表的下标，两个⽤于验证。这两个验证哈希替代了实际⽂件名。
当然了，这样仍然会出现2个不同的⽂件名哈希到3个同样的哈希。但是这种情况发⽣的概率平均是：
1:18889465931478580854784，这个概率对于任何⼈来说应该都是⾜够⼩的。现在再回到数据结构上，Blizzard使⽤的哈希表没有使⽤链表，⽽采⽤"顺延"的⽅式来解决问题，看看这个算法：
函数四、lpszString为要在hash表中查的字符串；lpTable为存储字符串hash值的hash表；nTableSize 为hash表的长度：
int GetHashTablePos( char *lpszString, MPQHASHTABLE *lpTable, intnTableSize )
{const int HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;int nHash =HashString(lpszString, HASH_OFFSET);int nHashA
=HashString(lpszString, HASH_A);int nHashB =HashString(lpszString, HASH_B);int nHashStart = nHash %nTableSize;int nHashPos =nHashStart;while( lpTable[nHashPos].bExists )
{/*如果仅仅是判断在该表中时候存在这个字符串，就⽐较这两个hash值就可以了，不⽤对结构体中的字符串进⾏⽐较。这样会加快运⾏的速度？减少hash表占⽤的空间？这种
⽅法⼀般应⽤在什么场合？*/
if (lpTable[nHashPos].nHashA ==nHashA&& lpTable[nHashPos].nHashB ==nHashB )
{returnnHashPos;
}else{
nHashPos= (nHashPos + 1) %nTableSize;
}if (nHashPos == nHashStart) break;
}return -1;
}
上述程序解释：
1. 计算出字符串的三个哈希值(⼀个⽤来确定位置，另外两个⽤来校验)
2. 察看哈希表中的这个位置
3. 哈希表中这个位置为空吗？如果为空，则肯定该字符串不存在，返回-1。
4. 如果存在，则检查其他两个哈希值是否也匹配，如果匹配，则表⽰到了该字符串，返回其Hash值。
5. 移到下⼀个位置，如果已经移到了表的末尾，则反绕到表的开始位置起继续查询
6. 看看是不是⼜回到了原来的位置，如果是，则返回没到
7. 回到3
ok，这就是本⽂中所说的最快的Hash表算法。什么?不够快?:D。欢迎，各位批评指正。
--------------------------------------------
补充1、⼀个简单的hash函数：
/*key为⼀个字符串，nTableLength为哈希表的长度
*该函数得到的hash值分布⽐较均匀*/unsignedlong getHashIndex( const char *key, intnTableLength )
{
unsignedlong nHash = 0;while (*key)
{
nHash= (nHash<<5) + nHash + *key++;
}return (nHash %nTableLength);
}
补充2、⼀个完整测试程序：
哈希表的数组是定长的，如果太⼤，则浪费，如果太⼩，体现不出效率。合适的数组⼤⼩是哈希表的性能的关键。哈希表的尺⼨最好是⼀个质数。当然，根据不同的数据量，会有不同的哈希表的⼤⼩。对于数据量时多时少的应⽤，最好的设计是使⽤动态可变尺⼨的哈希表，那么如果你发现哈希表尺⼨太⼩了，⽐如其中的元素是哈希表尺⼨的2倍时，我们就需要扩⼤哈希表尺⼨，⼀般是扩⼤⼀倍。
下⾯是哈希表尺⼨⼤⼩的可能取值：
17, 37, 79, 163, 331,
673, 1361, 2729, 5471, 10949,
21911, 43853, 87719, 175447, 350899,
701819, 1403641, 2807303, 5614657, 11229331,
22458671, 44917381, 89834777, 179669557, 359339171,
718678369, 1437356741, 2147483647
以下为该程序的完整源码，已在Linux下测试通过：
#include #include //多谢citylove指正。//crytTable[]⾥⾯保存的是HashString函数⾥⾯将会⽤到的⼀些数据，在
prepareCryptTable//函数⾥⾯初始化
unsigned long cryptTable[0x500];//以下的函数⽣成⼀个长度为0x500(合10进制数：1280)的cryptTable[0x500]
voidprepareCryptTable()
{
unsignedlong seed = 0x00100001, index1 = 0, index2 = 0, i;for( index1 = 0; index1 < 0x100; index1++)
{for( index2 = index1, i = 0; i < 5; i++, index2 += 0x100)
{
unsignedlongtemp1, temp2;
seed= (seed * 125 + 3) % 0x2AAAAB;
temp1= (seed & 0xFFFF) << 0x10;
seed= (seed * 125 + 3) % 0x2AAAAB;
temp2= (seed & 0xFFFF);
cryptTable[index2]= ( temp1 |temp2 );
}
}
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论