[译] PHP7 数组：HashTable-11130372

jinying8869

　　http://joshuais.me/yi-php7-shu-zu-hashtable/?utm_source=tuicool&utm_medium=referral
[译] PHP7 数组：HashTable
　　November 17, 2016
简介
　　几乎每个C程序中都会使用到哈希表。鉴于C语言只允许使用整数作为数组的键名，PHP 设计了哈希表，将字符串的键名通过哈希算法映射到大小有限的数组中。这样无法避免的会产生碰撞，PHP 使用了链表解决这个问题。
　　众多哈希表的实现方式，无一完美。每种设计都着眼于某一个侧重点，有的减少了 CPU 使用率，有的更合理地使用内存，有的则能够支持线程级的扩展。

　　实现哈希表的方式之所以存在多样性，是因为每种实现方式都只能在各自的关注点上提升，而无法面面俱到。

数据结构
　　开始介绍之前，我们需要事先声明一些事情：

• 　　哈希表的键名可能是字符串或者是整数。当是字符串时，我们声明类型为 zend_string；当是整数时，声明为 zend_ulong。
  
• 　　哈希表的顺序遵循表内元素的插入顺序。
  
• 　　哈希表的容量是自动伸缩的。
  
• 　　在内部，哈希表的容量总是2的倍数。
  
• 　　哈希表中每个元素一定是 zval 类型的数据。
  

　　以下是 HashTable 的结构体：
struct _zend_array {　　zend_refcounted_h gc;
　　union {
　　struct {
　　ZEND_ENDIAN_LOHI_4(
　　zend_uchar    flags,
　　zend_uchar    nApplyCount,
　　zend_uchar    nIteratorsCount,
　　zend_uchar    reserve)
　　} 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;};
　　这个结构体占56个字节。
　　其中最重要的字段是 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;
　　Bucket 中不再使用指向一个 zval 类型数据的指针，而是直接使用数据本身。因为在 PHP7 中，zval 不再使用堆分配，因为需要堆分配的数据会作为 zval 结构中的一个指针存储。（比如 PHP 的字符串）。
　　下面是 arData 在内存中存储的结构：

　　我们注意到所有的Bucket都是按顺序存放的。
插入元素
　　PHP 会保证数组的元素按照插入的顺序存储。这样当使用 foreach 循环数组时，能够按照插入的顺序遍历。假设我们有这样的数组：