PHP与Python实现Hash比较（一）

PHP中的array，python中的dict都是通过hash表(哈希表或散列表)实现的，或者说array与dict本身就是hash结构，本文及后续文章将分别比较PHP与python源代码中对哈希表的实现算法，一来学习其设计思想，另外可用于避免开发过程中一些可能会降低效率或易引发bug的

PHP中的array，python中的dict都是通过hash表(哈希表或散列表)实现的，或者说array与dict本身就是hash结构，本文及后续文章将分别比较PHP与python源代码中对哈希表的实现算法，一来学习其设计思想，另外可用于避免开发过程中一些可能会降低效率或易引发bug的操作。

先来PHP。一切源于PHP的内置数据类型zval(见PHP_X_X/Zend/zend.h):

typedef union _zvalue_value {
    long lval;                  //long value
    double dval;                //double value
    struct {
        char *val;
        int len;
    } str;
    HashTable *ht;              //hash table value
    zend_object_value obj;
} zvalue_value;
struct _zval_struct {
    //Variable information
    zvalue_value value;     //value
    zend_uint refcount_gc;
    zend_uchar type;    //active type
    zend_uchar is_ref_gc;
};

其中HashTable *ht即是PHP中用于表示Array类型的结构，在深究HashTable结构之前先了解哈希表的原理，在C语言中数组是通过自然数作为数组索引来存储数据的，而在PHP或python等这些语言中，哈希表是以key - value的方式存取的，要实现这一存储方式，则需要将任意可能的key对应或映射到数组或者内存的自然数序列索引上，即实现

index = hash(key)

hash()即为哈希函数。理想状态下的hash()可以将任意的key映射到均匀分布且不重叠的自然数集合中，但由于key的不确定性，这显然是不可能的，因而一个好的哈希函数应该可以尽可能地避免重叠或碰撞(collisions)，而在PHP中实现这一功能的哈希函数采纳的是DJBX33A算法。源码中实现代码如下：

static inline ulong zend_inline_hash_func(const char *arKey, uint nKeyLength)
{
    register ulong hash = 5381;
    /* variant with the hash unrolled eight times */
    for (; nKeyLength >= 8; nKeyLength -= 8) {
        hash = ((hash 
<p>据其注释中所解释的来看，DJBX33A (Daniel J. Bernstein, Times 33 with Addition)算法可简单描述为</p>
<blockquote>
<p>hash(i) = hash(i-1) * 33 + str[i]</p>
</blockquote>
<p>至于为何取33而不是其它数，解释说是对1 ~ 256进行分别进行测试后择优选择的结果，并没有理论上的支撑，而且初始的hash值为5381应该也没有什么特别特别的特别之处吧？到这里为止，首先可以确定的一条规则就是，<span style="color: #3498db">在PHP中定义使用数组时key的长度以最好不要超过7为妙</span>，便可省掉第一步的for循环，因而在考虑效率的前提下，道长当年所说的为了增加代码的可读性将变量名定为几十个字符甚至一句话显然是不可取的咯:P</p>
<p>通过巧妙的算法，hash碰撞得以减少，但是并没有完全避免(例如：PHP哈希表碰撞攻击原理），既然冲突是不可避免的，那就只能想办法解决冲突，算法书里面对冲突的处理方案有很多，PHP采用的是拉链法，具体实现方法还是要先追寻其定义(见PHP_X_X/Zend/zend_hash.h)：</p>
<p class="highlight"></p><pre class="brush:php;toolbar:false">typedef struct bucket {
    ulong h;                        //Used for numeric indexing
    uint nKeyLength;
    void *pData;
    void *pDataPtr;
    struct bucket *pListNext;
    struct bucket *pListLast;
    struct bucket *pNext;
    struct bucket *pLast;
    const char *arKey;
} Bucket;
typedef struct _hashtable {
    uint nTableSize;
    uint nTableMask;
    uint nNumOfElements;
    ulong nNextFreeElement;
    Bucket *pInternalPointer;   //Used for element traversal
    Bucket *pListHead;
    Bucket *pListTail;
    Bucket **arBuckets;
    dtor_func_t pDestructor;
    zend_bool persistent;
    unsigned char nApplyCount;
    zend_bool bApplyProtection;
#if ZEND_DEBUG
    int inconsistent;
#endif
} HashTable;

最终hash表的key保存在Bucket.arKey，key长为Bucket.nKeyLength，哈希函数计算得到的哈希值存为Bucket.h，当冲突时通过引出一条静态链表来解决，其实现如下：

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;
}

p = p->pNext即在已有元素之上开辟出新的位置存储冲突的下一个元素。至此，PHP中HashTable实现的基本思想就介绍完了，有空再把python的部分补上。

构建动态结构体的小trick

Bucket结构体的最后一个元素arKey被定义为char *arKey;也有看到char arKey[1]，有人解释说利用变长结构体，加上有看到注释

char arKey[1]; /* Must be last element */

更是如坠云里雾里，还以为说 arKey 必须存放 HashTable 里面 key 字符串的最后一个字符…经过一番挣扎，发现原来不是这个意思，shit！(见what-is-your-favorite-c-programming-trick)，所谓的变长结构体只是说在考虑到内存连续性条件下，为了实现结构体内部元素的动态分配，利用struct的性质，将需要动态分配的变量放在结构体最后，如此以来通过malloc动态分配给struct的内存超出结构体本身所需的部分sizeof(struct)可以顺其自然地被最后一个元素所访问，从而实现了可变长的结构体，所以说，注释中的Must be last element不是说存放的是key的最后一个字符，而是必须放在结构体的最后一个元素！shit again(but a good trick:P)!

参考

1. PHP哈希表结构的深入剖析

原文地址：PHP与Python实现Hash比较（一）, 感谢原作者分享。