PHP 배열의 기본 구현 논리에 대한 종합적인 분석

머리말

php 편집기 Banana는 PHP 배열의 기본 구현 논리를 종합적으로 분석합니다. PHP의 배열은 유연하고 강력한 데이터 구조이지만 그 이면의 구현 논리는 상당히 복잡합니다. 이 기사에서는 배열의 내부 구조, 인덱스와 해시 테이블 간의 관계, 배열의 추가, 삭제, 수정 및 쿼리 작업을 구현하는 방법을 포함하여 PHP 배열의 기본 원칙을 자세히 살펴보겠습니다. PHP 배열의 기본 구현 논리를 이해함으로써 개발자는 이 중요한 데이터 구조인 배열을 더 잘 이해하고 활용할 수 있습니다.

배열의 구조

PHP 커널에서 배열은 어떻게 생겼나요? PHP의 소스 코드에서 다음과 같은 구조를 볼 수 있습니다.

<code>// 定义结构体别名为 HashTable
typedef struct _zend_array HashTable;

struct _zend_array {
	// <strong class="keylink">GC</strong> 保存引用计数，内存管理相关；本文不涉及
	zend_refcounted_h gc;
	// u 储存辅助信息；本文不涉及
	u<strong class="keylink">NIO</strong>n {
		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;
	// arData 指向储存元素的数组第一个 Bucket，Bucket 为统一的数组元素类型
	Bucket           *arData;
	// 已使用 Bucket 数
	uint32_t          nNumUsed;
	// 数组内有效元素个数
	uint32_t          nNumOfElements;
	// 数组总容量
	uint32_t          nTableSize;
	// 内部指针，用于遍历
	uint32_t          nInternalPointer;
	// 下一个可用数字<strong class="keylink">索引</strong>
	zend_long         nNextFreeElement;
	// 析构函数
	dtor_func_t       pDestructor;
};</code>

• nNumUsed와 nNumOfElements의 차이점: nNumUsed는 다음을 참조합니다. arData 배열에 사용된 Bucket의 개수입니다. 요소를 삭제한 후 배열은 요소의 해당 값 유형을 설정하기 때문입니다. >Bucket을 IS_UNDEF로 변경하고(요소가 삭제될 때마다 배열을 이동하고 다시 색인화하는 것은 시간 낭비이기 때문입니다) nNumOfElements는 이에 해당합니다. 배열의 실제 요소 수입니다. nNumUsed 和 nNumOfElements 的区别：nNumUsed 指的是 arData 数组中已使用的 Bucket 数，因为数组在删除元素后只是将该元素 Bucket 对应值的类型设置为 IS_UNDEF（因为如果每次删除元素都要将数组移动并重新索引太浪费时间），而 nNumOfElements 对应的是数组中真正的元素个数。

• nTableSize 数组的容量，该值为 2 的幂次方。PHP 的数组是不定长度但 C 语言的数组定长的，为了实现 PHP 的不定长数组的功能，采用了「扩容」的机制，就是在每次插入元素的时候判断 nTableSize 是否足以储存。如果不足则重新申请 2 倍 nTableSize 大小的新数组，并将原数组复制过来（此时正是清除原数组中类型为 IS_UNDEF 元素的时机）并且重新索引。

• nNextFreeElement 保存下一个可用数字索引，例如在 PHP 中 $a[] = 1; 这种用法将插入一个索引为 nNextFreeElement 的元素，然后 nNextFreeElement  自增 1。

_zend_array 这个结构先讲到这里，有些结构体成员的作用在下文会解释，不用紧张O(∩_∩)O哈哈~。下面来看看作为数组成员的 Bucket 结构：

<code>typedef struct _Bucket {
	// 数组元素的值
	zval              val;
	// key 通过 Time 33 <strong class="keylink">算法</strong>计算得到的哈希值或数字索引
	zend_ulong        h;
	// 字符键名，数字索引则为 NULL
	zend_string      *key;
} Bucket;</code>

数组访问

我们知道 PHP 数组是基于哈希表实现的，而与一般哈希表不同的是 PHP 的数组还实现了元素的有序性，就是插入的元素从内存上来看是连续的而不是乱序的，为了实现这个有序性 PHP 采用了「映射表」技术。下面就通过图例说明我们是如何访问 PHP 数组的元素 :-D。

注意：因为键名到映射表下标经过了两次散列运算，为了区分本文用哈希特指第一次散列，散列即为第二次散列。

由图可知，映射表和数组元素在同一片连续的内存中，映射表是一个长度与存储元素相同的整型数组，它默认值为 -1 ，有效值为 Bucket 数组的下标。而 HashTable->arData 指向的是这片内存中 Bucket 数组的第一个元素。

举个例子 $a['key'] 访问数组 $a 中键名为 key 的成员，流程介绍：首先通过 Time 33 算法计算出 key 的哈希值，然后通过散列算法计算出该哈希值对应的映射表下标，因为映射表中保存的值就是 Bucket 数组中的下标值，所以就能获取到 Bucket 数组中对应的元素。

现在我们来聊一下散列算法，就是通过键名的哈希值映射到「映射表」的下标的算法。其实很简单就一行代码：

<code>nIndex = h | ht->nTableMask;</code>

将哈希值和 nTableMask 进行或运算即可得出映射表的下标，其中 nTableMask 数值为 nTableSize 的负数。并且由于  nTableSize 的值为 2 的幂次方，所以 h | ht->nTableMask 的取值范围在 [-nTableSize, -1]nTableSize 배열의 용량, 이 값은 2의 거듭제곱입니다. PHP의 배열은 가변 길이이지만 C 언어 배열은 고정 길이입니다. PHP의 가변 길이 배열 기능을 구현하기 위해 매 nTableSize를 결정하는 "확장" 메커니즘이 채택됩니다. 요소가 삽입되는 시간이면 충분합니까? 부족할 경우 nTableSize 크기의 2배인 새 배열을 다시 적용하고 원래 배열을 복사합니다. 원래 배열) 및 재인덱싱.

nNextFreeElement는 사용 가능한 다음 숫자 인덱스를 저장합니다(예: PHP $a[] = 1;). 이 사용법은 인덱스를 로 삽입합니다. nNextFreeElement 요소가 있으면 nNextFreeElement가 1씩 증가합니다.

_zend_array 이 구조는 여기에서 먼저 논의될 것입니다. 일부 구조 멤버의 기능은 아래에 설명될 것이므로 긴장하지 마십시오. O(∩_∩)O 하하~. 배열 멤버인 Bucket 구조를 살펴보겠습니다.

<code>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);
	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;
			
			if (flag & HASH_ADD) { // 指定 add 操作
				if (!(flag & HASH_UPDATE_INDIRECT)) { // 若不允许更新间接类型变量则直接返回
					return NULL;
				}
				// 确定当前值和新值不同
				ZEND_ASSERT(&p->val != pData);
				// data 指向原数组成员值
				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 { // 没有指定 add 操作
				// 确定当前值和新值不同
				ZEND_ASSERT(&p->val != pData);
				// data 指向原数组元素值
				data = &p->val;
				// 允许更新间接类型变量则 data 指向对应的变量
				if ((flag & HASH_UPDATE_INDIRECT) && Z_TYPE_P(data) == IS_INDIRECT) {
					data = Z_INDIRECT_P(data);
				}
			}
			if (ht->pDestructor) { // 析构函数存在
				// 执行析构函数
				ht->pDestructor(data);
			}
			// 将 pData 的值复制给 data
			ZVAL_COPY_VALUE(data, pData);
			return data;
		}
	}
	// 如果哈希表已满，则进行扩容
	ZEND_HASH_IF_FULL_DO_RESIZE(ht);

add_to_hash:
	// 数组已使用 Bucket 数 +1
	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 为新元素对应的 Bucket
	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);
	}
	// 计算键名的哈希值并赋值给 p
	p->h = h = ZSTR_H(key);
	// 将 pData 赋值该 Bucket 的 val
	ZVAL_COPY_VALUE(&p->val, pData);
	// 计算映射表下标
	nIndex = h | ht->nTableMask;
	// 解决冲突，将原映射表中的内容赋值给新元素变量值的 u2.next 成员
	Z_NEXT(p->val) = HT_HASH(ht, nIndex);
	// 将映射表中的值设为 idx
	HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx);

	return &p->val;
}</code>

Array access🎜PHP 배열은 해시 테이블을 기반으로 구현된다는 것을 알고 있으며, 일반 해시 테이블과 다른 점은 PHP가 배열 또한 요소의 질서가 달성됩니다. 즉, 삽입된 요소는 메모리 관점에서 연속적이며 순서가 어긋나지 않습니다. 이러한 질서를 달성하기 위해 PHP는 "매핑 테이블" 기술을 사용합니다. 다음은 PHP 배열의 요소에 액세스하는 방법을 보여주는 그림입니다. :-D. 🎜🎜🎜🎜참고 : 매핑 테이블 첨자에 대한 키 이름이 두 번 해싱되었기 때문에 이 기사를 구별하기 위해 해시는 첫 번째 해시를 참조하고 해시는 두 번째 해시를 참조합니다. 🎜🎜🎜그림에서 볼 수 있듯이 매핑 테이블과 배열 요소는 동일한 연속 메모리에 있습니다. 매핑 테이블은 저장 요소와 길이가 동일한 정수 배열입니다. 기본값은 -1이고 유효한 값입니다. Bucket code>입니다. 배열의 첨자입니다. 그리고 HashTable->arData는 이 메모리에 있는 Bucket 배열의 첫 번째 요소를 가리킵니다. 🎜🎜예를 들어 $a['key']는 $a 배열에서 키 이름이 key인 멤버에 액세스합니다. 도입: 첫 번째 통과 Time 33 알고리즘은 key의 해시 값을 계산한 다음, 매핑 테이블에 저장된 값이 키이기 때문에 해시 알고리즘을 사용하여 해시 값에 해당하는 매핑 테이블 첨자를 계산합니다. code>Bucket code> 배열의 아래 첨자 값이므로 Bucket 배열의 해당 요소를 얻을 수 있습니다. 🎜🎜이제 키 이름의 해시 값을 "매핑 테이블"의 첨자에 매핑하는 알고리즘인 해싱 알고리즘에 대해 이야기해 보겠습니다. 실제로 코드 한 줄이면 매우 간단합니다. 🎜rrreee🎜또는 해시 값과 nTableMask를 사용하여 매핑 테이블의 첨자를 가져옵니다. 여기서 nTableMask의 값 >는 nTableSize의 음수입니다. 그리고 nTableSize의 값은 2의 거듭제곱이므로 h |ht->nTableMask의 값 범위는 [-nTableSize, -1]는 정확히 매핑 테이블의 아래 첨자 범위 내에 있습니다. 간단한 "나머지" 연산을 사용하지 않고 "비트별 OR" 연산을 사용하는 수고를 감수해야 하는 이유는 무엇입니까? "비트별 OR" 연산은 "나머지" 연산보다 훨씬 빠르기 때문에 자주 사용되는 이 연산의 경우 더 복잡한 구현으로 인한 시간 최적화는 그만한 가치가 있다고 생각합니다. 🎜🎜해시 충돌🎜🎜서로 다른 키 이름의 해시 값을 해싱하여 계산한 "매핑 테이블" 첨자가 동일할 수 있어 해시 충돌이 발생합니다. 이러한 상황에서 PHP는 "체인 주소 방법"을 사용하여 이를 해결합니다. 다음 그림은 해시 충돌이 있는 요소에 액세스하는 상황을 보여줍니다. 🎜🎜🎜🎜<p>这看似与第一张图差不多，但我们同样访问 <code>$a['key'] 的过程多了一些步骤。首先通过散列运算得出映射表下标为 -2 ，然后访问映射表发现其内容指向 arData 数组下标为 1 的元素。此时我们将该元素的 key 和要访问的键名相比较，发现两者并不相等，则该元素并非我们所想访问的元素，而元素的 val.u2.next 保存的值正是下一个具有相同散列值的元素对应 arData 数组的下标，所以我们可以不断通过 next 的值遍历直到找到键名相同的元素或查找失败。

插入元素

插入元素的函数 _zend_hash_add_or_update_i ，基于 PHP 7.2.9 的代码如下：

<code>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);
	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;
			
			if (flag & HASH_ADD) { // 指定 add 操作
				if (!(flag & HASH_UPDATE_INDIRECT)) { // 若不允许更新间接类型变量则直接返回
					return NULL;
				}
				// 确定当前值和新值不同
				ZEND_ASSERT(&p->val != pData);
				// data 指向原数组成员值
				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 { // 没有指定 add 操作
				// 确定当前值和新值不同
				ZEND_ASSERT(&p->val != pData);
				// data 指向原数组元素值
				data = &p->val;
				// 允许更新间接类型变量则 data 指向对应的变量
				if ((flag & HASH_UPDATE_INDIRECT) && Z_TYPE_P(data) == IS_INDIRECT) {
					data = Z_INDIRECT_P(data);
				}
			}
			if (ht->pDestructor) { // 析构函数存在
				// 执行析构函数
				ht->pDestructor(data);
			}
			// 将 pData 的值复制给 data
			ZVAL_COPY_VALUE(data, pData);
			return data;
		}
	}
	// 如果哈希表已满，则进行扩容
	ZEND_HASH_IF_FULL_DO_RESIZE(ht);

add_to_hash:
	// 数组已使用 Bucket 数 +1
	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 为新元素对应的 Bucket
	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);
	}
	// 计算键名的哈希值并赋值给 p
	p->h = h = ZSTR_H(key);
	// 将 pData 赋值该 Bucket 的 val
	ZVAL_COPY_VALUE(&p->val, pData);
	// 计算映射表下标
	nIndex = h | ht->nTableMask;
	// 解决冲突，将原映射表中的内容赋值给新元素变量值的 u2.next 成员
	Z_NEXT(p->val) = HT_HASH(ht, nIndex);
	// 将映射表中的值设为 idx
	HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx);

	return &p->val;
}</code>

 扩容

前面将数组结构的时候我们有提到扩容，而在插入元素的代码里有这样一个宏 ZEND_HASH_IF_FULL_DO_RESIZE，这个宏其实就是调用了 zend_hash_do_resize 函数，对数组进行扩容并重新索引。注意：并非每次 Bucket 数组满了都需要扩容，如果 Bucket 数组中 IS_UNDEF 元素的数量占较大比例，就直接将 IS_UNDEF 元素删除并重新索引，以此节省内存。下面我们看看 zend_hash_do_resize 函数：

重新索引的逻辑在 zend_hash_rehash 函数中，代码如下：

 总结

嗯哼，本文就到此结束了，因为自身水平原因不能解释的十分详尽清楚。这算是我写过最难写的内容了，写完之后似乎觉得这篇文章就我自己能看明白/(ㄒoㄒ)/~~因为文笔太辣鸡。想起一句话「如果你不能简单地解释一样东西，说明你没真正理解它。」PHP 的源码里有很多细节和实现我都不算熟悉，这篇文章只是一个我的 PHP 底层学习的开篇，希望以后能够写出真正深入浅出的好文章。

위 내용은 PHP 배열의 기본 구현 논리에 대한 종합적인 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!