PHP中数组的实现

PHPer们应该都知道，PHP中无所不能的数组是通过Hashtable+双向链表的形式实现的。

那hash和链表到底是怎么一种组织方式呢？下面我们开始细细研究。

hashtable实现及组织方式

php5版本

php7版本

Zend/zend_types.h

struct _zend_array {
	zend_refcounted_h gc;
	union {
		struct {
			ZEND_ENDIAN_LOHI_4(
				zend_uchar    flags,
				zend_uchar    _unused,
				zend_uchar    nIteratorsCount,
				zend_uchar    _unused2)
		} v;
		uint32_t flags;
	} u;
	uint32_t          nTableMask;
	Bucket           *arData;
	uint32_t          nNumUsed;
	uint32_t          nNumOfElements;
	uint32_t          nTableSize;
	uint32_t          nInternalPointer;
	zend_long         nNextFreeElement;
	dtor_func_t       pDestructor;
};

/*
 * HashTable Data Layout
 * =====================
 *
 *                 +=============================+
 *                 | HT_HASH(ht, ht->nTableMask) |
 *                 | ...                         |
 *                 | HT_HASH(ht, -1)             |
 *                 +-----------------------------+
 * ht->arData ---> | Bucket[0]                   |
 *                 | ...                         |
 *                 | Bucket[ht->nTableSize-1]    |
 *                 +=============================+
 */

这个散列表中有很多成员，我们挑几个比较重要的来讲讲：

arData：散列表中保存存储元素的数组，其内存是连续的，arData指向数组的起始位置；

nTableSize：数组的总容量，即可以容纳的元素数，arData 的内存大小就是根据这个值确定的，它的大小的是2的幂次方，最小为8，然后按照 8、16、32…依次递增；

nTableMask：这个值在散列函数根据 key 的哈希值映射元素的时候用到，它的值实际就是 nTableSize 的负数，即 nTableMask = -nTableSize，用位运算来表示就是 nTableMask = ~nTableSize+1；

nNumUsed、nNumOfElements：nNumUsed 是指数组当前使用的 Bucket 数，但不是数组有效元素个数，因为某个数组元素被删除后并没有立即从数组中删除，而是将其标记为 IS_UNDEF，只有在数组需要扩容时才会真正删除，nNumOfElements 则表示数组中有效的元素数量，即调用 count 函数返回值，如果没有扩容，nNumUsed 一直递增，无论是否删除元素；

nNextFreeElement：这个是给自动确定数值索引使用的，默认从 0 开始，比如 $arr[] = 200，这个时候 nNextFreeElement 值会自动加 1；

pDestructor：当删除或覆盖数组中的某个元素时，如果提供了这个函数句柄，则在删除或覆盖时调用此函数，对旧元素进行清理；
u：这个联合体结构主要用于一些辅助作用

数据会核心保存在arData中，arData是一个Bucket数组，Bucket定义：

typedef struct _Bucket {
    zval              val; 	/*  数组值 */
    zend_ulong        h; 		/* 哈希值或数值索引   */
    zend_string      *key;  	/* string key or NULL for numerics */
} Bucket

整体看下zend_array的组织图：

5和7下对比分析

现在的冲突拉链被bauck.zval->u2.next替代（参见PHP7变量的实现之zval），于是bucket->pNext, bucket->pLast可以去掉了。
zend_array->arData是一个数组，所以也就不再需要pListNext, pListLast来保持顺序了, 他们也可以去掉了。现在数组中元素的先后顺序，完全根据它在arData中的index顺序决定，先加入的元素在低的index中。
PHP7中的Bucket现在直接保存一个zval, 取代了PHP5时代bucket中的pData和pDataPtr。
最后就是PHP7中现在使用zend_string作为数组的字符串key，取代了PHP5时代bucket的*key, nKeylength.

数组查找过程

清楚了 HashTable 的实现和哈希冲突的解决方式之后，查找的过程就比较简单了：首先根据 key 计算出的散列值与 nTableMask 计算得到最终散列值 nIndex，然后根据散列值从中间映射表中得到存储元素在有序存储数组中的位置 idx，接着根据 idx 从有序存储数组（即 arData）中取出 Bucket，遍历该 Bucket，判断 Bucket 的 key 是否是要查找的 key，如果是则终止遍历，否则继续根据 zval.u2.next 遍历比较。来自：PHP 数组底层实现原理

数组删除过程

关于数组数据删除前面我们在介绍散列表中的 nNumUsed 和 nNumOfElements 字段时已经提及过，从数组中删除元素时，并没有真正移除，并重新 rehash，而是当 arData 满了之后，才会移除无用的数据，从而提高性能。即数组在需要扩容的情况下才会真正删除元素：首先检查数组中已删除元素所占比例，如果比例达到阈值则触发重新构建索引的操作，这个过程会把已删除的 Bucket 移除，然后把后面的 Bucket 往前移动补上空位，如果还没有达到阈值则会分配一个原数组大小 2 倍的新数组，然后把原数组的元素复制到新数组上，最后重建索引，重建索引会将已删除的 Bucket 移除。

对应底层代码如下：

问题解答数组遍历for和foreach的区别

for 和 foreach有没有性能差异

注：以下纯属个人瞎猜，还没研究源码。

PHP5中，arData是通过链表组织的，foreach通过从head遍历到tail完成。而for的话，需要先计算hash值，故foreach性能更优。

PHP7中，arData是一个数组，for和foreach没有多大的差别。