散列表-PHP 数组底层实现原理（一）
- 1 min数据结构与算法系列（二十四）
数组是 PHP 中非常强大、灵活的一种数据类型，和 Java、C 等静态语言不同，我们在初始化 PHP 数组的时候不必指定大小和存储数据的类型，在赋值的时候可以通过数字索引，也可以通过字符串索引的方式：
于 PHP 数组的强大特性，我们可以轻易实现更加复杂的数据结构，比如栈、队列、列表、集合、字典等。PHP 数组功能之所以如此强大，得益于底层基于散列表实现。
PHP数组底层数据结构
PHP 数组底层依赖的散列表数据结构定义如下（位于 Zend/zend_types.h）：
这个散列表中有很多成员，我们挑几个比较重要的来讲讲：
- 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：这个联合体结构主要用于一些辅助作用
Bucket 的结构比较简单，主要用来保存元素的 key 和 value，以及一个整型的 h（散列值，或者叫哈希值）：如果元素是数值索引，则其值就是数值索引的值；如果是字符串索引，那么其值就是 key 通过 Time33 算法计算得到的散列值，h 的值用来最终映射元素的存储位置。Bucket 的数据结构如下：
PHP 数组的基本实现
散列表主要由两部分组成：存储元素数组、散列函数。散列表的基本实现我们前面已经探讨过，PHP 中的数组除了具备散列表的基本特点之外，还有一个特别的地方，那就是它是有序的（与Java中的HashMap的无序有所不同）：数组中各元素的顺序和插入顺序一致。这个是怎么实现的呢？
为了实现 PHP 数组的有序性，PHP 底层的散列表在散列函数与元素数组之间加了一层映射表，这个映射表也是一个数组，大小和存储元素的数组相同，存储元素的类型为整型，用于保存元素在实际存储的有序数组中的下标 —— 元素按照先后顺序依次插入实际存储数组，然后将其数组下标按照散列函数散列出来的位置存储在新加的映射表中：
这样，就可以完成最终存储数据的有序性了。
PHP 数组底层结构中并没有显式标识这个中间映射表，而是与 arData 放到了一起，在数组初始化的时候并不仅仅分配用于存储 Bucket 的内存，还会分配相同数量的 uint32_t 大小的空间，这两块空间是一起分配的，然后将 arData 偏移到存储元素数组的位置，而这个中间映射表就可以通过 arData 向前访问到。
今天我们主要分享了 PHP 数组底层散列表数据结构以及 PHP 数组有序性实现的理论基础，明天我们接着分享 PHP 数组初始化、插入、查找、删除及散列冲突（哈希冲突）的处理。