PHP7 数组的实现

前提
  • PHP版本：php7.0.29
  • 使用到的文件
    • php-src/Zend/zend_types.h
    • php-src/Zend/zend_hash.h
    • php-src/Zend/zend_hash.c
    • php-src/Zend/zend_string.h
  • 本文 是《PHP7底层设计和源码实现》第5章 数组的实现，学习笔记
功能分析
整体结构

  • 请添加图片描述

    • bucket 里面增加h字段，h代表的是数字key(packed array 模式下，直接是数组下标)
    • 哈希函数拆分为 hash1函数和hash2函数。hash1 将key映射为h值，hash2将h值映射为slot的索引值
    • key字段作为字符串key，不再表示数字key
数据结构
bucket结构分析
// Bucket: 散列表中存储的元素
typedef struct _Bucket {
	zval              val;  // 存储的具体value，这里嵌入一个zval，而不是一个指针
	zend_ulong        h;    // key 根据times 33 计算得到的哈希值，或者是数值索引编号
	zend_string      *key;  // 存储元素的key
};
  • 参数说明
    • val 参数
      • 对应HashTable设计中的value。始终是zval类型
      • zval结构
        struct _zval_struct {
	zend_value        value;			/* 表明zval类型 */
	union {
		struct {
			ZEND_ENDIAN_LOHI_4(
				zend_uchar    type,			/* active type */
				zend_uchar    type_flags,
				zend_uchar    const_flags,
				zend_uchar    reserved)	    /* call info for EX(This) */
		} v;
		uint32_t type_info;
	} u1;
	union {
		uint32_t     var_flags;
		uint32_t     next;                 /* 用来解决哈希冲突 */
		uint32_t     cache_slot;           /* 运行时缓存 */
		uint32_t     lineno;               /* 对于zend_ast_zval存行号 */
		uint32_t     num_args;             /* EX(This) 参数个数*/
		uint32_t     fe_pos;               /* foreach 位置 */
		uint32_t     fe_iter_idx;          /* foreach 游标的标记 */
	} u2;
};
      • 每个zval类型16个字节
      • h 参数
        • 对应HashTable设计中的h，表示数字key或者字符串key的h值
      • key 参数
        • 对应HashTable设计中的key，表示字符串的key
        • zend_string结构
          struct _zend_string {
	zend_refcounted_h gc;	/* 8字节，内嵌的gc，引用计数及字符串类别存储*/
	zend_ulong        h;   /* hash值，8字节，字符串的哈希值 */
	size_t            len;	/* 8字节，字符串的长度*/
	char              val[1]; /*柔性数数组，占1位，字符串的值存储的位置*/
};

typedef struct _zend_refcounted_h {
	uint32_t         refcount;			/* gc,整块占用8字节 */
	union { // 4字节
		struct {
			ZEND_ENDIAN_LOHI_3(
				zend_uchar    type,	/* 等同于zval的u1.v.type*/
				zend_uchar    flags,    /* 字符串的类型数据 */
				uint16_t      gc_info)  /* 垃圾回收标记颜色用 */
		} v;
		uint32_t type_info;
	} u;
} zend_refcounted_h;
          • zend_string是一种带有字符串长度，h值，gc信息的字符串数组的包装，提升了性能和空间效率
  • bucket 的类型
    • 未使用bucket
      • 最初所有的bucket都是未使用的状态
    • 有效bucket
      • 存储着有效的数据(key, val, h),当进行插入时，会选择一个未使用bucket，这样该bucket就变成了有效bucket
      • 更新操作只能发生在有效bucket上，更新后，仍然是有效bucket
    • 无效bucket
      • 当bucket上存储的数据被删除时，有效bucket就会变成无效bucket
  • bucket类型间的转换
    • 在内存分布上有效bucket和无效bucket会交替分布，但都在未使用bucket的前面
    • 插入的时候永远在未使用bucket上进行
    • 当由于删除等操作，导致无效bucket非常多，而有效bucket很少时，会对整个bucket数组进行rehash操作，这样，稀疏的有效bucket就会变得连续和紧密
    • 部分无效bucket会被重新利用而变为有效bucket
    • 还有一部分有效bucket和无效bucket会被释放出来，重新变成未使用bucket
    • 请添加图片描述
HashTable结构分析
// HashTable 结构
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    reserve)
		} v;
		uint32_t flags;
	} u;
	uint32_t          nTableMask;   // 哈希值计算掩码，等于nTableSize的负值(nTableMask = -nTableSize)
	Bucket           *arData;   // 存储元素数组，指向第一个Bucket
	uint32_t          nNumUsed; // 已用Bucket数
	uint32_t          nNumOfElements;   // 哈希表有效元素数
	uint32_t          nTableSize;   // 哈希表总大小，为2的n次方
	uint32_t          nInternalPointer;
	zend_long         nNextFreeElement; // 下一个可能的数值索引，如: arr[] = 1; arr["a"] = 2;arr[] = 3; 则nNextFreeElement = 2
	dtor_func_t       pDestructor;
};
  • 参数说明
    • gc 参数
      • 引用计数相关
      • 在PHP7中，引用计数不再是zval的字段，而是被设计在zval的value字段所指向的结构体中
    • argData 参数
      • 实际的存储容器
      • 通过指针指向一段连续的内存，存储着bucket数组
    • nTableSize 参数
      • HashTable 的大小
      • 表示 arData指向的bucket数组的大小，即所有bucket的数量
      • 最小值未8
      • 最大值在32位系统中是0x40000000(2 ^ 30)，在64位系统中0x80000000(2 ^ 31)
    • nNumUsed 参数
      • 指向已使用bucket的数量，包括有效bucket和无效bucket的数量
      • 在bucket数组中，下标从0 ~ (nNumUsed - 1)的bucket都属于已使用bucket
      • 而下标为nNumUsed ~ (nTableSize - 1)的bucket都属于未使用bucket
    • nNumOfElements 参数
      • 有效bucket的数量
      • 该值总是小于或等于nNumUsed
    • nTableMask 参数
      • 掩码。一般为-nTableSize
    • nInternalPointer 参数
      • HashTable的全局默认游标
    • nNextFreeElement 参数
      • HashTable的自然key
      • 自然key是指HashTable的应用语义是纯数组时，插入元素无须指定key，key会以nNextFreeElement的值为准
      • 例如
        • 该字段初始值为0
        • $a[] = 1，实际上是插入到key等于0的bucket上
        • 然后nNextFreeElement会递增1，代表下一个自然插入的元素的key是1
    • pDestructor 参数
      • 析构函数
      • 当bucket元素被更新或被删除时，会对bucket的value调用该函数
      • 如果value是引用计数的类型，那么会对value应用计数减1，进而引发可能的gc
    • u 联合体
      • 占用4个字节。可以存储一个uint32_t类型的flags
      • 也可以存储由4个unsigned char 组成的结构体v
      • u.v.flags 参数
        • 用各个bit来表达HashTable的各种标记
        • 共有下面6中flag，分别对应 u.v.flags的第1位到6位
          #define HASH_FLAG_PERSISTENT       (1<<0)	// 是否使用持久化内存（不使用内存池）
#define HASH_FLAG_APPLY_PROTECTION (1<<1)	// 是否开启递归遍历保护
#define HASH_FLAG_PACKED           (1<<2)	// 是否是packed array
#define HASH_FLAG_INITIALIZED      (1<<3)	// 是否初始化
#define HASH_FLAG_STATIC_KEYS      (1<<4)	// 标记HashTable的Key是否为long key
#define HASH_FLAG_HAS_EMPTY_IND    (1<<5)	// 是否存在空的间接val
      • u.v.nApplyCount 参数
        • 递归遍历计数
        • 为了解决循环引用导致的死循环问题
        • 当对某个数组进行某种递归操作时，在递归调入栈之前将nApplyCount加1，递归调出栈之后将nApplyCount减1
        • 当循环引用出现时，递归调用会不断入栈，当nApplyCount增加到一定阀值时，不再继续递归下去，返回一个合法的值，并打印"recursion detected"之类的warning或者error日志
        • 这个阀值一般不大于3
      • u.v.nIteratorsCount 参数
        • 迭代器计数
        • PHP中每一个foreach语句都会在全局变量EG中创建一个迭代器
        • 迭代器包含正在遍历的HashTable和游标信息
        • 该字段记录了runtime正在迭代当前的HashTable的迭代器的数量
      • u.v.consistency 参数
        • 成员用于调试目的
          #define HT_OK					0x00	// 正常状态，各种数据完全一致
#define HT_IS_DESTROYING		0x40	// 正在删除所有的内容，包括arBuckets本身
#define HT_DESTROYED			0x80	// 已删除，包括arBuckets本身
#define HT_CLEANING				0xc0	// 正在清除所有的arBuckets执行的内容，但不包括arBuckets本身
  • 为什么HashTable 掩码(nTableMask)是负数?
    • PHP7在分配bucket数据内存的时候，在bucket数组的前面额外多申请内存
    • 这段内存是一个索引数组(也加索引表)，数组里面的每个元素代表一个Slot,存储着每个slot链表的第一个bucket在bucket数组中的下标
    • 索引表的默认值：-1
    • 为了实现逻辑链表，由于bucket元素的val是zval，PHP7通过bucket.val.u2.next表达链表中下一个元素在数组中的下标
    • 请添加图片描述
HashTable 初始化
初始化一：为HashTable分配内存，初始化HashTable各个字段
  • 例如: $arr = array();
  • 初始化流程
    • 申请内存
      (ht) = (HashTable *)emalloc(sizeof(HashTable));
    • 调用_zend_hash_init
      static const uint32_t uninitialized_bucket[-HT_MIN_MASK] = {HT_INVALID_IDX, HT_INVALID_IDX};

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; 	// 7 类别设置成数组
	ht->u.flags = (persistent ? HASH_FLAG_PERSISTENT : 0) | HASH_FLAG_APPLY_PROTECTION | HASH_FLAG_STATIC_KEYS;
	ht->nTableSize = zend_hash_check_size(nSize);   // 能包含nSize的最小2 ^ n的数字最小值 8
	ht->nTableMask = HT_MIN_MASK;	// -2，默认是packed array
	HT_SET_DATA_ADDR(ht, &uninitialized_bucket);    // ptr偏移到arrData地址
	ht->nNumUsed = 0;
	ht->nNumOfElements = 0;
	ht->nInternalPointer = HT_INVALID_IDX;
	ht->nNextFreeElement = 0;
	ht->pDestructor = pDestructor;
}
  • 参数说明
    • nTableSzie = 8
      • 因为HashTable 内部的arBuckets的大小是2的n次方，并且最小是8，最大值为0x8000000
    • u.vflags = 18
      #define HASH_FLAG_PERSISTENT       (1<<0)
#define HASH_FLAG_APPLY_PROTECTION (1<<1)
#define HASH_FLAG_PACKED           (1<<2)
#define HASH_FLAG_INITIALIZED      (1<<3)
#define HASH_FLAG_STATIC_KEYS      (1<<4)
#define HASH_FLAG_HAS_EMPTY_IND    (1<<5)
      • flag = 18 = HASH_FLAG_STATIC_KEYS | HASH_FLAG_APPLY_PROTECTION
      • 而flag & HASH_FLAG_INITIALIZED 等于0说明，该数组尚未完成真正的初始化，即尚未为arData分配内存
    • 设置nNumberUsed, nNumOfElement为0
      • 因为现在还没有使用任何数据元素
    • 设置nInternalPointer为-1
      • 表示尚未设置全局遍历游标
    • 设置nNextFreeElement 为 0
      • 表示数组的自然key从0开始
    • 设置nTableSize
      • 如果传递的nSize 不是 2 ^ n，会通过zend_hash_check_size函数计算大于等于nSize的最小的 2 ^ n
      • 例如 nSize = 10, 那么最终ht->nTableSize取值为16
    • nTableMask = -2
      • 表示索引表大小为2
      • packed array的索引表未使用到，即nTableMask永远等于-2
初始化二：为bucket数组分配内存，修改HashTable某些字段
  • 例如: $arr[] = ‘foo’;
  • 流程
    • 调用 zend_hash_real_init_ex
      static void zend_always_inline zend_hash_real_init_ex(HashTable *ht, int packed)
{
	HT_ASSERT(GC_REFCOUNT(ht) == 1);
	ZEND_ASSERT(!((ht)->u.flags & HASH_FLAG_INITIALIZED));
	// packed: h < ht->nTableSize, h = 0, ht->nTableSize 默认为8
	if (packed) {	// packed array 初始化
		/* 为arData分配内存, 并把arData的指针偏移指向buckets数组的首地址*/
		HT_SET_DATA_ADDR(ht, pemalloc(HT_SIZE(ht), (ht)->u.flags & HASH_FLAG_PERSISTENT));
		// 修改flags为 已经初始化并且为packed array
		(ht)->u.flags |= HASH_FLAG_INITIALIZED | HASH_FLAG_PACKED;
		// nIndex置为无效标识-1，arData[-1], arrData[-2] = -1
		HT_HASH_RESET_PACKED(ht);
	} else {	// 普通哈希表的初始化
		/*
			掩码nTableMask为nTableSize的负数，即nTableMask = -nTableSize, 因为nTableSize 等于 2 ^ n，所以nTableMask二进制位右侧全部为0，也就保证了nIndex落在数组索引范围之内(|nIndex| <= nTableSize)
		*/
		(ht)->nTableMask = -(ht)->nTableSize;
		HT_SET_DATA_ADDR(ht, pemalloc(HT_SIZE(ht), (ht)->u.flags & HASH_FLAG_PERSISTENT));
		(ht)->u.flags |= HASH_FLAG_INITIALIZED;
		if (EXPECTED(ht->nTableMask == -8)) {
			Bucket *arData = ht->arData;

			HT_HASH_EX(arData, -8) = -1;
			HT_HASH_EX(arData, -7) = -1;
			HT_HASH_EX(arData, -6) = -1;
			HT_HASH_EX(arData, -5) = -1;
			HT_HASH_EX(arData, -4) = -1;
			HT_HASH_EX(arData, -3) = -1;
			HT_HASH_EX(arData, -2) = -1;
			HT_HASH_EX(arData, -1) = -1;
		} else {
			HT_HASH_RESET(ht);	// 调用memset函数把所有内存设置成无符号整型的-1
		}
	}
}
  • 参数说明
    • HashTable的arData被真正地分配内存
      • 并且按最小值8分配了8个bucket的存储空间
    • flags = 30
      • flags = 30 = HASH_FLAG_STATIC_KEYS | HASH_FLAG_APPLY_PROTECTION | HASH_FLAG_PACKED | HASH_FLAG_INITIALIZED
      • 说明当前HashTable.arData已经被初始化完毕，并且当前HashTable是packed array
    • nTableMask = -2
      • 因为是packed array
    • h = 0
      • $arr[] 对于首次插入，h 等于0
      • packed array 插入到bucket数组的第一个位置(下标为0)
    • bucket 里面内嵌了 zval
    • nNumUsed = 1
      • 由于bucket数组是连续分配的内存，nNumUsed = 1代表了已经使用了1个bucket
      • 那就是arData[0]这个bucket
    • nNumOfElements = 1
      • 表示当前HashTable中有一个有效元素arData[0]
    • nInternalPointer = 0
      • 遍历下标，表示遍历HashTable时从arData[0]开始
    • nNextFreeElement = 1
      • 自然下标，下次自然序插入时, h值为1
packed array 和 hash array 的区别

  • packed array

    • 例如：$a = array(1, 2, 3); // 纯数组
    • 特性和约束
      • key 全部数字key
      • key 按插入顺序排列，仍然是递增的
      • 每一个key-value对的存储位置都是非常确定的，都存储在bucket数组的第key个元素上
      • packed array 不需要索引数组
    • 请添加图片描述

  • hash array

    • 例如：$b = array(‘x’ => 1, ‘y’ => 2, ‘z’ => 3);
    • 说明
      • hash array 依赖数组来维护每个slot链表中首元素在bucket中的下标
      • 拿key 为 x举例，字符串x的h值是9223372036854953501，它与nTableMask(-8)做位或运算之后，结果是-3
      • 然后到索引数组上去查询-3这个slot值，得到该slot链表首元素在bucket数组的下标为0
    • 请添加图片描述
Hash 算法
static zend_always_inline zend_ulong zend_inline_hash_func(const char *str, size_t len)
{
	register zend_ulong hash = Z_UL(5381);

	/* variant with the hash unrolled eight times */
	for (; len >= 8; len -= 8) {
		hash = ((hash << 5) + hash) + *str++;
		hash = ((hash << 5) + hash) + *str++;
		hash = ((hash << 5) + hash) + *str++;
		hash = ((hash << 5) + hash) + *str++;
		hash = ((hash << 5) + hash) + *str++;
		hash = ((hash << 5) + hash) + *str++;
		hash = ((hash << 5) + hash) + *str++;
		hash = ((hash << 5) + hash) + *str++;
	}
	switch (len) {
		case 7: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
		case 6: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
		case 5: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
		case 4: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
		case 3: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
		case 2: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
		case 1: hash = ((hash << 5) + hash) + *str++; break;
		case 0: break;
EMPTY_SWITCH_DEFAULT_CASE()
	}

	/* Hash value can't be zero, so we always set the high bit */
#if SIZEOF_ZEND_LONG == 8
	return hash | Z_UL(0x8000000000000000);
#elif SIZEOF_ZEND_LONG == 4
	return hash | Z_UL(0x80000000);
#else
# error "Unknown SIZEOF_ZEND_LONG"
#endif
}
  • PHP的Hash采用的是目前最为普遍的DJBX33A (Daniel J. Bernstein, Times 33 with Addition)
  • 算法的核心思想就是:
    • hash(i) = hash(i-1) * 33 + str[i]
  • PHP中并没有使用直接乘33, 而是采用了: hash << 5 + hash
映射函数
  • 映射函数(散列函数)是散列表的关键部分，它将key 与 value 建立映射关系,一般映射函数可以根据key的哈希值与Bucket数组大小取模得到
    • 即 key->h % ht->nTableSize
    • PHP的做法： nIndex = key->h | nTablesMask
  • nTablesMask 为 nTableSize 的负数，即：nTablesMask = -nTableSize
  • 因为 nTableSize 等于 2 ^ n, 所以nTablesMask二进制右侧全部为0，也就保证了nIndex 落在数组索引的范围之内([-n, -1])
    • 11111111 11111111 11111111 11111000 -8
    • 11111111 11111111 11111111 11111001 -7
    • 11111111 11111111 11111111 11111010 -6
    • 11111111 11111111 11111111 11111011 -5
    • 11111111 11111111 11111111 11111100 -4
    • 11111111 11111111 11111111 11111101 -3
    • 11111111 11111111 11111111 11111110 -2
    • 11111111 11111111 11111111 11111111 -1
HashTable 插入
情景分析
  • 例子1: $arr[] = ‘foo’; // 默认为packed array
    • 流程
      • 调用 zend_hash_init 函数，进行hashtable的初始化
        • 初始化为packed array 模式
      • 调用 _zend_hash_next_index_insert 函数将uninitialized_zval插入到HashTable中
        • 然后将字符串foo(zend string 类型)拷贝到对应的zval中
    • 调用函数分析
      • _zend_hash_next_index_insert
        • _zend_hash_next_index_insert 会调用 _zend_hash_index_add_or_update_i
        /**
* @description 向数值索引哈希表的尾部插入数据
* @param HashTable* ht 待操作的哈希表
* @param zval* pData 待保存的数据
* @return: zval*
*/
ZEND_API zval* ZEND_FASTCALL _zend_hash_next_index_insert(HashTable *ht, zval *pData ZEND_FILE_LINE_DC)
{
	return _zend_hash_index_add_or_update_i(ht, ht->nNextFreeElement, pData, HASH_ADD | HASH_ADD_NEXT ZEND_FILE_LINE_RELAY_CC);
}
      • _zend_hash_index_add_or_update_i
        static zend_always_inline zval *_zend_hash_index_add_or_update_i(HashTable *ht, zend_ulong h, zval *pData, uint32_t flag ZEND_FILE_LINE_DC)
{
	uint32_t nIndex;
	uint32_t idx;
	Bucket *p;

	IS_CONSISTENT(ht);
	HT_ASSERT(GC_REFCOUNT(ht) == 1);

	if (UNEXPECTED(!(ht->u.flags & HASH_FLAG_INITIALIZED))) {	//  检测hash table 是否初始化
		CHECK_INIT(ht, h < ht->nTableSize);
		if (h < ht->nTableSize) {
			p = ht->arData + h;
			goto add_to_packed;
		}
		goto add_to_hash;
	} else if (ht->u.flags & HASH_FLAG_PACKED) {	// hash table 为 packed array
		// 使用已有的bucket
		if (h < ht->nNumUsed) {
			p = ht->arData + h;
			// p 不是要删除的bucket
			if (Z_TYPE(p->val) != IS_UNDEF) {
				if (flag & HASH_ADD) {
					return NULL;
				}
				if (ht->pDestructor) {
					ht->pDestructor(&p->val);
				}
				ZVAL_COPY_VALUE(&p->val, pData);
				if ((zend_long)h >= (zend_long)ht->nNextFreeElement) {
					ht->nNextFreeElement = h < ZEND_LONG_MAX ? h + 1 : ZEND_LONG_MAX;
				}
				return &p->val;
			} else { /* we have to keep the order :( */
				goto convert_to_hash;
			}
		} else if (EXPECTED(h < ht->nTableSize)) {
			p = ht->arData + h;
		} else if ((h >> 1) < ht->nTableSize &&
				(ht->nTableSize >> 1) < ht->nNumOfElements) {
			zend_hash_packed_grow(ht);
			p = ht->arData + h;
		} else {
			goto convert_to_hash;
		}

add_to_packed:
		HANDLE_BLOCK_INTERRUPTIONS();
		/* incremental initialization of empty Buckets */
		if ((flag & (HASH_ADD_NEW|HASH_ADD_NEXT)) == (HASH_ADD_NEW|HASH_ADD_NEXT)) {
			ht->nNumUsed = h + 1;	// nNumUsed(实际bucket)增加 h + 1
		} else if (h >= ht->nNumUsed) {
			// h 大于 nNumUsed: 意味着，这个是新插入的数据
			if (h > ht->nNumUsed) {
				Bucket *q = ht->arData + ht->nNumUsed;	// 指针移动到 ht->arData + ht->nNumUsed 位置
				while (q != p) {
					ZVAL_UNDEF(&q->val);	// 把val设置为 is_undef(标记为无效bucket)
					q++;
				}
			}
			ht->nNumUsed = h + 1;
		}
		ht->nNumOfElements++;
		if (ht->nInternalPointer == HT_INVALID_IDX) {
			ht->nInternalPointer = h;
		}
		zend_hash_iterators_update(ht, HT_INVALID_IDX, h);
		if ((zend_long)h >= (zend_long)ht->nNextFreeElement) {
			ht->nNextFreeElement = h < ZEND_LONG_MAX ? h + 1 : ZEND_LONG_MAX;
		}
		// packey array。h 不需要 h | nTableSize
		p->h = h;
		p->key = NULL;
		// 把pData 赋值到 val中
		ZVAL_COPY_VALUE(&p->val, pData);

		HANDLE_UNBLOCK_INTERRUPTIONS();

		return &p->val;

convert_to_hash:
		// packed array 模式 转换成 hash array模式
		zend_hash_packed_to_hash(ht);
	} else if ((flag & HASH_ADD_NEW) == 0) {
		p = zend_hash_index_find_bucket(ht, h);
		if (p) {
			if (flag & HASH_ADD) {
				return NULL;
			}
			ZEND_ASSERT(&p->val != pData);
			HANDLE_BLOCK_INTERRUPTIONS();
			if (ht->pDestructor) {
				ht->pDestructor(&p->val);
			}
			ZVAL_COPY_VALUE(&p->val, pData);
			HANDLE_UNBLOCK_INTERRUPTIONS();
			if ((zend_long)h >= (zend_long)ht->nNextFreeElement) {
				ht->nNextFreeElement = h < ZEND_LONG_MAX ? h + 1 : ZEND_LONG_MAX;
			}
			return &p->val;
		}
	}

	ZEND_HASH_IF_FULL_DO_RESIZE(ht);		/* If the Hash table is full, resize it */

add_to_hash:
	HANDLE_BLOCK_INTERRUPTIONS();
	idx = ht->nNumUsed++;	// nNumUsed++为bucket下标
	ht->nNumOfElements++;	// 有效的bucket个数增加1
	if (ht->nInternalPointer == HT_INVALID_IDX) {
		ht->nInternalPointer = idx;
	}
	zend_hash_iterators_update(ht, HT_INVALID_IDX, idx);
	if ((zend_long)h >= (zend_long)ht->nNextFreeElement) {
		ht->nNextFreeElement = h < ZEND_LONG_MAX ? h + 1 : ZEND_LONG_MAX;
	}
	p = ht->arData + idx;	// 指针移动到 ht->arData + idx位置
	p->h = h;
	p->key = NULL;
	nIndex = h | ht->nTableMask;	// nIndex为slot位置
	// // 把pData 赋值到 val中
	ZVAL_COPY_VALUE(&p->val, pData);
	// 哈希冲突处理，把p->val.u2.next 设置为 slot位置
	Z_NEXT(p->val) = HT_HASH(ht, nIndex);
	// 把slot位置的内容设置为 idx
	HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx);
	HANDLE_UNBLOCK_INTERRUPTIONS();

	return &p->val;
}
  • 例子2: $arr[‘a’] = ‘bar’
    • 流程
      • 首先调用zend_hash_find根据 key = 'a’查找,查找不到对应的key
      • 然后通过zend_hash_add_new把uninitialized_zval插入到HashTable中
      • 如果此时是packed array，需要调用zend_hash_packed_to_hash进行转换
    • 函数解析
      • zend_hash_find
        ZEND_API zval* ZEND_FASTCALL zend_hash_find(const HashTable *ht, zend_string *key)
{
	Bucket *p;

	IS_CONSISTENT(ht);

	p = zend_hash_find_bucket(ht, key);
	return p ? &p->val : NULL;
}
      • zend_hash_find_bucket
        static zend_always_inline Bucket *zend_hash_find_bucket(const HashTable *ht, zend_string *key)
{
	zend_ulong h;
	uint32_t nIndex;
	uint32_t idx;
	Bucket *p, *arData;
	// key 通过 zend_string_hash_val获得
	h = zend_string_hash_val(key);
	arData = ht->arData;
	// slot 位置
	nIndex = h | ht->nTableMask;
	// slot 里的内容
	idx = HT_HASH_EX(arData, nIndex);
	// idx不为空
	while (EXPECTED(idx != HT_INVALID_IDX)) {
		// arData 中寻找idx下标的bucket
		p = HT_HASH_TO_BUCKET_EX(arData, idx);
		// 找到对应的值
		if (EXPECTED(p->key == key)) { /* check for the same interned string */
			return p;
		} else if (EXPECTED(p->h == h) &&
			EXPECTED(p->key) &&
			EXPECTED(ZSTR_LEN(p->key) == ZSTR_LEN(key)) &&
			EXPECTED(memcmp(ZSTR_VAL(p->key), ZSTR_VAL(key), ZSTR_LEN(key)) == 0)) {
			return p;
		}
		idx = Z_NEXT(p->val);
	}
	return NULL;
}
      • zend_hash_add_new
        • 最后是调用_zend_hash_add_or_update_i
      • zend_hash_packed_to_hash
        ZEND_API void ZEND_FASTCALL zend_hash_packed_to_hash(HashTable *ht)
{
	// 把当前的hash table 设置为旧hash table
	void *new_data, *old_data = HT_GET_DATA_ADDR(ht);
	Bucket *old_buckets = ht->arData;

	HT_ASSERT(GC_REFCOUNT(ht) == 1);
	HANDLE_BLOCK_INTERRUPTIONS();
	// ~HASH_FLAG_PACKED 把 packed array 变成 hash array
	ht->u.flags &= ~HASH_FLAG_PACKED;
	// 申请nTableSize + nTableMask数量的内存
	new_data = pemalloc(HT_SIZE_EX(ht->nTableSize, -ht->nTableSize), (ht)->u.flags & HASH_FLAG_PERSISTENT);
	ht->nTableMask = -ht->nTableSize;
	// 修改ht内存指向
	HT_SET_DATA_ADDR(ht, new_data);
	// 复制旧数据到新hash table
	memcpy(ht->arData, old_buckets, sizeof(Bucket) * ht->nNumUsed);
	// 释放旧数据
	pefree(old_data, (ht)->u.flags & HASH_FLAG_PERSISTENT);
	// 重建索引
	zend_hash_rehash(ht);
	HANDLE_UNBLOCK_INTERRUPTIONS();
}
  • 例子3: $arr[2] = ‘abc’
    • 流程
      • 首先使用 zend_hash_index_find函数根据h = 2来查找，查找不到的话
      • 调用zend_hash_index_add_new 将其插入HashTable中去
    • 函数分析
      • zend_hash_index_find
        ZEND_API zval* ZEND_FASTCALL zend_hash_index_find(const HashTable *ht, zend_ulong h)
{
	Bucket *p;

	IS_CONSISTENT(ht);
	//hash table 是否是packed array
	if (ht->u.flags & HASH_FLAG_PACKED) {
		// 查找的值，小于hash table 实际的bucket
		if (h < ht->nNumUsed) {
			p = ht->arData + h;
			// p 不是被标记删除的数据
			if (Z_TYPE(p->val) != IS_UNDEF) {
				return &p->val;
			}
		}
		return NULL;
	}
	// 如果是hash array就使用 zend_hash_index_find_bucket
	p = zend_hash_index_find_bucket(ht, h);
	return p ? &p->val : NULL;
}
      • zend_hash_index_add_new
        • 最后调用 _zend_hash_index_add_or_update_i
  • 例子4: $arr[] = ‘xyz’
    • 流程
      • 调用_zend_hash_next_index_insert
      • 对于h，使用的是ht->nNextFreeElement
      • 如此时ht->nNextFreeElement == 3, 同样传入 h = 3调用zend_hash_index_find_bucket查找
      • 查找不到的话，进行插入
    • 函数分析
      • _zend_hash_next_index_insert
        • 最后调用 _zend_hash_index_add_or_update_i
      • zend_hash_index_find_bucket
        static zend_always_inline Bucket *zend_hash_index_find_bucket(const HashTable *ht, zend_ulong h)
{
	uint32_t nIndex;
	uint32_t idx;
	Bucket *p, *arData;

	arData = ht->arData;
	// 获取slot位置
	nIndex = h | ht->nTableMask;
	// 获取 slot的内容
	idx = HT_HASH_EX(arData, nIndex);
	// idx 不为空
	while (idx != HT_INVALID_IDX) {
		// 断言，idx小于 ht->nTableSize
		ZEND_ASSERT(idx < HT_IDX_TO_HASH(ht->nTableSize));
		// 获取 arrData下标处的内容
		p = HT_HASH_TO_BUCKET_EX(arData, idx);
		// h相等，且key不为空。意味着是hash array类型
		if (p->h == h && !p->key) {
			return p;
		}
		// 不然，需要选择p的冲突链表里的next值
		idx = Z_NEXT(p->val);
	}
	return NULL;
}
  • 例子5: $arr[‘a’] = ‘foo’
    • 流程
      • 调用zend_hash_find_bucket，通过 key = a查找，通过zend_string_hash_val可以计算 h值
      • 然后通过 nIndex = h | ht->nTableMask , nIndex = -2, 而-2位置对应1，找到arData的第1个位置，判断key是否等于’a’,然后将对应的值改为’foo’，并做优化
HashTable 哈希冲突解决
  • 说明
    • PHP7 hash array 的做法，把每个冲突的idx存储在bucket的zval.u2.next中
    • 插入的时候把老的value存储的地址(idx)放到新value的next中，再把新value的存储地址更新到索引数组
    • 通过 zval.u2.next的值，就可以形成一条隐藏的链表
  • 例如

    • 请添加图片描述

    • 1). 插入第1个bucket，对应nIdex为-3，那么此时nIndex = -3的位置值为1

    • 2). 若此时插入第2个bucket，与第1个冲突，也就是对应的nIndex也为-3

      • 所以，令nIndex = -3的位置值为2，同时将第2个bucket中zval里面的u2.next值置为1
      • 这样，在查找第1个bucket的key对应的nIndex时，找到第2个bucket，校验key值不同，会取u2.next对应的1，取第1个bucket中的内容，与key校验一致，则返回

    • 3). 若此时插入第3个bucket，与第1个和第2个冲突，那么用同样的方式，令nIndex = -3的位置值为3，同时将第3个bucket中zval里面的u2.next值置为2

HashTable 扩容和rehash操作

  • 扩容和rehash整体流程流程

    • hash array 的容量分配的是固定的，初始化每次申请的是2 ^ n的容量，容量最小值为 2 ^ 3，最大值为0x8000000
    • 当容量足够时候，直接执行插入操作
    • 当容量不够时候(nNumUsed >= nTableSize)
      • 检查已删除元素所占的比例，假如达到阀值(ht->nNumUsed - ht->nNumOfElements > (ht->nNumOfElements >> 5))
      • 则将已删除元素从HashTable中移除，并重建索引
      • 如果未到阀值，则要进行扩容操作，新的容量扩大到当前的大小的2倍(2 * nTableSzie),将当前bucket数组复制到新的空间，然后重建索引
    • 重建完索引后，有足够的空余空间再执行插入操作
    • 请添加图片描述

  • 重建索引的过程

    • rehash对应源码中的zend_hash_rehash(ht)方法

    • rehash的主要功能就是HashTable bucket数组中标识为IS_UNDEF的数据剔除，把有效数据重新聚合到bucket数组并更新插入索引表

    • rehash不重新申请内存，整个过程是在原有结构上做聚合调整

    • 请添加图片描述

      • 具体步骤
        • 重置所有Index数组为-1
        • 初始化两个bucket类型的指针p, q,循环遍历bucket数组
        • 每次循环, p++，遇到第一个IS_UNDEF， q =p;继续循环数组
        • 当再一次遇到一个正常数据时，把正常数据拷贝到q指向的位置，q++
        • 直到遍历完数据，更新nNumUsed等计数

  • 代码分析

    • zend_hash_rehash
      ZEND_API int ZEND_FASTCALL zend_hash_rehash(HashTable *ht)
{
	Bucket *p;
	uint32_t nIndex, i;

	IS_CONSISTENT(ht);

	// 有效bucket为0
	if (UNEXPECTED(ht->nNumOfElements == 0)) {
		// hash table 还没有初始化
		if (ht->u.flags & HASH_FLAG_INITIALIZED) {
			ht->nNumUsed = 0;
			HT_HASH_RESET(ht);
		}
		return SUCCESS;
	}

	// 把slot 数组设置为-1
	HT_HASH_RESET(ht);
	i = 0;
	p = ht->arData;
	// 全部都是有效bucket
	if (ht->nNumUsed == ht->nNumOfElements) {
		// 重建slot索引
		do {
			nIndex = p->h | ht->nTableMask;
			Z_NEXT(p->val) = HT_HASH(ht, nIndex);
			HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(i);
			p++;
		} while (++i < ht->nNumUsed);
	} else {
		do {
			// 如果是要剔除的数据
			if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) {
				uint32_t j = i;
				Bucket *q = p;
				/**
				* 初始化两个bucket类型的指针p, q,循环遍历bucket数组
				* 每次循环, p++，遇到第一个IS_UNDEF， q =p;继续循环数组
				* 当再一次遇到一个正常数据时，把正常数据拷贝到q指向的位置，q++
				* 直到遍历完数据，更新nNumUsed等计数
				*/
				// 迭代计数器为0
				if (EXPECTED(ht->u.v.nIteratorsCount == 0)) {
					
					while (++i < ht->nNumUsed) {
						p++;
						if (EXPECTED(Z_TYPE_INFO(p->val) != IS_UNDEF)) {
							ZVAL_COPY_VALUE(&q->val, &p->val);
							q->h = p->h;
							nIndex = q->h | ht->nTableMask;
							q->key = p->key;
							Z_NEXT(q->val) = HT_HASH(ht, nIndex);
							HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(j);
							if (UNEXPECTED(ht->nInternalPointer == i)) {
								ht->nInternalPointer = j;
							}
							q++;
							j++;
						}
					}
				} else {
					uint32_t iter_pos = zend_hash_iterators_lower_pos(ht, 0);

					while (++i < ht->nNumUsed) {
						p++;
						if (EXPECTED(Z_TYPE_INFO(p->val) != IS_UNDEF)) {
							ZVAL_COPY_VALUE(&q->val, &p->val);
							q->h = p->h;
							nIndex = q->h | ht->nTableMask;
							q->key = p->key;
							Z_NEXT(q->val) = HT_HASH(ht, nIndex);
							HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(j);
							if (UNEXPECTED(ht->nInternalPointer == i)) {
								ht->nInternalPointer = j;
							}
							if (UNEXPECTED(i == iter_pos)) {
								zend_hash_iterators_update(ht, i, j);
								iter_pos = zend_hash_iterators_lower_pos(ht, iter_pos + 1);
							}
							q++;
							j++;
						}
					}
				}
				ht->nNumUsed = j;
				break;
			}
			nIndex = p->h | ht->nTableMask;
			Z_NEXT(p->val) = HT_HASH(ht, nIndex);
			HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(i);
			p++;
		} while (++i < ht->nNumUsed);
	}
	return SUCCESS;
}
参考资料
  • 《PHP7底层设计和源码实现》
  • 《PHP7内核剖析》
  • PHP中的Hash算法

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/716414.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

mac安装高版本git（更新git）

mac安装高版本git（更新git）

问题 问题&#xff1a;新下载的idea&#xff0c;此idea的版本较高&#xff0c;但是在工作发现这个版本的git存在一定漏洞会导致一些信息泄露问题。 1.安装Homebrew 对于Mac更新git&#xff0c;最简单的就是使用brew命令。所以我们首先下载homebrew。已下载的同学忽略直接下一…
阅读更多...
SN65HVD485EDR封装SOIC-8 半双工RS-485/RS-422收发器芯片 VP485

SN65HVD485EDR封装SOIC-8 半双工RS-485/RS-422收发器芯片 VP485

SN65HVD485EDR 主要的应用场景包括但不限于以下几个方面&#xff1a; 1. 工业自动化&#xff1a;在工业控制系统中&#xff0c;RS-485接口常用来连接传感器、执行器和其他现场设备到中央控制系统。由于SN65HVD485EDR 的高ESD保护和抗噪能力&#xff0c;它特别适合于工厂车间等…
阅读更多...
SpringCloud：Feign远程调用

SpringCloud：Feign远程调用

程序员老茶 &#x1f648;作者简介&#xff1a;练习时长两年半的Java up主 &#x1f649;个人主页&#xff1a;程序员老茶 &#x1f64a; P   S : 点赞是免费的&#xff0c;却可以让写博客的作者开心好久好久&#x1f60e; &#x1f4da;系列专栏&#xff1a;Java全栈&#…
阅读更多...
最新编程语言排行榜，C++ 和 Go 成为新王？！

最新编程语言排行榜，C++ 和 Go 成为新王？！

大家好&#xff0c; 我是不爱敲代码吖,2024 年 6 月最新的 TIOBE 编程语言排行榜已经发布&#xff0c;如图&#xff1a; 注意&#xff0c;TIOBE 编程语言排行榜是基于 全球 工程师的数量、课程、热门网站、第三方供应商综合计算出来的&#xff0c;只是一个编程语言流行度和趋势…
阅读更多...
office 修复命令

office 修复命令

System.Runtime.InteropServices.COMException:“远程调用失败 DISM /Online /Cleanup-Image /RestoreHealth
阅读更多...
[图解]建模相关的基础知识-11

[图解]建模相关的基础知识-11

1 00:00:00,700 --> 00:00:05,090 下一个知识点就是函数在集合上的限制 2 00:00:08,290 --> 00:00:10,200 符号可以这样来 3 00:00:10,210 --> 00:00:16,640 F然后一个往下的箭头A 4 00:00:16,650 --> 00:00:19,520 意思就是说F里面的元素 5 00:00:20,120 --&…
阅读更多...
中国人口密度分布图

中国人口密度分布图

原文链接https://mp.weixin.qq.com/s?__bizMzUyNzczMTI4Mg&mid2247679489&idx3&sna05d4c0bed51c611101f7c777420d27e&chksmfa77613ccd00e82ad4177706fe02c365ed2cdb5974664af1df4ed513bfba48f762260433c419&token808263816&langzh_CN&scene21#wec…
阅读更多...
AIOps在业务运维的最佳应用实践

AIOps在业务运维的最佳应用实践

随着企业IT基础架构的复杂性日益增加&#xff0c;传统运维模式难以满足高效、稳定的业务需求。AIOps&#xff08;人工智能运维&#xff09;作为一种新兴技术&#xff0c;通过数据驱动的自动化和智能化手段&#xff0c;有效提升了IT运维的效率和可靠性。本文将探讨AIOps在业务运…
阅读更多...
Golang | Leetcode Golang题解之第150题逆波兰表达式求值

Golang | Leetcode Golang题解之第150题逆波兰表达式求值

题目&#xff1a; 题解&#xff1a; func evalRPN(tokens []string) int {stack : make([]int, (len(tokens)1)/2)index : -1for _, token : range tokens {val, err : strconv.Atoi(token)if err nil {indexstack[index] val} else {index--switch token {case ""…
阅读更多...
利用CNN识别英文语音数字

利用CNN识别英文语音数字

问题总述 任何一个数字&#xff0c;都是由10个基数构成的&#xff0c;本任务目的是借助于机器来实现英文语音数字的识别。下面&#xff0c;利用语音特征提取技术和卷积神经网络模型&#xff0c;对英文语音数字进行识别以解决上述问题。 步骤一&#xff1a;提取音频文件的语音…
阅读更多...
【递归、搜索与回溯】综合练习二

【递归、搜索与回溯】综合练习二

综合练习二 1.组合2.目标和3.组合总和4.字母大小写全排列 点赞&#x1f44d;&#x1f44d;收藏&#x1f31f;&#x1f31f;关注&#x1f496;&#x1f496; 你的支持是对我最大的鼓励&#xff0c;我们一起努力吧!&#x1f603;&#x1f603; 1.组合 题目链接&#xff1a;77. 组…
阅读更多...
海康充电桩报文校验TCP校验和

海康充电桩报文校验TCP校验和

1 TCP校验文档校验文档要求&#xff1a; 校验码描述 校验码计算范围包含包头标识、消息头和消息体&#xff0c;校验算法采用 TCP 和校验&#xff0c;具体规则如下。 将待校验的所有数据分为 16 位的字&#xff08;大端序&#xff09;&#xff0c;如果总长度为奇数个字节&#…
阅读更多...
hadoop未授权访问命令执行漏洞复现-vulfocus

hadoop未授权访问命令执行漏洞复现-vulfocus

1 介绍 Hadoop YARN&#xff08;Yet Another Resource Negotiator&#xff09;的ResourceManager是集群资源管理的核心组件&#xff0c;负责分配和管理集群资源以及调度作业。如果ResourceManager出现未授权访问漏洞&#xff0c;可能允许未经认证的用户访问或操作集群资源&…
阅读更多...
Linux DNS域名解析

Linux DNS域名解析

DNS系统的作用及类型 整个 Internet 大家庭中连接了数以亿计的服务器、个人主机&#xff0c;其中大部分的网站、邮件等服务器都使用了域名形式的地址&#xff0c;如www.google.com、mail.163.com 等。很显然这种地址形式要比使用 64.233.189.147、202.108.33.74的IP地址形式更…
阅读更多...
Windows NT 3.5程序员讲述微软标志性“3D管道”屏幕保护程序的起源故事

Windows NT 3.5程序员讲述微软标志性“3D管道”屏幕保护程序的起源故事

人们使用屏保程序来防止 CRT 显示器"烧毁"&#xff0c;因为静态图像会永久损坏屏幕。像 3D Pipes 这样的屏保程序能在显示器处于非活动状态时为其提供动画效果&#xff0c;从而保护屏幕并延长其使用寿命。此外&#xff0c;它们还能在用户不使用电脑时为其提供可定制的…
阅读更多...
计算机组成原理之存储器（一）

计算机组成原理之存储器（一）

文章目录 存储器概述存储器的分类情况按照存储器在系统中的作用分类按存储介质分类按存取方式分类 主存储器的技术指标 存储器概述 程序的局部性原理&#xff08;构成多级存储系统的依据&#xff09;&#xff1a;在某一个时间段你频繁访问某一局部的存储器地址空间&#xff0c;…
阅读更多...
git 配置私人令牌

git 配置私人令牌

这里写自定义目录标题 获取私人令牌配置个人令牌 获取私人令牌 在个人设置里点击私人令牌选型&#xff0c;之后生成令牌即可。注意&#xff1a;令牌只会出现一次&#xff0c;务必保存好。 配置个人令牌 个人令牌&#xff1a;3c15c866fa61066212a83c66fd8133ba # 进入项目文…
阅读更多...
私有化、源码开放、无限制技术支持，一站式解决企业文档管理痛点

私有化、源码开放、无限制技术支持，一站式解决企业文档管理痛点

之前有个用户&#xff0c;当时他们需要查找一份两年前某个产品的设计图纸。在公司的文档库&#xff0c;一份份地翻阅&#xff0c;他花费了整整两天时间才找到所需的设计图纸。这种低效的文档查找方式严重影响了工作效率。 这种就是企业内部文档管理的问题&#xff0c;除了这个…
阅读更多...
Python私教张大鹏 Vue3整合AntDesignVue之Steps 步骤条

Python私教张大鹏 Vue3整合AntDesignVue之Steps 步骤条

引导用户按照流程完成任务的导航条。 何时使用 当任务复杂或者存在先后关系时&#xff0c;将其分解成一系列步骤&#xff0c;从而简化任务。 案例&#xff1a;步骤条组件 核心代码&#xff1a; <template><a-steps:current"1":items"[{title: Fin…
阅读更多...
LogicFlow 学习笔记——10. LogicFlow 进阶 边

LogicFlow 学习笔记——10. LogicFlow 进阶 边

我们可以基于 Vue 组件自定义边&#xff0c;可以在边上添加任何想要的 Vue 组件&#xff0c;甚至将原有的边通过样式隐藏&#xff0c;重新绘制。 如 Example3 中所示&#xff1a; 锚点 默认情况下&#xff0c;LogicFlow 只记录节点与节点的信息。但是在一些业务场景下&#…
阅读更多...
最新文章

Copyright @ 2022~2023