哈希表之bkdrhash算法解析及扩展

             BKDRHASH是一种字符哈希算法,像BKDRHash，APHash。DJBHash，JSHash，RSHash。SDBMHash。PJWHash。ELFHash等等,这些都是比較经典的，通过http://blog.csdn.net/wanglx_/article/details/40300363（字符串哈希函数）这篇文章，我们可知道，BKDRHash是比較好的一个获取哈希值的方法。以下就解说这个BKDRHash函数是怎样推导实现的。

            当我看到BKDRHash的代码时。不禁就疑惑了。这里面有个常数Seed，取值为31、131等，为什么要这么取。我取其它的值不行吗？还有为什么要将每一个字符相加。并乘以这个Seed？ 这些究竟是什么含义？ 最后想了老半天都是不得其解，最后绕进素数里面出不来了……最后在一位牛人的指点下。才茅塞顿开。以下把我的想法和推导过程记录例如以下。

BKDRHash计算公式的推导

          由一个字符串（比方：ad）得到其哈希值。为了降低碰撞，应该使该字符串中每一个字符都參与哈希值计算。使其符合雪崩效应，也就是说即使改变字符串中的一个字节，也会对终于的哈希值造成较大的影响。我们直接想到的办法就是让字符串中的每一个字符相加。得到其和SUM，让SUM作为哈希值，如SUM（ad）= a+d;但是依据ascii码表得知a(97)+d(100)=b(98)+c(99)。那么发生了碰撞，我们发现直接求和的话会非常easy发生碰撞，那么怎么办哪？我们能够对字符间的差距进行放大，乘以一个系数：

SUM(ad) =系数1 * a + 系数2 * d

SUM(bc)= 系数1 * b + 系数2 * c

系数1不等于系数2。这样SUM(ad)等于SUM(bc)的概率就会大大减小。

           但是我们的字符串不可能仅仅有两位或者三位，我们也不可能为每一个系数去人为的赋值。但是字符串中有位数的顺序。比方在”ab”中，b是第0位，a是第1位,那么我们能够用系数的n次方作为每一个字符的系数，但这个系数不能为1:

SUM(ad) =系数^1 * a + 系数^0 * d

SUM(bc)= 系数^1 * b + 系数^0 * c

这样我们就大大减少了碰撞的发生，以下我们如果有个字符数组p，有n个元素，那么

即:

以下就是这个“系数”取值的问题。取什么值那？从上面的分析来看。取除1之外的什么值都能够，我们知道整数不是奇数就是偶数。为了便于推算我们将偶数分为2的幂的偶数和非2的幂的偶数，也就是分3种取值讨论

系数的推导

如今我们的任务是推导系数的值，分2的幂的偶数、非2的幂的偶数、奇数三个部分讨论。

a.      取2的幂

假如我们取32，也就是2^5，那么我们计算SUM(ad)和SUM(bc)结果例如以下:

结果不同，有效处理了碰撞。

可是当我们进一步測试会发现。当我们取SUM(ahijklmn)和SUM(hijklmn)时计算得:

取SUM(abhijklmn)和SUM(abchijklmn)时计算得:

SUM(abcdefghijklmn)和SUM(123456hijklmn)时计算得:

我们会发现，仅仅要最末尾的”hijklmn”这几个字符不变，无论前面怎么变，得到的哈希值都是一样的，全然碰撞了！

这是为什么那？

          首先哈希值SUM的存储类型用什么？当然用unsignedint ,由于值会非常大，unsigned int 是32位。而仅仅要计算就可能会溢出，CPU对于溢出的处理是抛弃最高位，比方两个unsigned int 的值相加结果为33位，那么最高位33位就会被抛弃。那么我们对上面的情况进行计算:

计算SUM(ahijklmn)和SUM(bhijklmn)：

SUM(ahijklmn)= 32^7*a + 32^6*h + 32^5*I + 32^4*j + 32^3*k + 32^2*l + 32^1*m + 32^0*n

SUM(bhijklmn)= 32^7*b + 32^6*h + 32^5*I + 32^4*j + 32^3*k + 32^2*l + 32^1*m + 32^0*n

将32换为2^5得：

SUM(ahijklmn)= 2^35*a + 2^30*h + 2^25*I + 2^20*j + 2^15*k + 2^10*l + 2^5*m + 2^0*n

SUM(bhijklmn)= 2^35*b + 2^30*h + 2^25*I + 2^20*j + 2^15*k + 2^10*l + 2^5*m + 2^0*n

由此可知SUM(ahijklmn)和SUM(bhijklmn)都大于unsignedint所能表达的最大值，所以须要抛弃最高位，也就是对0x100000000(也就是2^33)取余，依据同余定理：

(a+b)%m= (a%m + b%m)%m

(a*b)%m= (a%m * b%m)%m

可知

SUM(ahijklmn)%2^33 = (2^35*a% 2^33  +  2^30*h% 2^33  + … +  2^0*n%2^33)% 2^33

SUM(bhijklmn)%2^33 = (2^35*b % 2^33  +  2^30*h % 2^33  + … +  2^0*n%2^33) 2^33

2^35*a% 2^33和 2^35*b % 2^33 为零，所以因溢出被CPU舍弃。得

SUM(ahijklmn)%2^33 = (2^30*h% 2^33  + … +  2^0*n% 2^33) 2^33

SUM(bhijklmn)%2^33 = (2^30*h % 2^33  + … +  2^0*n% 2^33) 2^33

终于他们的哈希值为

SUM(ahijklmn)= 2^30*h + 2^25*I + 2^20*j + 2^15*k + 2^10*l + 2^5*m + 2^0*n

SUM(bhijklmn)= 2^30*h + 2^25*I + 2^20*j + 2^15*k + 2^10*l + 2^5*m + 2^0*n

所以SUM(ahijklmn)等于SUM(bhijklmn)，这就是为什么” hijklmn”不变时，无论前面是什么字符串都会被舍弃，得到一样的字符串。

这里用的是32=2^5，仅仅要你用2^n，n无论为多少都不行。都会由于字符串的长度达到一定值而造成前面的被舍弃。造成一直碰撞。

b.       取非2的幂的偶数

既然去取2的幂不行，那么我们取非2的幂的偶数，假如我们取6作为系数。6为2^2+2，我们由上面取2的幂的推导可知，当字符的长度大于等于33时，系数就会变为6^32=3*2^33，可知系数大于2^32，对2^33取余，被舍弃。那么造成仅仅要后32个字符不变，前面无论有多少个同的字符，都会被舍弃，计算所得的哈希值也就一样。

由上面两块可知。系数取偶数行不通

c.      取奇数（大于1）

假如我们取9=2^3+1，9^2=81=80+1。9^3=729=728+1，… 。9^n=9^n-1+1，我们知道9的幂肯定是奇数。那么9^n-1肯定为偶数，由上面的推论可知字符串达到一定的长度时。偶数系数前面的字符是能够舍弃的。但是9^n=9^n-1+1，最后的1是永远不会被舍弃的，所以每一个字符都会參与运算，取大于1的奇数可行。

结论

由上面三步的推导可知。这个系数应当选择大于1的奇数，这样能够非常好的减少碰撞的几率，那么我们就能够依据上面推导的公式，用代码实现:

bkdrhash的初步代码实现例如以下:

#include <iostream> #include <MATH.H> unsigned int str_hash_1(const char* s) { unsigned char *p = (unsigned char*)s; unsigned int hash = 0; unsigned int seed = 3;//3,5,7,9,...,etc奇数 unsigned int nIndex = 0; unsigned int nLen = strlen((char*)p); while( *p ) { hash = hash + pow(3,nLen-nIndex-1)*(*p); ++p; nIndex++; } return hash; } int main(int argc, char* argv[]) { std::cout << str_hash_1("hijklmn")<<std::endl; std::cout << str_hash_1("bhijklmn")<<std::endl; getchar(); return 0; } 事实上我们能够对代码进行简化，即利用递归进行实现，可是在使用bkdrhash时你会发现里面大多源代码使用的都是特殊的奇数2^n-1，那是由于在CPU的运算中移位和减法比較快。代码例如以下:

#include <iostream> unsigned int bkdr_hash(const char* key) { char* str = const_cast<char*>(key); unsigned int seed = 31; // 31 131 1313 13131 131313 etc.. 37 unsigned int hash = 0; while (*str) { hash = hash * seed + (*str++); } return hash; } int main(int argc, char* argv[]) { std::cout << bkdr_hash("hijklmn")<<std::endl; std::cout << bkdr_hash("bhijklmn")<<std::endl; getchar(); return 0; }

扩展

注意：即使终于求得的bkdrhash值差点儿不会冲突碰撞。但他们都是非常大的值，不可能直接映射到哈希数组地址上，所以一般都是直接对哈希数组大小取余，以余数作为索引地址，可是这就造成了，可能的地址冲突。bkdrhash值不一样，可是取余后得到的索引地址一样。也就是冲突。仅仅是这样的冲突的概率非常小。对于哈希表不可能全然消除碰撞。仅仅能减少碰撞的几率。作为对哈希知识的进一步熟悉。以下罗列几点提升哈希表效率的注意点:

1.选用的哈希函数

            哈希函数的目的就是为了产生譬如字符串的哈希值，让不同的字符串尽量产生不同的哈希值的函数就是好的哈希函数，全然不会产生同样的哈希函数就是完美的。

2.处理冲突的方法

         处理冲突的方法有多种，拉链法、线性探測等，我喜欢用拉链法

3.哈希表的大小

         这个哈希表的大小是固定的。但能够动态调整。也就是创建个新的数组，用旧的给新的循环又一次计算Key赋值。删除旧的。

但最好依据需求数据量设置足够大的初始值。防止动态调整的频繁，由于调整是非常费时又费空间的。还有重要的是，这个哈希表的大小要设为一个质数，为什么是质数？由于质数仅仅有1和它本身两个约数，当用bkdrhash算得的key对哈希表大小取余时，不会由于存在公约数而缩小余数的范围，假设余数范围缩小的话，就会加大碰撞的几率(说法有点牵强，知道的童鞋请给个合理的解释)。

4.装载因子。即哈希表的饱和程度

一般来说装载因子越小越好。装载因子越小，碰撞也就越小。哈希表的速度就会越快，但是这样会大大的浪费空间。假如装载因子为0.1。那么哈希表仅仅有10%的空间被真正利用。其余的90%都浪费了，这就是时间和空间的矛盾点。为了平衡，如今大部分採用的是0.75作为装载因子，装载因子达到0.75，那么就动态添加哈希表的大小。

哈希表的初步C++封装实现

//my_hash_map.h //哈希表的初步实现 //參考互联网资料实现 #pragma once #define HASH_MAX_STRING_LEN 128 #include <WINDOWS.H> template<typename objectType> class my_strhash_map { protected: struct Assoc { Assoc() { memset(sKey,0,HASH_MAX_STRING_LEN); pData = NULL; pNext = NULL; } char sKey[HASH_MAX_STRING_LEN]; objectType* pData; Assoc* pNext; }; typedef Assoc* LPAssoc; public: struct iterator { friend class my_strhash_map; iterator() { m_pIter = NULL; m_nIndex = 0; m_pMap = NULL; } //前缀，如++i iterator& operator++() { if ( m_pIter->pNext ) { m_pIter = m_pIter->pNext; return *this } for ( ULONG i=m_nIndex+1; i<m_pMap->m_nHashSize; i++ ) { if ( NULL != m_pMap->m_pHashTable[i] ) { m_pIter = m_pMap->m_pHashTable[i]; m_nIndex = i; return *this; } } m_pIter = NULL; m_nIndex = 0; return *this; } //后缀 如i++ const iterator operator++(int) { iterator tmp( m_pIter,m_nIndex,m_pMap ); if ( m_pIter->pNext ) { m_pIter = m_pIter->pNext; return tmp; } for ( ULONG i=m_nIndex+1; i<m_pMap->m_nHashSize; i++ ) { if ( NULL != m_pMap->m_pHashTable[i] ) { m_pIter = m_pMap->m_pHashTable[i]; m_nIndex = i; return tmp; } } m_pIter = NULL; m_nIndex = 0; return tmp; } objectType& operator *() { return *( m_pIter->pData ); } bool operator== (const iterator& obj) { return m_pMap == obj.m_pMap && m_pIter == obj.m_pIter; } bool operator != (const iterator& obj) { return m_pMap != obj.m_pMap || m_pIter != obj.m_pIter; } protected: iterator(LPAssoc pAssoc,ULONG nIndex,my_strhash_map* map) { m_pIter = pAssoc; m_nIndex = nIndex; m_pMap = map; } LPAssoc m_pIter; ULONG m_nIndex; my_strhash_map* m_pMap; }; my_strhash_map(ULONG nInitSize = 199,BOOL bAutoIncr = TRUE) { m_bAutoIncr = bAutoIncr; m_nHashSize = 0; m_nCount = 0; m_nConflictCount = 0; m_pHashTable = NULL; InitMap(nInitSize); } BOOL insert(const char* sKey,objectType obj) { if ( NULL == sKey || strlen(sKey) > HASH_MAX_STRING_LEN ) { return FALSE; } ULONG nHash = BkdrHashKey(sKey) % m_nHashSize; LPAssoc pAssoc = m_pHashTable[nHash]; if ( NULL == pAssoc ) { m_pHashTable[nHash] = new Assoc; strcpy(m_pHashTable[nHash]->sKey,sKey); m_pHashTable[nHash]->pData = new objectType(obj); m_pHashTable[nHash]->pNext = NULL; m_nCount++; } else { LPAssoc pAssocPre = pAssoc; while( pAssoc ) { //反复插入同一sKey，则返回 if ( 0 == strcmp(pAssoc->sKey,sKey) ) break; pAssocPre = pAssoc; pAssoc = pAssoc->pNext; } if ( NULL == pAssoc ) { pAssoc = new Assoc; strcpy(pAssoc->sKey,sKey); pAssoc->pData = new objectType(obj); pAssoc->pNext = NULL; pAssocPre->pNext = pAssoc; m_nConflictCount++; } } if ( m_nCount > m_nHashSize ) { ReSetTableSize( AdjustSize(m_nCount) ); } return TRUE; } BOOL Find(const char* sKey,objectType& obj) { if ( NULL == sKey || strlen(sKey) > HASH_MAX_STRING_LEN ) { return FALSE; } ULONG nHash = BkdrHashKey(sKey); nHash = nHash % m_nHashSize; LPAssoc pAssoc = m_pHashTable[nHash]; while( pAssoc ) { if ( 0 == strcmp(pAssoc.sKey,sKey) ) { obj = *(pAssoc->pData); return TRUE; } pAssoc = pAssoc->pNext; } return FALSE; } BOOL Containts(const char* sKey) { if ( NULL == sKey || strlen(sKey) > HASH_MAX_STRING_LEN ) { return FALSE; } ULONG nHash = BkdrHashKey(sKey); nHash = nHash % m_nHashSize; LPAssoc pAssoc = m_pHashTable[nHash]; while( pAssoc ) { if ( 0 == strcmp(pAssoc->sKey,sKey) ) return TRUE; pAssoc = pAssoc->pNext; } return FALSE; } void RemoveKey(const char* sKey) { if ( NULL == sKey ) return; ULONG nHash = BkdrHashKey(sKey)%m_nHashSize; LPAssoc pAssoc = m_pHashTable[nHash]; if ( pAssoc && strcmp(pAssoc->sKey,sKey) == 0 ) { m_pHashTable[nHash] = pAssoc->pNext; delete pAssoc->pData; delete pAssoc; m_nCount--; } else { LPAssoc pAssocPre = pAssoc; pAssoc = pAssoc->pNext; while( pAssoc ) { if ( strcmp(pAssoc->sKey,sKey) == 0 ) { pAssocPre->pNext = pAssoc->pNext; delete pAssoc->pData; delete pAssoc; m_nConflictCount--; break; } pAssocPre = pAssoc; pAssoc = pAssoc->pNext; } } } ULONG Size() { return m_nCount+m_nConflictCount; } void Clear() { LPAssoc pAssoc = NULL; LPAssoc pDelAssoc = NULL; for ( int i = 0;i < m_nHashSize;i++ ) { pAssoc = m_pHashTable[i]; while( pAssoc ) { pDelAssoc = pAssoc; pAssoc = pAssoc->pNext; delete pDelAssoc->pData; delete pDelAssoc; } m_pHashTable[i] = NULL; } m_nCount = 0; m_nConflictCount = 0; } iterator begin() { for ( ULONG i=0; i<m_nHashSize; i++ ) { if ( NULL != m_pHashTable[i] ) { return iterator(m_pHashTable[i],i,this); } } return iterator(NULL,0,this); } iterator end() { return iterator(NULL,0,this); } ULONG GetTableSize() { return m_nHashSize; } BOOL AutoIncrease() { return m_bAutoIncr; } protected: void ReSetTableSize(ULONG nSize) { LPAssoc* pNewAssocTable = new LPAssoc[nSize]; memset( pNewAssocTable,0,sizeof((LPAssoc*)pNewAssocTable) ); for ( ULONG i = 0;i < m_nHashSize;i++ ) { LPAssoc pOldAssoc = m_pHashTable[i]; while( NULL != pOldAssoc ) { ULONG nHash = BkdrHashKey(pOldAssoc->sKey)%nSize; if ( NULL == pNewAssocTable[nHash] ) { pNewAssocTable[nHash] = pOldAssoc; pNewAssocTable[nHash]->pNext = NULL; } else { LPAssoc pAssocTemp = pNewAssocTable[nHash]; while( NULL != pAssocTemp->pNext ) pAssocTemp = pAssocTemp->pNext; pAssocTemp->pNext = pOldAssoc; pAssocTemp->pNext->pNext = NULL; } pOldAssoc = pOldAssoc->pNext; } } delete[] m_pHashTable; m_pHashTable = pNewAssocTable; m_nHashSize = nSize; } void InitMap(ULONG nSize) { m_nHashSize = AdjustSize(nSize); if ( m_pHashTable ) { delete[] m_pHashTable; m_pHashTable = NULL; } m_pHashTable = new LPAssoc[m_nHashSize]; memset(m_pHashTable,0,sizeof(LPAssoc)*m_nHashSize ); } ULONG AdjustSize(ULONG nSize) { // 注意：如果 long 至少有 32 bits。

//定义28个素数（大概是2倍关系增长），用来做hash table的大小 const ULONG size_list[] = { 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786443, 1572869, 3145739, 6291469, 12582917, 25165842, 50331553, 100663319, 201326611, 402653189, 805306457, 1610612741, 3221225473ul, 4294967291ul }; int nlistsize = sizeof(size_list) / sizeof(ULONG); int i = 0; for (;i<nlistsize;i++) { if ( size_list[i] >= nSize ) break; } if ( i == nlistsize ) i--; return size_list[i]; } ULONG BkdrHashKey(const char* key) { if (1) { char* str = const_cast<char*>(key); unsigned int seed = 31; // 31 131 1313 13131 131313 etc.. 37 unsigned int hash = 0; while (*str) { hash = hash * seed + (*str++); } return (hash & 0x7FFFFFFF); } if ( NULL == key ) return 0; ULONG nHash = 0; while (*key) nHash = (nHash<<5) + nHash + *key++; return nHash; } protected: ULONG m_nHashSize; //哈希表大小 ULONG m_nCount; //哈希表中当前元素个数 ULONG m_nConflictCount; //哈希表中冲突的个数 LPAssoc* m_pHashTable; //哈希表头指针 BOOL m_bAutoIncr; //是否自己主动调整表大小 };

转载于:https://www.cnblogs.com/bhlsheji/p/5101268.html

相关资源：数据结构—成绩单生成器