php 数组
本文转自 https://www.laruence.com/2020/02/25/3182.html
php5
php5中hashtable结构
typedef struct _hashtable {
uint nTableSize; /* 散列表大小, Hash值的区间 */
uint nTableMask; /* 等于nTableSize -1, 用于快速定位 */
uint nNumOfElements; /* HashTable中实际元素的个数 */
ulong nNextFreeElement; /* 下个空闲可用位置的数字索引 */
Bucket *pInternalPointer; /* 内部位置指针, 会被reset, current这些遍历函数使用 */
Bucket *pListHead; /* 头元素, 用于线性遍历 */
Bucket *pListTail; /* 尾元素, 用于线性遍历 */
Bucket **arBuckets; /* 实际的存储容器 */
dtor_func_t pDestructor;/* 元素的析构函数(指针) */
zend_bool persistent;
unsigned char nApplyCount; /* 循环遍历保护 */
zend_bool bApplyProtection;
#if ZEND_DEBUG
int inconsistent;
#endif
} HashTable;
查看上面的结构, 可以看出, 对于HashTable, 关键元素就是arBuckets了, 这个是实际存储的容器, 让我们来看看它的结构定义:
typedef struct bucket {
ulong h; /* 数字索引/hash值 */
uint nKeyLength; /* 字符索引的长度 */
void *pData; /* 数据 */
void *pDataPtr; /* 数据指针 */
struct bucket *pListNext; /* 下一个元素, 用于线性遍历 */
struct bucket *pListLast; /* 上一个元素, 用于线性遍历 */
struct bucket *pNext; /* 处于同一个拉链中的下一个元素 */
struct bucket *pLast; /* 处于同一拉链中的上一个元素 */
char arKey[1]; /* 节省内存,方便初始化的技巧 */
} Bucket;
h是元素的Hash值,对于数字索引的元素,h为直接索引值(通过nKeyLength=0来表示是数字索引).而对于字符串索引来说, 索引值保存在arKey中, 索引的长度保存在nKeyLength中.
在Bucket中，实际的数据是保存在pData指针指向的内存块中，通常这个内存块是系统另外分配的。但有一种情况例外，就是当Bucket保存 的数据是一个指针时，HashTable将不会另外请求系统分配空间来保存这个指针，而是直接将该指针保存到pDataPtr中，然后再将pData指向本结构成员的地址。这样可以提高效率，减少内存碎片。由此我们可以看到PHP HashTable设计的精妙之处。如果Bucket中的数据不是一个指针，pDataPtr为NULL。
HashTable的pListhHead指向线性列表形式下的第一个元素, 上图中是元素1, pListTail指向的是最后一个元素0, 而对于每一个元素pListNext就是红色线条画出的线性结构的下一个元素, 而pListLast是上一个元素.
pInternalPointer指向当前的内部指针的位置, 在对数组进行顺序遍历的时候, 这个指针指明了当前的元素.
当在线性(顺序)遍历的时候, 就会从pListHead开始, 顺着Bucket中的pListNext/pListLast, 根据移动pInternalPointer, 来实现对所有元素的线性遍历.
比如, 对于foreach, 如果我们查看它生成的opcode序列, 我们可以发现, 在foreach之前, 会首先有个FE_RESET来重置数组的内部指针, 也就是pInternalPointer(关于foreach可以参看深入理解PHP原理之foreach), 然后通过每次FE_FETCH来递增pInternalPointer,从而实现顺序遍历.
php7
优化点：
- 优化zval存储，减少内存占用
- 缓存局部性问题，php5中hashtable的bucket和zval都是独立分配的，会导致遍历和顺序访问一个数组时，缓存不友好。
比如如图所示在PHP代码中常见的foreach一个数组， 就会发生多次的内存跳跃.
- 和1类似，在PHP5的Hashtable中，要访问一个zval，因为是zval， 那需要至少解指针俩次，一方面是缓存不友好，另外一方面也是效率低下。比如上图中，蓝色框的部分，我们找到数组中的bucket以后，还需要解开zval，才可以读取到实际的zval的内容。 也就是需要发生俩次内存读取。效率低下。
zend_array
定义了一个新的结构体zend_array，可替代原来的hashtable。
zend_array定义：
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;
};相比PHP5时代的Hashtable，zend_array的内存占用从PHP5点72个字节，降低到了56个字节，想想一个PHP生命进程中成千上万的数组，内存降低明显。
此处再次特别说明下上面zend_array定义中的ZEND_ENDIAN_LOHT_4这个作用，这个是为了解决大小端问题，在大端小端上都能让其中的元素保证同样的内存存储顺序，可以方便我们写出通用的位操作。 在PHP7中，位操作应用的很多，因为这样一来一个字节就可以保存8个状态位， 很节省内存:)
#ifdef WORDS_BIGENDIAN
# define ZEND_ENDIAN_LOHI_4(a, b, c, d) d; c; b; a;
#else
# define ZEND_ENDIAN_LOHI_4(a, b, c, d) a; b; c; d;
#endif而数据会核心保存在arData中，arData是一个Bucket数组，Bucket定义:
typedef struct _Bucket {
zval val;
zend_ulong h; /* hash value (or numeric index) */
zend_string *key; /* string key or NULL for numerics */
} Bucket再对比看下PHP5多Bucket:
typedef struct bucket {
ulong h; /* Used for numeric indexing */
uint nKeyLength;
void *pData;
void *pDataPtr;
struct bucket *pListNext;
struct bucket *pListLast;
struct bucket *pNext;
struct bucket *pLast;
const char *arKey;
} Bucket;内存占用从72字节，降低到了32个字节，想想一个PHP进程中几十万的数组元素，这个内存降低就更明显了.
对比的看，
- 现在的冲突拉链被bauck.zval->u2.next替代， 于是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.
现在我们来整体看下zend_array的组织图：
PHP 数组的基本实现
散列表主要由两部分组成：存储元素数组、散列函数。散列表的基本实现前面已经探讨过，PHP 中的数组除了具备散列表的基本特点之外，还有一个特别的地方，那就是它是有序的（与Java中的HashMap的无序有所不同）：数组中各元素的顺序和插入顺序一致。这个是怎么实现的呢？
插入数据
插入时会检查数组是否已经分配存储空间，因为初始化并没有实际分配 arData 的内存，在第一次插入时才会根据 nTableSize 的大小分配，分配以后会把 HashTable->u.flags 打上 HASH_FLAG_INITIALIZED 掩码，这样，下次插入时发现已经分配了就不会重复操作，这段检查逻辑位于 _zend_hash_add_or_update_i 函数中：
if (UNEXPECTED(!(HT_FLAGS(ht) & HASH_FLAG_INITIALIZED))) {
zend_hash_real_init_mixed(ht);
if (!ZSTR_IS_INTERNED(key)) {
zend_string_addref(key);
HT_FLAGS(ht) &= ~HASH_FLAG_STATIC_KEYS;
zend_string_hash_val(key);
}
goto add_to_hash;
}
如果 arData 还没有分配，则最终由 zend_hash_real_init_mixed_ex 完成内存分配：
分配完 arData 的内存后就可以进行插入操作了，插入时先将元素按照顺序插入 arData，然后将其在 arData 数组中的位置存储到根据 key 的散列值与 nTableMask 计算得到的中间映射表中的对应位置：
哈希冲突
PHP 数组底层的散列表采用链地址法解决哈希冲突，即将冲突的 Bucket 串成链表。
HashTable 中的 Bucket 会记录与它冲突的元素在 arData 数组中的位置，这也是一个链表，冲突元素的保存位置不在 Bucket 结构中，而是保存在了存储元素 zval 的 u2 结构中，即 Bucket.val.u2.next，所以插入时分为以下两步：
// 将映射表中原来的值保存到新 Bucket 中，哈希冲突时会用到（以链表方式解决哈希冲突）
Z_NEXT(p->val) = HT_HASH_EX(arData, nIndex);
// 再把新元素数组存储位置更新到数据表中
// 保存idx：((unit32_t*))(ht->arData)[nIndex] = idx
HT_HASH_EX(arData, nIndex) = HT_IDX_TO_HASH(idx);
数组查找
清楚了 HashTable 的实现和哈希冲突的解决方式之后，查找的过程就比较简单了：首先根据 key 计算出的散列值与 nTableMask 计算得到最终散列值 nIndex，然后根据散列值从中间映射表中得到存储元素在有序存储数组中的位置 idx，接着根据 idx 从有序存储数组（即 arData）中取出 Bucket，遍历该 Bucket，判断 Bucket 的 key 是否是要查找的 key，如果是则终止遍历，否则继续根据 zval.u2.next 遍历比较。
参考文章
删除数据
关于数组数据删除前面我们在介绍散列表中的 nNumUsed 和 nNumOfElements 字段时已经提及过，从数组中删除元素时，并没有真正移除，并重新 rehash，而是当 arData 满了之后，才会移除无用的数据，从而提高性能。即数组在需要扩容的情况下才会真正删除元素：首先检查数组中已删除元素所占比例，如果比例达到阈值则触发重新构建索引的操作，这个过程会把已删除的 Bucket 移除，然后把后面的 Bucket 往前移动补上空位，如果还没有达到阈值则会分配一个原数组大小 2 倍的新数组，然后把原数组的元素复制到新数组上，最后重建索引，重建索引会将已删除的 Bucket 移除。
https://www.laruence.com/2009/08/23/1065.html
https://www.cnblogs.com/mzhaox/p/11295445.html