php内核数组(HashTable)实现方式
数组是php重要的部分，内核中也有大量使用。一起来看看是如何实现的吧。
php7中数组类型有两个概念分为packed、hash数组。
packed 数组：key 为顺序数字，索引数组。
hash 数组：key为字符串，关键数组。
下面主要是hash数组的插入、更新、及hash 冲突时解决方法。
数组使用到的结构体_zend_array 、_Bucket 。
使用数组字符串key生成hash值
zend_string_hash_val(key)
使用h | ht->nTableMask 计算映射表的索引编号(负数)
nIndex = h | ht->nTableMask
数组元素在内存中的偏移量
idx = HT_HASH_EX(arData, nIndex);
根据偏移量找到元素
p = HT_HASH_TO_BUCKET_EX(arData, idx);
zend_array 组成部分
typedef struct _Bucket {zval val; // 数组元素的值zend_ulong h; // hash值或数组索引zend_string *key; // 字符串key，数字key时为NULL
} Bucket;typedef struct _zend_array HashTable;struct _zend_array {zend_refcounted_h gc;union {struct {ZEND_ENDIAN_LOHI_4(zend_uchar flags,zend_uchar nApplyCount,zend_uchar nIteratorsCount,zend_uchar consistency)} v;uint32_t flags;} u;uint32_t nTableMask; // 掩码 获取nIndex = h | ht->nTableMask数据取值-nTableSizeBucket *arData; // Bucket 数组uint32_t nNumUsed; // 已使用的Bucke个数(包括标记删除的)uint32_t nNumOfElements; // 有效元素数uint32_t nTableSize; // 数组空间的大小，为2的n次方uint32_t nInternalPointer;zend_long nNextFreeElement; // 自增packed array 索引dtor_func_t pDestructor; // destruct 方法
};插入或更新数组元素
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_RC1(ht);//是否可以修改 （检查数组refcoun是否大于1，或者是不可变数组）if (UNEXPECTED(!(ht->u.flags & HASH_FLAG_INITIALIZED))) { // 是否分配内存空间CHECK_INIT(ht, 0);goto add_to_hash;} else if (ht->u.flags & HASH_FLAG_PACKED) { // 是否是hash数组zend_hash_packed_to_hash(ht); // 转化成hash数组} else if ((flag & HASH_ADD_NEW) == 0) { // 是更新还是新增p = zend_hash_find_bucket(ht, key); //根据key查找元素是否存在if (p) { //如果找到更新zval *data;if (flag & HASH_ADD) {if (!(flag & HASH_UPDATE_INDIRECT)) {return NULL;}ZEND_ASSERT(&p->val != pData);data = &p->val;if (Z_TYPE_P(data) == IS_INDIRECT) {data = Z_INDIRECT_P(data);if (Z_TYPE_P(data) != IS_UNDEF) {return NULL;}} else {return NULL;}} else {ZEND_ASSERT(&p->val != pData);data = &p->val;if ((flag & HASH_UPDATE_INDIRECT) && Z_TYPE_P(data) == IS_INDIRECT) {data = Z_INDIRECT_P(data);}}if (ht->pDestructor) {ht->pDestructor(data);}ZVAL_COPY_VALUE(data, pData);return data;}}//下在是新增ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* If the Hash table is full, resize it */add_to_hash: idx = ht->nNumUsed++; //元素指针的偏移量 （等于有效元素+1）ht->nNumOfElements++; //增加有效元素个数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; // 保存keyif (!ZSTR_IS_INTERNED(key)) { //检查key是否是内部字符串zend_string_addref(key);ht->u.flags &= ~HASH_FLAG_STATIC_KEYS;zend_string_hash_val(key);}p->h = h = ZSTR_H(key); // 保存数组key的hash值ZVAL_COPY_VALUE(&p->val, pData); // 保存数组的值nIndex = h | ht->nTableMask; //计算数组映射表位置Z_NEXT(p->val) = HT_HASH(ht, nIndex); //元素next 映射表位置 HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx); // 保存元素偏移保存在映射表return &p->val;
}
根据字符串key查找数组元素
static zend_always_inline Bucket *zend_hash_find_bucket(const HashTable *ht, zend_string *key)
{zend_ulong h; //计算出来的hash值uint32_t nIndex; //映射表的索引 是个负数uint32_t idx; //元素位置的偏移量Bucket *p, *arData; // 元素h = zend_string_hash_val(key); // 根据key生成hash值arData = ht->arData; // 元素指针位置nIndex = h | ht->nTableMask; // 计算映射表中位置(负数)idx = HT_HASH_EX(arData, nIndex); // 根据映射表位置找到元素在数组中的偏移量while (EXPECTED(idx != HT_INVALID_IDX)) { // 判断映射表是否有效p = HT_HASH_TO_BUCKET_EX(arData, idx); //根据偏移量找到数组元素位置if (EXPECTED(p->key == key)) { /*判断key是否相等 */return p;} else if (EXPECTED(p->h == h) && // hash值是否相等EXPECTED(p->key) &&EXPECTED(ZSTR_LEN(p->key) == ZSTR_LEN(key)) && //key长度是否相等EXPECTED(memcmp(ZSTR_VAL(p->key), ZSTR_VAL(key), ZSTR_LEN(key)) == 0)) { // 对比hash、key的长度、key是否相等return p;}idx = Z_NEXT(p->val); // 如果不相等通过(zval).u2.next找到新的偏移量（hash冲突时，会保存链表结构）}return NULL;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！