前言
本文主要简单介绍一下PHP7数组的数据结构哈希表，阅读本文前，您需要掌握基础的C/C++的知识以及对哈希表的定义有简单的了解。
概念
哈希表是根据键(Key)而直接访问在内存存储位置的数据结构，就像数组的索引的一样。我们可以先想象一下这个数据结构：
-
首先需要一个字段来存储具体的数据。
-
其次需要根据key可以直接访问到这个具体的值，可想而知能够直接访问内存的无外乎内存地址了，那我们要做的就是key和内存地址的映射。内存地址的的访问分两种，一种是开始地址+偏移量得到目标数据的地址，还有一种就是直接得到目标数据的地址。后者从理论上是不可行的，前者很方便，但是只在连续的内存空间内可行。
-
开始地址是不变的，我们要做的是key和偏移量之间的映射，这样就可以访问到不同内存地址，他们之间可以用hash算法实现
-
虽然我们会选择更唯一，更均匀的hash算法，但还是会存在冲突，所以我们还需要一个解决冲突的方法
如果满足了上面4条，一个哈希表基本就实现了。
PHP中的HashTable
先贴上php源码中哈希表的数据结构
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;
uint32_t nTableMask; //nTableSize的负值
Bucket *arData; //存取具体值的桶
uint32_t nNumUsed; //已经使用的Bucket数量
uint32_t nNumOfElements; //有具体值的Bucket数量
uint32_t nTableSize; //总的Bucket数量
uint32_t nInternalPointer;
zend_long nNextFreeElement;
dtor_func_t pDestructor;
};
typedef struct _Bucket {
zval val;//存取具体的值
zend_ulong h; /* hash value (or numeric index) */
zend_string *key; /* string key or NULL for numerics */
} Bucket;
其中重要的字段后面我都加了注释。接下来，我们根据上面说的4条，来分析一下这个结构体：
-
存取数据的字段就是Bucket，zval是php的核心，是所有数据类型的抽象表示，类似于go里面的interface，h是key的hash值。
-
在php中，索引数组
["a", "b"]和关联数组["a" => "b"]都是用这个结构来实现的，索引数组可以直接用索引当做是偏移量；关联数组的key是字符串，偏移量的算法可以用h % nTableSize取模，按照这样我们大概可以画出一个内存结构图：
1.jpg
如果h % nTableSize的模为2，则我们就把数据存储到下标为2的bucket上
-
哈希冲突。当多个key的hash值对nTableSize的模相等时，就出现了冲突，两个数据就落在了同一个bucket里面。解决的方法也很多，链表法最常用，也最简单，就是把冲突的元素用一个单向链表串联起来，看图：
2.jpg
当我们根据key去查找元素的时候，从定位的bucket开始，沿着单向链表一直匹配，如果key和某个bucket的key相等，我们认为这就是我们想要的数据。至于链表的长度，就要看哈希函数的唯一性了。
我们知道，php中不管是索引数组还是关联数组都是插入有序的，也就是说先插入的肯定先遍历出来，索引数组当然没有问题，但是关联数组很可能不是我们想要的结果，从上面的内存图中，如果我们从开始地址遍历这个数组，我们得到的结果很可能是无序的，因为第一个元素key对应bucket很可能不在索引为0的bucket，解决的方法就是按插入的顺序用一个可以顺序访问结构存起来，比如redis的有序集合用的就是跳跃表(skiptable)。php做法也是类似，但是稍有不同，它用后面的bucket内存来充当顺序结构，再用一块内存也就是前面的idx来做地址映射，idx的最小索引为nTableMask, 如下：
3.jpg
遍历的时候只要按顺序遍历bucket就行了。随机访问，比如关联数组的key经过hash运算之后的值-3，则先找到索引为-3的idx,再通过idx找到对应的bucket。
首先要给大家普及两个c语言的知识：
- 任何数据在内存里面都是没有数据类型之分的，都是按字节存储
- 如果你的p指针指向数组中的任意一个元素，则p[1]是访问当前元素的下一个元素，p[-1]就是前一个元素
有人可能会问了，那bucket充当顺序结构，那冲突链去哪了呢？在idx上？其实，PHP并没有用一个活生生的链表去解决冲突。先来看下PHP的核心zval这个结构体：
struct _zval_struct {
zend_value value; /* value */
union {
struct {
ZEND_ENDIAN_LOHI_4(
zend_uchar type, /* active type */
zend_uchar type_flags,
zend_uchar const_flags,
zend_uchar reserved) /* call info for EX(This) */
} v;
uint32_t type_info;
} u1;
union {
uint32_t next; /* hash collision chain */
uint32_t cache_slot; /* literal cache slot */
uint32_t lineno; /* line number (for ast nodes) */
uint32_t num_args; /* arguments number for EX(This) */
uint32_t fe_pos; /* foreach position */
uint32_t fe_iter_idx; /* foreach iterator index */
uint32_t access_flags; /* class constant access flags */
uint32_t property_guard; /* single property guard */
uint32_t extra; /* not further specified */
} u2;
};
u2联合体里面的next字段就是用来解决hash冲突的，这个字段存储的并不是下一个冲突元素地址，而是下一个冲突元素距离bucket开始地址的字节偏移量，然后把首个元素的字节偏移量存储到对应的idx里面。如下图：
4.jpg
也就是说我们每次新增元素的时候都是先把next指向原来idx存放的字节偏移量，然后用新元素的字节偏移量去覆盖idx.
需要注意的是：
- idx和bucket是一整块连续内存，并不是单独的内存块，不同的是idx用的是unsign int类型来访问，后面的则用bucket类型来访问。
- idx的索引是负数，那如何对负数取模呢？对负数取模运算结果是正的，不符合我们的要求，但是要保证idx在[nTableMask, -1]区间内，php用的不是取模运算，而是h | nTabeMask, 至于为什么这里就不详细说了，你们多举几个例子就明白了。
到这为止php中哈希表的模型已经解释完了，下一篇我们跟着源码去更详细的看下哈希表的新增，删除，查找，扩容以及一些标志位的作用来进一步了解哈希表，然后分析一下在什么情况下会出现一些性能问题。
备注：如果有错误或者有更好的实现方式，请读者们不吝指出，感激不尽。
本文版权归作者所有，转载请注明出处。
网友评论