深入理解PHP内核(六)哈希表以及PHP的哈希表实现，深入理解

typedef struct _Bucket
{
    char *key;
    void *value;
    struct _Bucket *next;
 
} Bucket;
 
typedef struct _HashTable
{
    int size;
    Bucket* buckets;
} HashTable;

static int hash_str(char *key)
{
    int hash = 0;
 
    char *cur = key;
 
    while(*(cur++) != '\0') {
        hash += *cur;
    }
 
    return hash;
}
 
// —使用这个宏来求得key在哈希表中的索引
#define HASH_INDEX(ht, key) (hash_str((key)) % (ht)->size)

int hash_init(HashTable *ht);                               // 初始化哈希表
int hash_lookup(HashTable *ht, char *key, void **result);   // 根据key查找内容
int hash_insert(HashTable *ht, char *key, void *value);     // 将内容插哈希表中
int hash_remove(HashTable *ht, char *key);                  // 删除key所指向的内容
int hash_destroy(HashTable *ht);

int hash_insert(HashTable *ht, char *key, void *value)
{
    // check if we need to resize the hashtable
    resize_hash_table_if_needed(ht);    // 哈希表不固定大小，当插入的内容快占满哈希表的存储空间
                                        // 将对哈希表进行扩容，以便容纳所有的元素
    int index = HASH_INDEX(ht, key);    // 找到key所映射到的索引
 
    Bucket *org_bucket = ht->buckets[index];
    Bucket *bucket = (Bucket *)malloc(sizeof(Bucket)); // 为新元素申请空间
 
    bucket->key   = strdup(key);
    // 将值内容保存起来，这里只是简单的将指针指向要存储的内容，而没有将内容复制
    bucket->value = value;  
 
    LOG_MSG("Insert data p: %p\n", value);
 
    ht->elem_num += 1; // 记录一下现在哈希表中的元素个数
 
    if(org_bucket != NULL) { // 发生了碰撞，将新元素放置在链表的头部
        LOG_MSG("Index collision found with org hashtable: %p\n", org_bucket);
        bucket->next = org_bucket;
    }
 
    ht->buckets[index]= bucket;
 
    LOG_MSG("Element inserted at index %i, now we have: %i elements\n",
        index, ht->elem_num);
 
    return SUCCESS;
}

int hash_lookup(HashTable *ht, char *key, void **result)
{
    int index = HASH_INDEX(ht, key);
    Bucket *bucket = ht->buckets[index];
     if(bucket == NULL) return FAILED;
 
    // 查找这个链表以便找到正确的元素，通常这个链表应该是只有一个元素的，也就不同多次循环
    // 要保证这一点需要有一个合适的哈希算法。
    while(bucket)
    {
        if(strcmp(bucket->key, key) == 0)
        {
            LOG_MSG("HashTable found key in index: %i with  key: %s value: 
%p\n",
                index, key, bucket->value);
            *result = bucket->value;    
            return SUCCESS;
        }
 
        bucket = bucket->next;
    }
 
    LOG_MSG("HashTable lookup missed the key: %s\n", key);
    return FAILED;
}

typedef struct _hashtable { 
    uint nTableSize;        // hash Bucket的大小，最小为8，以2x增长
    uint nTableMask;        // nTableSize-1,索引取值的优化
    uint nNumOfElements;    // hash Bucket中当前存在的元素个数，count()函数会直接返回此值
    ulong nNextFreeElement; // 下一个数字索引的位置
    Bucket *pInternalPointer;   // 当前遍历的指针(foreach 比for快的原因之一)
    Bucket *pListHead;          // 存储数头元素指针
    Bucket *pListTail;          // 存储数组尾元素指针
    Bucket **arBuckets;         // 存储hash数组
    dtor_func_t pDestructor;
    zend_bool persistent;
    unsigned char nApplyCount; // 标记当前hash Bucket被递归访问的次数(防止多次递归)
    zend_bool bApplyProtection;// 标记当前hash桶允许不允许多次访问，不允许时，最多只能递归3此
#if ZEND_DEBUG
    int inconsistent;
#endif
} HashTable;

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;
    //...
    if (nSize >= 0x80000000) {
        /* prevent overflow */
        ht->nTableSize = 0x80000000;
    } else {
        while ((1U << i) < nSize) {
            i++;
        }
        ht->nTableSize = 1 << i;
    }
    // ...
    ht->nTableMask = ht->nTableSize - 1;
 
    /* Uses ecalloc() so that Bucket* == NULL */
    if (persistent) {
        tmp = (Bucket **) calloc(ht->nTableSize, sizeof(Bucket *));
        if (!tmp) {
            return FAILURE;
        }
        ht->arBuckets = tmp;
    } else {
        tmp = (Bucket **) ecalloc_rel(ht->nTableSize, sizeof(Bucket *));
        if (tmp) {
            ht->arBuckets = tmp;
        }
    }
 
    return SUCCESS;
}

h = zend_inline_hash_func(arKey, nKeyLength);
nIndex = h & ht->nTableMask;

<?php
$a = array(10 => 'Hello');
$a[] = 'TIPI';
var_dump($a);
 
// ouput
array(2) {
  [10]=>
  string(5) "Hello"
  [11]=>
  string(5) "TIPI"
}

typedef struct bucket {
    ulong h;            // 对char *key进行hash后的值，或者是用户指定的数字索引值
    uint nKeyLength;    // hash关键字的长度，如果数组索引为数字，此值为0
    void *pData;        // 指向value，一般是用户数据的副本，如果是指针数据，则指向pDataPtr
    void *pDataPtr;     // 如果是指针数组，此值会指向真正的value，同时上面pData会指向此值
    struct bucket *pListNext;   // 整个hash表的下一个元素
    struct bucket *pListLast;   // 整个hash表的上一个元素
    struct bucket *pNext;       // 存放在同一个hash Bucket内的下一个元素
    struct bucket *pLast;       // 存放在同一个hash Bucket内的上一个元素
    char arKey[1];  
    /*
    存储字符索引，此项必须放在最末尾，因为此处只定义了1个字节，存储的实际上是指向char *key的值，
    这就意味着可以省去再赋值一次的消耗，而且，有时此值并不需要，所以同时还节省了空间。
    */
} Bucket;