在分析PHP中HashTable实现原理之前，先介绍一下相关的基本概念：

如下图例子，希望通过人名检索一个数据，键名通过哈希函数，得到指向bucket的指针，最后访问真实的bucket。

键名(Key)：在哈希函数转换前，数据的标识。

桶(Bucket)：在哈希表中，真正保存数据的容器。

哈希函数(Hash Function)：将Key通过哈希函数，得到一个指向bucket的指针。MD5，SHA-1是我们在业务中常用的哈希函数。

哈希冲突(Hash Collision)：两个不同的Key，经过哈希函数，得到同一个bucket的指针。

现在我们来看一下PHP中的哈希表结构

//Zend/zend_hash.h

typedef struct _hashtable {
uint nTableSize; //哈希表的长度，不是元素个数
uint nTableMask; //哈希表的掩码，设置为nTableSize-1
uint nNumOfElements; //哈希表实际元素个数
ulong nNextFreeElement; //指向下一个空元素位置
Bucket *pInternalPointer; //用于遍历哈希表的内部指针
Bucket *pListHead; //哈希表队列的头部
Bucket *pListTail; //哈希表队列的尾部
Bucket **arBuckets; //哈希表存储的元素数组
dtor_func_t pDestructor; //哈希表的元素析构函数指针
zend_bool persistent; //是否是持久保存，用于pmalloc的参数，可以持久存储在内存中
unsigned char nApplyCount; // zend_hash_apply的次数，用来限制嵌套遍历的层数，限制为3层
zend_bool bApplyProtection; //是否开启嵌套遍历保护
#if ZEND_DEBUG
int inconsistent; //debug字段，查看哈希表的操作记录
#endif
} HashTable;

typedef struct bucket {
ulong h; //数组索引的哈希值
uint nKeyLength; //索引数组为0，关联数组为key的长度
void *pData; //元素内容的指针
void *pDataPtr; // 如果是指针大小的数据，用pDataPtr直接存储，pData指向pDataPtr
struct bucket *pListNext; //哈希链表中下一个元素
struct bucket *pListLast; //哈希链表中上一个元素
struct bucket *pNext; //解决哈希冲突，变为双向链表，双向链表的下一个元素
struct bucket *pLast; //解决哈希冲突，变为双向链表，双向链表的上一个元素
const char *arKey; //最后一个元素key的名称
} Bucket;

哈希表的常用操作函数，内核使用宏定义来方便我们的操作

//初始化哈希表
#define zend_hash_init(ht, nSize, pHashFunction, pDestructor, persistent) _zend_hash_init((ht), (nSize), (pDestructor), (persistent) ZEND_FILE_LINE_CC)
ht 指向哈希表的指针，通常我们可以这样定义哈希表，HashTable *ht;ALLOC_HASHTABLE(ht);
nSize 哈希表的数量，哈希表总是以2N次递增的，所以实际的数量会大于你传递的数量
pHashFunction 这是早期用到的一个参数，用来定义一个hash函数，现在全部改成默认的DJBX33A算法计算哈希值，只是为了兼容才保留了参数，我们传NULL即可
pDestructor 是一个回调函数，当我们删除或修改hashtable表中的一个元素时便会调用改函数
persistent 是一个标识位，是否在内存中永久保存ht指向的哈希表。可以使用1或0两个值，显然1表示永久保存

//更新哈希表的关联数组值
#define zend_hash_update(ht, arKey, nKeyLength, pData, nDataSize, pDest) \
_zend_hash_add_or_update(ht, arKey, nKeyLength, pData, nDataSize, pDest, HASH_UPDATE ZEND_FILE_LINE_CC)
ht 同上
arKey 字符索引的key值
nKeyLength key长度
pData 字符数组保存的值
nDataSize sizeof(pData)的值
pDest 如果不为NULL，则*pDest=pData;

//插入哈希表的关联数组数据 
#define zend_hash_add(ht, arKey, nKeyLength, pData, nDataSize, pDest) \
_zend_hash_add_or_update(ht, arKey, nKeyLength, pData, nDataSize, pDest, HASH_ADD ZEND_FILE_LINE_CC)
参数同上
//更新索引数组
#define zend_hash_index_update(ht, h, pData, nDataSize, pDest) \
_zend_hash_index_update_or_next_insert(ht, h, pData, nDataSize, pDest, HASH_UPDATE ZEND_FILE_LINE_CC)
h 数字索引值
其余参数同上
//插入索引数组
#define zend_hash_next_index_insert(ht, pData, nDataSize, pDest) \
_zend_hash_index_update_or_next_insert(ht, , pData, nDataSize, pDest, HASH_NEXT_INSERT ZEND_FILE_LINE_CC)
参数同上

哈希表的ＡＰＩ

int zend_hash_init(HashTable* ht, uint size, hash_func_t hash, dtor_func_t destructor, zend_bool persistent)
int zend_hash_add(HashTable* ht, const char* key, uint klen, void* data, uint dlen, void** dest)
int zend_hash_update(HashTable* ht, const char* key, uint klen, void* data, uint dlen, void** dest)
int zend_hash_find(HashTable* ht, const char* key, uint klen, void** data)
zend_bool zend_hash_exists(HashTable* ht, const char* key, uint klen)
int zend_hash_del(HashTable* ht, const char* key, uint klen)
int zend_hash_index_update(HashTable* ht, ulong index, void* data, uint dsize, void** dest)
int zend_hash_index_del(HashTable* ht, ulong index)
int zend_hash_index_find(HashTable* ht, ulong index, void** data)
int zend_hash_index_exists(HashTable* ht, ulong index)ulong zend_hash_next_free_element(HashTable* ht)

哈希表的遍历API

HashTable Traversal API
int zend_hash_internal_pointer_reset(HashTable* ht)
resets the internal pointer of ht to the start
int zend_hash_internal_pointer_reset_ex(HashTable* ht, HashPosition position)
sets position the the start of ht
int zend_hash_get_current_data(HashTable* ht, void* data)
gets the data at the current position in ht, data should be cast to void**, ie: (void**) &data
int zend_hash_get_current_data_ex(HashTable* ht, void* data, HashPosition position)
sets data to the data at position in ht
int zend_hash_get_current_key(HashTable* ht, void* data, char**key, uint klen, ulong index, zend_bool duplicate)
sets key, klen, and index from the key information at the current position. The possible return values HASH_KEY_IS_STRING and HASH_KEY_IS_LONG are indicative of the kind of key found at the current posision.
int zend_hash_get_current_key_ex(HashTable* ht, void* data, char**key, uint klen, ulong index, zend_bool duplicate, HashPosition position)
sets key, klen, and index from the key information at position. The possible return values HASH_KEY_IS_STRING and HASH_KEY_IS_LONG are indicative of the kind of key found at position.
int zend_hash_move_forward(HashTable* ht)
moves the internal pointer of ht to the next entry in ht
int zend_hash_move_forward_ex(HashTable* ht, HashPosition position)
moves position to the next entry in ht

通过一个例子来使用上面的API函数

PHP_FUNCTION(myext_example_hashtable);//php_myext.h申明

PHP_FE(myext_example_hashtable, NULL)//函数注册

PHP_FUNCTION(myext_example_hashtable){
php_printf("init\n");
HashTable *myht;
ALLOC_HASHTABLE(myht);
int nSize = ;
zend_hash_init(myht, nSize, NULL, NULL, );//哈希函数和析构函数都为NULL
char *key1 = "key1";
int nKeyLength = sizeof(key1);
zval * value1;
MAKE_STD_ZVAL(value1);
ZVAL_STRING(value1,"value1",);
zval * value2;
MAKE_STD_ZVAL(value2);
ZVAL_STRING(value2,"value2",);
int ret = zend_hash_add(myht, key1, nKeyLength+, &value1, sizeof(zval*),NULL);
printf("zend_hash_add,ret=>%d\n",ret);
ret = zend_hash_add(myht, key1, nKeyLength+, &value2, sizeof(zval*),NULL);
printf("add exist key , zend_hash_add,ret=>%d\n",ret);
ret = zend_hash_update(myht, key1, nKeyLength+, &value2, sizeof(zval*),NULL);
printf("update exist key , zend_hash_add,ret=>%d\n",ret);
ret = zend_hash_index_update(myht,,&value2,sizeof(zval*),NULL);
printf("zend_hash_index_update,ret=>%d\n",ret);
ret = zend_hash_next_index_insert(myht,&value2,sizeof(zval*),NULL);
printf("zend_hash_next_index_insert,ret=>%d\n",ret);

HashPosition position;  
zval \*\*data = NULL;

php\_printf("\\n");  
for (zend\_hash\_internal\_pointer\_reset\_ex(myht, &position);  
        zend\_hash\_get\_current\_data\_ex(myht, (void\*\*) &data, &position) == SUCCESS;  
        zend\_hash\_move\_forward\_ex(myht, &position)) {

    /\* by now we have data set and can use Z\_ macros for accessing type and variable data \*/

    char \*key = NULL;  
    uint  klen;  
    ulong index;

    if (zend\_hash\_get\_current\_key\_ex(myht, &key, &klen, &index, , &position) == HASH\_KEY\_IS\_STRING) {  
        /\* the key is a string, key and klen will be set \*/  
        php\_printf("string key %s =>",key);  
    } else {  
        /\* we assume the key to be long, index will be set \*/  
        php\_printf("index key %d =>",index);  
    }  
    if (Z\_TYPE\_PP(data) != IS\_STRING) {  
        convert\_to\_long(\*data);  
    }  
    PHPWRITE(Z\_STRVAL\_PP(data), Z\_STRLEN\_PP(data));  
    php\_printf("\\n");  
}

FREE\_ZVAL(value1);  
FREE\_ZVAL(value2);  
zend\_hash\_destroy(myht);  
FREE\_HASHTABLE(myht);  
RETURN\_NULL();  

}

还可以使用内核把哈希表封装成数组的方式使用，也就是zval类型里面的IS_ARRAY

array_init(arrval);

add_assoc_long(zval *arrval, char *key, long lval);
add_index_long(zval *arrval, ulong idx, long lval);
add_next_index_long(zval *arrval, long lval);

//add_assoc_*系列函数：
add_assoc_null(zval *aval, char *key);
add_assoc_bool(zval *aval, char *key, zend_bool bval);
add_assoc_long(zval *aval, char *key, long lval);
add_assoc_double(zval *aval, char *key, double dval);
add_assoc_string(zval *aval, char *key, char *strval, int dup);
add_assoc_stringl(zval *aval, char *key,char *strval, uint strlen, int dup);
add_assoc_zval(zval *aval, char *key, zval *value);

//备注：其实这些函数都是宏，都是对add_assoc_*_ex函数的封装。

//add_index_*系列函数：
ZEND_API int add_index_long (zval *arg, ulong idx, long n);
ZEND_API int add_index_null (zval *arg, ulong idx );
ZEND_API int add_index_bool (zval *arg, ulong idx, int b );
ZEND_API int add_index_resource (zval *arg, ulong idx, int r );
ZEND_API int add_index_double (zval *arg, ulong idx, double d);
ZEND_API int add_index_string (zval *arg, ulong idx, const char *str, int duplicate);
ZEND_API int add_index_stringl (zval *arg, ulong idx, const char *str, uint length, int duplicate);
ZEND_API int add_index_zval (zval *arg, ulong index, zval *value);

//add_next_index_long函数：
ZEND_API int add_next_index_long (zval *arg, long n );
ZEND_API int add_next_index_null (zval *arg );
ZEND_API int add_next_index_bool (zval *arg, int b );
ZEND_API int add_next_index_resource (zval *arg, int r );
ZEND_API int add_next_index_double (zval *arg, double d);
ZEND_API int add_next_index_string (zval *arg, const char *str, int duplicate);
ZEND_API int add_next_index_stringl (zval *arg, const char *str, uint length, int duplicate);
ZEND_API int add_next_index_zval (zval *arg, zval *value);