PHP7 array的实现源码

array的函数我分为几类

1、像操作hash表一样的，unset()、array['key']=1、array['key'], array_keys, array_values()

2、像操作链表一样的，array_push(), array_pop, array_unshift, array_shift

从以上看，array的实现像是链表，又像是hash表，那到底是什么呢？

PHP7的数组是hash表实现的，我们还是看代码，在zend中zend_array实现了数组

struct _zend_array {
	zend_refcounted_h gc; // 垃圾回收
	union {
		struct {
			ZEND_ENDIAN_LOHI_4(
				zend_uchar    flags,
				zend_uchar    nApplyCount,
				zend_uchar    nIteratorsCount,
				zend_uchar    consistency)
		} v;
		uint32_t flags; 
	} u;
	// 用于散列函数映射存储元素在arData数组中的下标
	uint32_t          nTableMask; 
	// 存储元素数组，每个元素的结构统一成bucket，arData指向第一个bucket
	Bucket            *arData; 
	// 已经使用的bucket数目
	uint32_t          nNumUsed; 
	// 数组中实际存储的元素数
	uint32_t          nNumOfElements; 
	// hash表的大小
	uint32_t          nTableSize; 
	// 下一个可用的数值索引
	uint32_t          nInternalPointer; 
	zend_long         nNextFreeElement;// 指向下一个指针
	dtor_func_t       pDestructor;
};

其中bucket的数据结构是

typedef struct _Bucket {
	zval              val; 	// hash元素的value
	zend_ulong        h;    // hash值 或者是索引
	zend_string      *key;  // key的值
} Bucket; 

散列表通过hash函数写入到bucket数组中，散列表本身是无序的，那数组的遍历是如何实现的呢？遍历的时候是按照元素的插入顺序完成的。那如何实现array的有序性呢？PHP中的散列表在散列函数与元素数组之间加入了一层映射表，这个映射表也是一个数组，大小和存储元素数组相同，它存储的元素类型是整型，用于保存元素在实际存储的有序数组的下标。元素按照先后顺序依次插入实际存储数组，然后将其数组下标按照散列函数散列出来的位置存储到新加的映射表中。（那么，下一个问题又出现了，hash冲突了怎么办，中间映射表中的一个下标可能存放两个元素数组中的下标。）这个问题下保留，但是我们看代码，并没有发现那里存储了这个映射表。

事实上，它与arData放在了一起，在数组初始化时不仅仅分配了用于存储bucket的内存，还会分配相同数量的uint32_t大小的空间。

#define HT_SET_DATA_ADDR(ht, ptr) do { 
		// 申请内存的时候，arData指向存储元素数组的位置
		(ht)->arData = (Bucket*)(((char*)(ptr)) + HT_HASH_SIZE((ht)->nTableMask)); 
	} while (0)

参考：https://zhuanlan.zhihu.com/p/45338807