[PHP知识库]PHP7数组(zend_array)的实现

PHP7数组的实现

1 | 基本概念

1.1数组的语义

1.PHP的数组是一个字典，存着键-值（key-value）

2.PHP数组是有序的。即插入有序且遍历时也是有序的。

PHP使用HashTable来存储键值对，但不能保证其有序性，所以需要做一些额外的设计来保证有序性

1.2数组的概念

zend_array 对应的是HashTable

但PHP数组中分为package array 和hash array所以通过需要通过的两个hash函数来保留的下标的值。

1）bucket里面增加h字段。

2）哈希函数拆分成了hash1和hash2函数。hash1将key映射为h值，hash2将h值映射为slot的索引值。

3）bucket里面的key字段作为字符串key，不再表示数字key。这个h值的作用是什么呢？

一、由于HashTable中key可能是数字，也有可能是字符串，所以bucket在设计key的时候，需要做拆分，拆分成数字key和字符串key，在上图的bucket中，“h”代表数字key，“key”代表字符串key。实际上，对于数字key, hash1函数没有做任何事情，h值就是数字key。

二、每一个字符串key，经过hash1函数都会计算出一个h值。这个h值可以加快字符串key之间的比较速度。如果要比较两个字符串key1和key2是否相等，会首先比较key1和key2的h值是否相等，如果相等，再去比较字符串的长度以及内容。否则，可直接判定key1和key2不相等。在大部分场景，不同字符串的h值都不会发生碰撞，这大大提高了HashTable插入、查找的速度。

2 | PHP7数组的实现

PHP7为了解决哈希冲突使用了链地址法（另一种方案是开放地址法）

PHP7中，数组的核心结构是stuct _zend_array和bucket,并起了两个别名HashTable和zend_array

zend_types.h :line 248~270

typedef struct _zend_array HashTable; //line 249

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;
};// line 270

//line 91
typedef struct _zend_array      zend_array;

typedef struct _Bucket { //line 242
	zval              val;
	zend_ulong        h;                /* hash value (or numeric index)   */
	zend_string      *key;              /* string key or NULL for numerics */
} Bucket;