正文
php Hash Table(二) Hash函数
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
哈希表最关键的几个方面有：
- 通过key访问（通过哈希函数计算出key）
- 映射到数据结构中（哈希表本身的存储结构）
- 映射的处理（冲突或者碰撞检测和处理函数）
理解PHP的哈希算法
一般来说对于整形索引进行哈希我们很容易想到的是取模运算，比如array(1=>'a', 2=>'b', 3=>'c')，这类我们可以使用index%3来哈希，不过PHP数组的下标还有更灵活的array('a'='c', 'b'=>'d')，此时选择什么哈希函数？答案是DJBX33A算法。
PS：DJBX33A算法，也就是time33算法，是APR默认哈希算法，php, apache, perl, bsddb也都使用time33哈希。对于33这个数，DJB注释中是说，1到256之间的所有奇数，都能达到一个可接受的哈希分布，平均分布大概是86%。而其中33，17，31，63，127，129这几个数在面对大量的哈希运算时有一个更大的优势，就是这些数字能将乘法用位运算配合加减法替换，这样运算速度会更高。gcc编译器开启优化后会自动将乘法转换为位运算。
下面就是这个哈希函数的具体代码实现：
更详细的解释看鸟哥：http://www.laruence.com/2009/07/23/994.html
static inline ulong zend_inline_hash_func(char *arKey, uint nKeyLength){
register ulong hash = ; /* variant with the hash unrolled eight times */
for (; nKeyLength >= ; nKeyLength -= ） {
hash = ((hash << ) + hash) + *arKey++;
hash = ((hash << ) + hash) + *arKey++;
hash = ((hash << ) + hash) + *arKey++;
hash = ((hash << ) + hash) + *arKey++;
hash = ((hash << ) + hash) + *arKey++;
hash = ((hash << ) + hash) + *arKey++;
hash = ((hash << ) + hash) + *arKey++;
hash = ((hash << ) + hash) + *arKey++;
}
switch (nKeyLength) {
case : hash = ((hash << ) + hash) + *arKey++; /* fallthrough... */
case : hash = ((hash << ) + hash) + *arKey++; /* fallthrough... */
case : hash = ((hash << ) + hash) + *arKey++; /* fallthrough... */
case : hash = ((hash << ) + hash) + *arKey++; /* fallthrough... */
case : hash = ((hash << ) + hash) + *arKey++; /* fallthrough... */
case : hash = ((hash << ) + hash) + *arKey++; /* fallthrough... */
case : hash = ((hash << ) + hash) + *arKey++; break;
case : break;
EMPTY_SWITCH_DEFAULT_CASE()
}
return hash;
}
nTableMask
PHP哈希表最小容量是8（2^3），最大容量是0x80000000（2^31），并向2的整数次幂圆整（即长度会自动扩展为2的整数次幂，如13个元素的哈希表长度为16；100个元素的哈希表长度为128）。nTableMask被初始化为哈希表长度（圆整后）减1。
哈希表的掩码数值等于 nTableSize-1，他的作用是什么？用来纠正通过DBJ算法计算的哈希值在当前nTableSize大小的哈希表中的正确的索引值。比 如"foo"通过固定算法之后得出的哈希值是193491849，如果表的大小为64，很明显已经超过了最大索引值，这时候就需要运用哈希表的掩码对其进 行矫正实际采用的方法就是与掩码进行位与运算，这样做是为了把哈希值大的一样映射到nTalbeSize空间内。
hash | 193491849 | 0b1011100010000111001110001001
& mask | & 63 | & 0b0000000000000000000000111111
---------------------------------------------------------
= index | = 9 | = 0b0000000000000000000000001001
具体代码在zend/Zend_hash.c的_zend_hash_init函数中，这里截取与本文相关的部分并加上少量注释。
ZEND_API int _zend_hash_init(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC)
{
uint i = ;
Bucket **tmp; SET_INCONSISTENT(HT_OK); //长度向2的整数次幂圆整
if (nSize >= 0x80000000) {
/* prevent overflow */
ht->nTableSize = 0x80000000;
} else {
while ((1U << i) < nSize) {
i++;
}
ht->nTableSize = << i;
} ht->nTableMask = ht->nTableSize - ; /*此处省略若干代码…*/ return SUCCESS;
}
Zend HashTable的哈希算法比较简单：
hash(key)=key & nTableMask
即简单将数据的原始key与HashTable的nTableMask进行按位与即可。
如果原始key为字符串，则首先使用Times33算法将字符串转为整形再与nTableMask按位与。
hash(strkey)=time33(strkey) & nTableMask
下面是Zend源码中查找哈希表的代码：
ZEND_API int zend_hash_index_find(const HashTable *ht, ulong h, void **pData)
{
uint nIndex;
Bucket *p; IS_CONSISTENT(ht); nIndex = h & ht->nTableMask; p = ht->arBuckets[nIndex];
while (p != NULL) {
if ((p->h == h) && (p->nKeyLength == )) {
*pData = p->pData;
return SUCCESS;
}
p = p->pNext;
}
return FAILURE;
} ZEND_API int zend_hash_find(const HashTable *ht, const char *arKey, uint nKeyLength, void **pData)
{
ulong h;
uint nIndex;
Bucket *p; IS_CONSISTENT(ht); h = zend_inline_hash_func(arKey, nKeyLength);
nIndex = h & ht->nTableMask; p = ht->arBuckets[nIndex];
while (p != NULL) {
if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
if (!memcmp(p->arKey, arKey, nKeyLength)) {
*pData = p->pData;
return SUCCESS;
}
}
p = p->pNext;
}
return FAILURE;
}
其中zend_hash_index_find用于查找整数key的情况，zend_hash_find用于查找字符串key。逻辑基本一致，只是字符串key会通过zend_inline_hash_func转为整数key，zend_inline_hash_func封装了times33算法。
哈希冲突的处理
关于哈希冲突，PHP的实现是通过拉链法实现的，当键值被哈希到同一个槽位（bucket）就是发生了冲突，这时候会从bucket拉出一个链表把冲突的元素顺序链接起来。
关于那两对指针，国外有网站上搞错了，这里把检测哈希冲突的PHP函数贴出来，pNext指针的作用就一目了然了。
ZEND_API int zend_hash_exists(const HashTable *ht, const char *arKey, uint nKeyLength)
{
ulong h;
uint nIndex;
Bucket *p; IS_CONSISTENT(ht); h = zend_inline_hash_func(arKey, nKeyLength);
nIndex = h & ht->nTableMask; p = ht->arBuckets[nIndex];
while (p != NULL) {
if (p->arKey == arKey ||
((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) {
return ;
}
p = p->pNext;
}
return ;
}
