PHP 7内核之HashTable实现

作者：wj （360电商技术）

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

-------------------------------------------------------------------------------------

黑夜路人，一个关注开源技术、乐于学习、喜欢分享的程序员

博客：http://blog.csdn.net/heiyeshuwu

微博：http://weibo.com/heiyeluren

微信：heiyeluren2012

想获取更多IT开源技术相关信息，欢迎关注微信！

微信二维码扫描快速关注本号码：

​