PHP数组的有序性
在 PHP7中,我们往数组中插入元素的顺序,就决定了我们数组遍历元素的顺序。可以说,PHP7中的数组是有序的。这个有序就是指元素插入数组时的顺序,与遍历时顺序的一致性。
为了实现插入与遍历的顺序一致性,在PHP7中,增加了一个中间映射层,它的大小与哈希表相同,存储了元素在bucket中最终存储的位置,我们把它叫做映射表。
在PHP7中,为了方便映射表的访问,没有将映射表的空间额外单独地分配,而是直接分配在与hashtable中紧挨着的前一块相邻的内存空间中,这样通过一个指针,就可以同时访问映射表和每一个bucket啦
HashTable中另外一个非常重要的值arData,arData数组保存了所有的buckets(也就是数组的元素),这个数组被分配的内存大小为2的幂次方,它被保存在nTableSize这个字段(最小值为8)。这个值指向存储元素数组的第一个Bucket,插入元素时按顺序依次插入数组,比如第一个元素在arData[0]、第二个在arData[1]…arData[nNumUsed],这跟元素对应的键没有任何关系,这只跟插入的顺序相关。PHP数组的有序性正是通过arData保证的。
哈希表实现的关键是有一个数组存储哈希值与Bucket的映射,但是HashTable中并没有这样一个索引数组。
实际上这个索引数组包含在arData中,索引数组与Bucket列表一起分配,arData指向了Bucket列表的起始位置,而索引数组可以通过arData指针向前移动访问到,即arData[-1]、arData[-2]、arData[-3]……索引数组的结构是uint32_t,它存储的是Bucket元素在arData中的位置。
所以,整体来看HashTable主要依赖arData实现元素的存储、索引。插入一个元素时先将元素插入Bucket数组,位置是idx,再根据key的哈希值与nTableMask计算出索引数组的位置,将idx存入这个位置;查找时先根据key的哈希值与nTableMask计算出索引数组的位置,获得元素在Bucket数组的位置idx,再从Bucket数组中取出元素。