PHP HashTable总结
本篇文章主要是对 PHP HashTable 总结，下面的参考链接是很好的学习资料。学习“散列”这个数据结构—推荐《数据结构与算法分析 C语言描述》
总结
HashTable 又叫做散列表，是一种用于以常数平均时间执行插入、删除和查找的技术。不能有效的支持元素之间的排序。——《数据结构与算法分析 C语言描述》
HashTable 是 PHP 的灵魂，因为在 Zend 引擎中大量的使用了 HashTable，如变量表，常量表，函数表等，这些都是使用 HashTable 保存的，另外，PHP 的数组也是通过使用 HashTble 实现的。
接下来看下面这一句话：
Hashtable是非常常见的数据结构，它被设计出来解决计算机只能直接表示以连续的整数作为索引的数组的问题。使用Hashtable，程序员才能使用字符串或者其他的复合类型作为数组的键。
Hashtable 的概念：字符串的键先会被传递给一个 hash 函数（hashing function，中文也翻译为散列函数）,然后这个函数会返回一个整数，而这个整数就是“通常”的数组的索引，通过这个数字索引可以访问到 字符串的键对应的数据。
关于 HashTable 的几个概念
- 键(key)：用于操作数据的标示，例如PHP数组中的索引，或者字符串键等等。
- 槽(slot/bucket)：哈希表中用于保存数据的一个单元，也就是数据真正存放的容器。
- 哈希函数(hash function)：将key映射(map)到数据应该存放的slot所在位置的函数。
- 哈希冲突(hash collision)：哈希函数将两个不同的key映射到同一个索引的情况。
对比 PHP 的数组和 C 语言的数组，发现 PHP 的数组确实支持更多的写法，下标不仅可以是数字也可以是字母等。另一方面 HashTable 是无序的，那 PHP 数组的顺序结构是怎么实现的呢？可以带着这些疑问阅读 PHP 源码。
源码版本： php-7.1.19-src
解决哈希冲突一般有两种方式，PHP 使用的是分离链接法，既当产生冲突时，数据形成一个链表。
Hashtable 的数据结构
1 typedef struct _Bucket {
2 zval val; /* 存储的具体数据 */
3 zend_ulong h; /* 一个 hash 值 */
4 zend_string *key; /* 一个字符串键 */
5 } Bucket;
6
7 typedef struct _zend_array HashTable;
8
9 struct _zend_array {
10 zend_refcounted_h gc;
11 union {
12 struct {
13 ZEND_ENDIAN_LOHI_4(
14 zend_uchar flags,
15 zend_uchar nApplyCount,
16 zend_uchar nIteratorsCount,
17 zend_uchar consistency)
18 } v;
19 uint32_t flags;
20 } u;
21 uint32_t nTableMask; /* 掩码,用于根据hash值计算存储位置,永远等于nTableSize-1 */
22 Bucket *arData; /* 存放实际数据 */
23 uint32_t nNumUsed; /* arData数组已经使用的数量 */
24 uint32_t nNumOfElements; /* hash表中元素个数 */
25 uint32_t nTableSize; /* hash表的大小 */
26 uint32_t nInternalPointer; /* 用于HashTable遍历 */
27 zend_long nNextFreeElement; /* 下一个空闲可用位置的数字索引 */
28 dtor_func_t pDestructor; /* 析构函数 */
29 };结构体 _Bucket 代表的是 PHP 里数组的元素， _zend_array 为 PHP 具体功能添加了一些必要的数据。
例如当将一个元素从哈希表删除时并不会将对应的Bucket移除，而是将Bucket存储的zval标示为IS_UNDEF，所以使用 nNumOfElements 保存 Hash 的元素个数，使用 nNumUsed 表示数组真实的使用数量。
nTableSize 表示分配的内存大小，最小为8。
HashTable中另外一个非常重要的值 arData ，这个值指向存储元素数组的第一个Bucket，插入元素时按顺序依次插入数组，比如第一个元素在arData[0]、第二个在arData[1]...arData[nNumUsed]。PHP数组的有序性正是通过arData保证的。
哈希表实现的关键是有一个数组存储哈希值与 Bucket 的映射，但是HashTable中并没有这样一个索引数组。实际上这个索引数组包含在arData中，在内存中一块存在。具体的位置如下图。
所以，整体来看 HashTable 主要依赖 arData 实现元素的存储、索引。插入一个元素时先将元素插入Bucket数组，位置是 index，再根据key的哈希值与nTableMask计算出索引数组的位置，将 index 存入这个位置；查找时先根据 key 的哈希值与 nTableMask 计算出索引数组的位置，获得元素在 Bucket 数组的位置 index，再从 Bucket 数组中取出元素。
哈希表的大小为2^n，插入时如果容量不够则首先检查已删除元素所占比例，如果达到阈值(ht->nNumUsed - ht->nNumOfElements > (ht->nNumOfElements >> 5)，则将已删除元素移除，重建索引，如果未到阈值则进行扩容操作，扩大为当前大小的2倍，将当前Bucket数组复制到新的空间，然后重建索引。