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 = 5381;     /* variant with the hash unrolled eight times */    
    for (; nKeyLength >= 8; nKeyLength -= 8） {        
        hash = ((hash << 5) + hash) + *arKey++;        
        hash = ((hash << 5) + hash) + *arKey++;        
        hash = ((hash << 5) + hash) + *arKey++;        
        hash = ((hash << 5) + hash) + *arKey++;        
        hash = ((hash << 5) + hash) + *arKey++;        
        hash = ((hash << 5) + hash) + *arKey++;        
        hash = ((hash << 5) + hash) + *arKey++;        
        hash = ((hash << 5) + hash) + *arKey++;    
    }
    switch (nKeyLength) {        
        case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */        
        case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */        
        case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */        
        case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */        
        case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */        
        case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */        
        case 1: hash = ((hash << 5) + hash) + *arKey++; break;        
        case 0: 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 = 3;
    Bucket **tmp;

    SET_INCONSISTENT(HT_OK);

    //长度向2的整数次幂圆整
    if (nSize >= 0x80000000) {
        /* prevent overflow */
        ht->nTableSize = 0x80000000;
    } else {
        while ((1U << i) < nSize) {
            i++;
        }
        ht->nTableSize = 1 << i;
    }

    ht->nTableMask = ht->nTableSize - 1;

    /*此处省略若干代码…*/

    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 == 0)) {
            *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 1;
        }
        p = p->pNext;
    }
    return 0;
}