PHP7的HashTable实现
PHP开发的主干已经切换到大版本7了，这个版本Zend引擎改变很大，可以说是一个全新的版本，因此新的Zend引擎被命名为NG。在这个大版本中变量以及hash表变动也很大。所以在这里把自己的学习过程和成果记录下来，毕竟好记性不如烂笔头啊。
数据结构
HashTable的结构定义在Zend/zend_types.h，之前的php版本中被定义在Zend/Zend_hash.h文件中。
HashTable中的每一个元素都被保存在一个Bucket结构中，新的结构定义如下：
typedef struct _Bucket {
zval val;
zend_ulong h; /* hash value (or numeric index) */
zend_string *key; /* string key or NULL for numerics */
} Bucket;
新的Bucket的结构已经相当简洁了，不像原来的里面还有链表指针什么的。HashTable的结构定义如下：
typedef struct _HashTable {
union {
struct {
ZEND_ENDIAN_LOHI_3(
zend_uchar flags,
zend_uchar nApplyCount, /* 循环遍历保护 */
uint16_t reserve)
} v;
uint32_t flags;
} u;
uint32_t nTableSize; /* hash表的大小 */
uint32_t nTableMask; /* 掩码,用于根据hash值计算存储位置,永远等于nTableSize-1 */
uint32_t nNumUsed; /* arData数组已经使用的数量 */
uint32_t nNumOfElements; /* hash表中元素个数 */
uint32_t nInternalPointer; /* 用于HashTable遍历 */
zend_long nNextFreeElement; /* 下一个空闲可用位置的数字索引 */
Bucket *arData; /* 存放实际数据 */
uint32_t *arHash; /* Hash表 */
dtor_func_t pDestructor; /* 析构函数 */
} HashTable;
创建HashTable
创建一个HashTable有很多途径，但是最终调用的都是_zend_hash_init函数，下面是这个函数的实现,我们省掉windows的实现部分
ZEND_API void _zend_hash_init(HashTable *ht, uint32_t nSize, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC)
{
...
/* size should be between 8 and 0x80000000 */
nSize = (nSize <= 8 ? 8 : (nSize >= 0x80000000 ? 0x80000000 : nSize));
# if defined(__GNUC__)
ht->nTableSize = 0x2 << (__builtin_clz(nSize - 1) ^ 0x1f);
# else
nSize -= 1;
nSize |= (nSize >> 1);
nSize |= (nSize >> 2);
nSize |= (nSize >> 4);
nSize |= (nSize >> 8);
nSize |= (nSize >> 16);
ht->nTableSize = nSize + 1;
# endif
ht->nTableMask = 0;
ht->nNumUsed = 0;
ht->nNumOfElements = 0;
ht->nNextFreeElement = 0;
ht->arData = NULL;
ht->arHash = (uint32_t*)&uninitialized_bucket;
ht->pDestructor = pDestructor;
ht->nInternalPointer = INVALID_IDX;
ht->u.flags = (persistent ? HASH_FLAG_PERSISTENT : 0) | HASH_FLAG_APPLY_PROTECTION;
}
pDestructor是HashTable元素的析构指针，在更新/销毁HashTable中的元素时候会使用。上面的一系列得nSize的计算只是为了得到一个大于等于原始nSize的2的整数次幂的最小值,在这里并没有初始化arData，它会在使用HashTable的时候来创建。
操作HashTable
添加更新元素
在新的实现中，将以前的最底层添加和更新元素的api_zend_hash_add_or_update变成了现在的_zend_hash_add_or_update_i，其他的对HashTable的新增和更新的操作全部是基于_zend_hash_add_or_update_i实现的宏。下面是_zend_hash_add_or_update_i的实现：
static zend_always_inline zval *_zend_hash_add_or_update_i(HashTable *ht, zend_string *key, zval *pData, uint32_t flag ZEND_FILE_LINE_DC)
{
zend_ulong h;
uint32_t nIndex;
uint32_t idx;
Bucket *p;
IS_CONSISTENT(ht);
if (UNEXPECTED(!(ht->u.flags & HASH_FLAG_INITIALIZED))) { /* 检查hashtable是否初始化 */
CHECK_INIT(ht, 0);
goto add_to_hash;
} else if (ht->u.flags & HASH_FLAG_PACKED) { /* ? */
zend_hash_packed_to_hash(ht);
} else if ((flag & HASH_ADD_NEW) == 0) { /* 新增 */
p = zend_hash_find_bucket(ht, key); /* 根据key查是否已经存在 */
if (p) { /* 当前的key已经存在 */
zval *data;
if (flag & HASH_ADD) { /* key已经存在产生添加冲突，退出 */
return NULL;
}
ZEND_ASSERT(&p->val != pData); /* key存在的情况下，值不一样做更新操作 */
data = &p->val;
if ((flag & HASH_UPDATE_INDIRECT) && Z_TYPE_P(data) == IS_INDIRECT) {
data = Z_INDIRECT_P(data);
}
HANDLE_BLOCK_INTERRUPTIONS();
if (ht->pDestructor) {
ht->pDestructor(data); /* 释放掉原来的data */
}
ZVAL_COPY_VALUE(data, pData); /* 将新的pData值复制给原来的data */
HANDLE_UNBLOCK_INTERRUPTIONS();
return data;
}
}
ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* If the Hash table is full, resize it */
add_to_hash:
HANDLE_BLOCK_INTERRUPTIONS();
idx = ht->nNumUsed++; /* 已使用计数+1，并且用老的位置来做为索引 */
ht->nNumOfElements++; /* 元素个数加1 */
if (ht->nInternalPointer == INVALID_IDX) {
ht->nInternalPointer = idx;
}
p = ht->arData + idx; /* 指针加法移位 */
p->h = h = zend_string_hash_val(key); /* 计算key的hash值 */
p->key = key;
zend_string_addref(key);
ZVAL_COPY_VALUE(&p->val, pData);
nIndex = h & ht->nTableMask; /* 与tablemask进行计算得出hash索引 */
Z_NEXT(p->val) = ht->arHash[nIndex]; /* 新的元素的hash冲突链表的next指向当前冲突链表的首部元素 */
ht->arHash[nIndex] = idx; /* 新的元素放到当前hash冲突链表的头部 */
HANDLE_UNBLOCK_INTERRUPTIONS();
return &p->val;
}
#define Z_NEXT(zval) (zval).u2.next
从上面的api _zend_hash_add_or_update_i可以看出，其实更新操作很简单的，验证key是否存在，key存在的情况下如果值相等的话不做任何的操作，值不相同做更新操作。
这里比较重要的是hash表的新增，这里会涉及hash索引以及hash冲突链表。上面代码中的add_to_hash部分的代码主要就是在做这部分的做操。从上面的代码中可以看出，ht->arData 其实就是一个不定长的Bucket数组，它利用 ht->nNumUsed 来计算这个数组下一个空闲位置,然后将新的Bucket放到这个位置上。计算得到传入的key的hash值，然后与 ht->nTableMask 进行按位与得出新的bucket对应的 ht->arHash上的位置 ,这里就完成了hash表的构造。
但是还有个非常重要的地方，就是hash冲突的解决。hash冲突一直都是以一个链表来解决的，当出现hash冲突时候会将相同hash值的bucket连接成一个链表，然后进行查找时候是一个个的遍历，一个个的对比key值是否相同。和NG之前不同的是，现在的hash冲突链表被放到了 __zval_struct 结构中，而不是以前的Bucket里面。下面先是新老结构的对比
Old Bucket
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;
New Bucket
typedef struct _Bucket {
zval val;
zend_ulong h; /* hash value (or numeric index) */
zend_string *key; /* string key or NULL for numerics */
} Bucket;
从上面结构的对比可以看出，新的 _Bucket 只是一个单纯存储key以及value的结构了，而不承担以前的hash链表以及hash冲突链表的构建工作了。新的HashTable中，hash链表的构建工作由 HashTable->arHash 来承担，而解决hash冲突的链表则被放到了_zval_struct了。在新的实现当中，HashTable->arHash[] 会指向冲突链表的头，然后利用 _zval_struct.u2.next 来指向冲突链表中的下一个Bucket对应的 arHash 的位置。这样，现在的冲突链表俨然由原来的双向链表变成了现在的单向链表了。当新的冲突产生的时候，会将新的 Bucket 放入这个冲突链表的头部，然后让这个链表所对应的 arHash 的位置重新指向它，然后它的 _zval_struct.u2.next 指向原来的冲突链表头元素。就这样就构建好了一个冲突链表。
删除元素
Zend提供了一系列删除HashTable中元素的API，，定义如下：
ZEND_API int zend_hash_del(HashTable *ht, zend_string *key); ZEND_API int zend_hash_del_ind(HashTable *ht, zend_string *key); ZEND_API int zend_hash_str_del(HashTable *ht, const char *key, size_t len); ZEND_API int zend_hash_str_del_ind(HashTable *ht, const char *key, size_t len); ZEND_API int zend_hash_index_del(HashTable *ht, zend_ulong h);
接下来看看 zend_hash_del 的代码：
ZEND_API int zend_hash_del(HashTable *ht, zend_string *key)
{
zend_ulong h;
uint32_t nIndex;
uint32_t idx;
Bucket *p;
Bucket *prev = NULL;
IS_CONSISTENT(ht);
h = zend_string_hash_val(key); /* 根据key计算出hash值 */
nIndex = h & ht->nTableMask; /* 与nTableMask按位与计算出在hashtable中的位置 */
idx = ht->arHash[nIndex];
while (idx != INVALID_IDX) {
p = ht->arData + idx; /* 指针移位 */
if ((p->key == key) || /* 比较key值 */
(p->h == h &&
p->key &&
p->key->len == key->len &&
memcmp(p->key->val, key->val, key->len) == 0)) {
_zend_hash_del_el_ex(ht, idx, p, prev); /* 做实际删除动作的函数 */
return SUCCESS;
}
prev = p;
idx = Z_NEXT(p->val); /* 遍历hash冲突链表 */
}
return FAILURE;
}
上面的函数函数非常简单，就是进行hash查找，然后比较key值，最后调用函数 _zend_hash_del_el_ex 进行实际的删除动作，我们接下来看看 _zend_hash_del_el_ex d的代码实现：
static zend_always_inline void _zend_hash_del_el_ex(HashTable *ht, uint32_t idx, Bucket *p, Bucket *prev)
{
HANDLE_BLOCK_INTERRUPTIONS();
if (!(ht->u.flags & HASH_FLAG_PACKED)) { /* 非自然key序数组 */
if (prev) { /* 找到的元素不在hash冲突链表的首位，将它的前一个的next指针指向它的下一个元素 */
Z_NEXT(prev->val) = Z_NEXT(p->val);
} else { /* 找到的元素位于hash冲突链表的首位，将arHash对应的位置指向它的下一个元素 */
ht->arHash[p->h & ht->nTableMask] = Z_NEXT(p->val);
}
}
if (ht->nNumUsed - 1 == idx) { /* 元素位于arData数组的尾部 */
do {
ht->nNumUsed--;
} while (ht->nNumUsed > 0 && (Z_TYPE(ht->arData[ht->nNumUsed-1].val) == IS_UNDEF)); /* 循环自减，去掉删除当前元素后遗留的尾部的UNDEF元素 */
}
ht->nNumOfElements--; /* hash表中元素个数减1 */
if (ht->nInternalPointer == idx) {
while (1) {
idx++;
if (idx >= ht->nNumUsed) { /* 当idx指向的元素位于hash表最后一个元素时候，重置hash遍历指针为无效指针 */
ht->nInternalPointer = INVALID_IDX;
break;
} else if (Z_TYPE(ht->arData[idx].val) != IS_UNDEF) { /* 当前元素不在hash表最后，并且指向的元素是非UNDEF的，将hash遍历指针指向它 */
ht->nInternalPointer = idx;
break;
}
}
}
if (p->key) { /* 释放key */
zend_string_release(p->key);
}
if (ht->pDestructor) { /* 调用析构函数释放value的值 */
zval tmp;
ZVAL_COPY_VALUE(&tmp, &p->val);
ZVAL_UNDEF(&p->val);
ht->pDestructor(&tmp);
} else {
ZVAL_UNDEF(&p->val);
}
HANDLE_UNBLOCK_INTERRUPTIONS();
}
有一个注意的就是上面出现了一个宏 HASH_FLAG_PACKED 。根据鸟哥原话的解释：
表示一个自然key序的数组，就是可以随机访问的数组，就好比是C语言的数
array(1,2,3,4)，那么$arr[2]就是ht->arData[2]
array(1,2,3,4) packed / array(1 => 2, 3=> 2, 2=> 1) 非packed
个人理解就是自然排序(packed)就是Zend引擎自己生成的一个key，而不是程序员指定的。
清空HashTable
Zend提供了一个api来清空整个HashTable zend_hash_clean，下面是它的实现代码：
ZEND_API void zend_hash_clean(HashTable *ht)
{
Bucket *p, *end;
IS_CONSISTENT(ht);
if (ht->nNumUsed) { /* 非空HashTable */
p = ht->arData; /* 数组头 */
end = p + ht->nNumUsed; /* 数组尾 */
if (ht->pDestructor) {
if (ht->u.flags & HASH_FLAG_PACKED) { /* 自然key序数组 */
do {
if (EXPECTED(Z_TYPE(p->val) != IS_UNDEF)) {
ht->pDestructor(&p->val);
}
} while (++p != end); /* 循环遍历，挨个调用析构函数进行销毁 */
} else {
do {
if (EXPECTED(Z_TYPE(p->val) != IS_UNDEF)) {
ht->pDestructor(&p->val); /* 调用析构函数进行数据销毁 */
if (EXPECTED(p->key)) { /* 存在key，销毁key并释放内存 */
zend_string_release(p->key);
}
}
} while (++p != end); /* 循环遍历进行销毁 */
}
} else {
if (!(ht->u.flags & HASH_FLAG_PACKED)) { /* 非自然key序数组 */
do {
if (EXPECTED(Z_TYPE(p->val) != IS_UNDEF)) {
if (EXPECTED(p->key)) {
zend_string_release(p->key);
}
}
} while (++p != end); /* 循环遍历，挨个销毁key */
}
}
if (!(ht->u.flags & HASH_FLAG_PACKED)) { /* 非自然key序数组，重置arHash */
memset(ht->arHash, INVALID_IDX, ht->nTableSize * sizeof(uint32_t));
}
}
ht->nNumUsed = 0; /* arData计数置为0 */
ht->nNumOfElements = 0; /* hash表中元素个数置为0 */
ht->nNextFreeElement = 0; /* 下一个空闲可用位置的数字索引置为0 */
ht->nInternalPointer = INVALID_IDX; /* Hash遍历指针置为不可用 */
}
销毁HashTable
HashTable 的销毁是由 zend_hash_destroy 来负责的，实现如下：
ZEND_API void zend_hash_destroy(HashTable *ht)
{
Bucket *p, *end;
IS_CONSISTENT(ht);
if (ht->nNumUsed) {
p = ht->arData;
end = p + ht->nNumUsed;
if (ht->pDestructor) {
SET_INCONSISTENT(HT_IS_DESTROYING);
if (ht->u.flags & HASH_FLAG_PACKED) {
do {
if (EXPECTED(Z_TYPE(p->val) != IS_UNDEF)) {
ht->pDestructor(&p->val);
}
} while (++p != end);
} else {
do {
if (EXPECTED(Z_TYPE(p->val) != IS_UNDEF)) {
ht->pDestructor(&p->val);
if (EXPECTED(p->key)) {
zend_string_release(p->key);
}
}
} while (++p != end);
}
SET_INCONSISTENT(HT_DESTROYED);
} else {
if (!(ht->u.flags & HASH_FLAG_PACKED)) {
do {
if (EXPECTED(Z_TYPE(p->val) != IS_UNDEF)) {
if (EXPECTED(p->key)) {
zend_string_release(p->key);
}
}
} while (++p != end);
}
}
} else if (EXPECTED(!(ht->u.flags & HASH_FLAG_INITIALIZED))) {
return;
}
pefree(ht->arData, ht->u.flags & HASH_FLAG_PERSISTENT); /* 释放arData的内存 */
}
其实 zend_hash_destroy 和 zend_hash_clean 的实现很相近，释放元素的过程几乎一样，唯一的区别就是最后的工作，zend_hash_destroy 最后是将 arData 彻底释放了。
结尾
HashTable在PHP的内核中的地位非常重要，数组、作用域等都是靠HashTable来实现的，PHP数组设计的操作肯定不止这点，更多的操作还包括排序、rehash等。不过这些都是最普遍的增删改查。更多的实现请自行阅读PHP源码 zend_hash.c zend_hash.h