PHP7内核的HashTable的数据结构与实现

  1. HashTable
  2. 数据结构
  3. HashTable操作
    1. HashTable初始化
    2. 更新HashTable
    3. 更新元素
    4. 删除元素
    5. 清空HashTable
    6. 销毁HashTable
    7. 清空和销毁的区别
    8. 其他高级操作函数
  4. 参考

PHP7的中的HashTable变了,是的,进一步带来的就是相关操作方法在细节上的实现的不同,追其细节,就不得不对底层的方法逐个击破参透,从一个版本切换到另一个版本真是要伤透脑筋的活啊。

HashTable

即哈希表,又名散列表,是根据关键字(key value)直接访问在内存存储位置的数据结构。是一种将随机访问的数据结构转换为有序储存的数据结构。它通过把键值通过一个函数的计算,映射到表中一个位置来访问,此函数称为散列函数。现在很多高级程序语言中都有实现HashTable,而C语言中最常用的是uthashtable。

本文基于PHP 7.0.0 RC版本。

HashTable的结构有所变化,直接定义为了_zend_array,且从文件zend_hash.h移到了zend_types.h.

数据结构

typedef struct _zend_array HashTable;
struct _zend_array {
zend_refcounted gc;
union {
struct {
ZEND_ENDIAN_LOHI_4(
zend_uchar flags,
zend_uchar nApplyCount,
zend_uchar nIteratorsCount,
zend_uchar reserve)
} v;
uint32_t flags;
} u;
uint32_t nTableMask; /* 掩码,用于根据hash值计算存储位置,永远等于nTableSize-1 */
Bucket *arData; /* 存放实际数据 */
uint32_t nNumUsed; /* arData数组已经使用的数量 */
uint32_t nNumOfElements; /* hash表中元素个数 */
uint32_t nTableSize; /* hash表的大小 */
uint32_t nInternalPointer; /* 用于HashTable遍历 */
zend_long nNextFreeElement; /* 下一个空闲可用位置的数字索引 */
dtor_func_t pDestructor; /* 析构函数 */
};

在上面的结构定义中,_zend_array结构体构成一个完整的HashTable

HashTable操作

HashTable初始化

创建一个HashTable有很多途径,最终调用的都是_zend_hash_init函数:

zend_hash.c

ZEND_API void ZEND_FASTCALL _zend_hash_init(HashTable *ht, uint32_t nSize, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC)
{
GC_REFCOUNT(ht) = 1;
GC_TYPE_INFO(ht) = IS_ARRAY;
ht->u.flags = (persistent ? HASH_FLAG_PERSISTENT : 0) | HASH_FLAG_APPLY_PROTECTION | HASH_FLAG_STATIC_KEYS;
ht->nTableSize = zend_hash_check_size(nSize);
ht->nTableMask = HT_MIN_MASK;
HT_SET_DATA_ADDR(ht, &uninitialized_bucket);
ht->nNumUsed = 0;
ht->nNumOfElements = 0;
ht->nInternalPointer = HT_INVALID_IDX;
ht->nNextFreeElement = 0;
ht->pDestructor = pDestructor;
}

pDestructor是HashTable元素的析构指针,在更新/销毁HashTable中的元素时候会使用。在这里并没有初始化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的实现:
zend_hash.c

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);
HT_ASSERT(GC_REFCOUNT(ht) == 1);
/* 检查hashtable是否初始化 */
if (UNEXPECTED(!(ht->u.flags & HASH_FLAG_INITIALIZED))) {
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);
if (p) {
zval *data;
/* key已经存在产生添加冲突,退出 */
if (flag & HASH_ADD) {
return NULL;
}
/* key存在的情况下,值不一样做更新操作 */
ZEND_ASSERT(&p->val != pData);
data = &p->val;
if ((flag & HASH_UPDATE_INDIRECT) && Z_TYPE_P(data) == IS_INDIRECT) {
data = Z_INDIRECT_P(data);
}
HANDLE_BLOCK_INTERRUPTIONS();
/* 释放掉原来的data */
if (ht->pDestructor) {
ht->pDestructor(data);
}
/* 将新的pData值复制给原来的data */
ZVAL_COPY_VALUE(data, pData);
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 == HT_INVALID_IDX) {
ht->nInternalPointer = idx;
}
zend_hash_iterators_update(ht, HT_INVALID_IDX, idx);
p = ht->arData + idx; /* 指针加法移位 */
p->key = key;
if (!ZSTR_IS_INTERNED(key)) {
zend_string_addref(key);
ht->u.flags &= ~HASH_FLAG_STATIC_KEYS;
zend_string_hash_val(key); /* 计算key的hash值 */
}
p->h = h = ZSTR_H(key);
ZVAL_COPY_VALUE(&p->val, pData);
nIndex = h | ht->nTableMask; /* 与tablemask进行计算得出hash索引 */
Z_NEXT(p->val) = HT_HASH(ht, nIndex); /* 新的元素的hash冲突链表的next指向当前冲突链表的首部元素 */
HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx); /* 新的元素放到当前hash冲突链表的头部 */
HANDLE_UNBLOCK_INTERRUPTIONS();
return &p->val;
}

从上面的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里面。

索引相关的方法:

ZEND_API zval* ZEND_FASTCALL zend_hash_index_find(const HashTable *ht, zend_ulong h)
ZEND_API zend_bool ZEND_FASTCALL zend_hash_index_exists(const HashTable *ht, zend_ulong h)

更新元素

zend_hash_index_update(target, idx, &rv);

参数传递个数与PHP5不同,此处只需要3个参数,而在PHP5中需要5个参数,函数原型:

#define zend_hash_index_update(ht, h, pData) \
_zend_hash_index_update(ht, h, pData ZEND_FILE_LINE_CC)

第一个参数:HashTable
第二个参数:ulong,数字索引的key
第三个参数:void
,数据指针,指向要保存的数据

删除元素

zend_hash_del(ht)

Zend提供了一系列删除HashTable中元素的API,,定义如下:

static zend_always_inline void _zend_hash_del_el_ex(HashTable *ht, uint32_t idx, Bucket *p, Bucket *prev)
static zend_always_inline void _zend_hash_del_el(HashTable *ht, uint32_t idx, Bucket *p)
ZEND_API void ZEND_FASTCALL zend_hash_del_bucket(HashTable *ht, Bucket *p)
ZEND_API int ZEND_FASTCALL zend_hash_del(HashTable *ht, zend_string *key)
ZEND_API int ZEND_FASTCALL zend_hash_del_ind(HashTable *ht, zend_string *key)
ZEND_API int ZEND_FASTCALL zend_hash_str_del_ind(HashTable *ht, const char *str, size_t len)
ZEND_API int ZEND_FASTCALL zend_hash_str_del(HashTable *ht, const char *str, size_t len)
ZEND_API int ZEND_FASTCALL zend_hash_index_del(HashTable *ht, zend_ulong h)

清空HashTable

zend_hash_clean(ht)

销毁HashTable

HashTable的销毁是由zend_hash_destroy来负责的,使用:

zend_hash_destroy(ht)

清空和销毁的区别

zend_hash_destroyzend_hash_clean的区别
zend_hash_destory之后此HashTable就不能再利用了,而zend_hash_clean之后的HashTable还可能再次利用

其他高级操作函数

ZEND_API void ZEND_FASTCALL _zend_hash_merge(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, zend_bool overwrite ZEND_FILE_LINE_DC)
static zend_bool ZEND_FASTCALL zend_hash_replace_checker_wrapper(HashTable *target, zval *source_data, Bucket *p, void *pParam, merge_checker_func_t merge_checker_func)
ZEND_API void ZEND_FASTCALL zend_hash_merge_ex(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, merge_checker_func_t pMergeSource, void *pParam)
ZEND_API int zend_hash_compare(HashTable *ht1, HashTable *ht2, compare_func_t compar, zend_bool ordered)
static zend_always_inline int zend_hash_compare_impl(HashTable *ht1, HashTable *ht2, compare_func_t compar, zend_bool ordered)
ZEND_API int ZEND_FASTCALL _zend_handle_numeric_str_ex(const char *key, size_t length, zend_ulong *idx)

参考

script>