PHP数组底层实现

It is never too late to learn。
PHP数组是一个神奇而强大的数据结构。以前听人说,都说语言的面向对象,PHP变成可以说是面向数组。
PHP 中的数组实际上是一个有序映射。映射是一种把 values 关联到 keys 的类型
于 PHP 数组的强大特性,我们可以轻易实现更加复杂的数据结构,比如栈、队列、列表、集合、字典等。PHP 数组功能之所以如此强大,得益于底层基于散列表Hashtable实现。
key: 键,通过它可以快速检索到对应的value。一般为数字或字符串。
value : 值,目标数据。可以是复杂的数据结构。
bucket: 桶,HashTable中存储数据的单元。用来存储key和value以及辅助信息的容器。
slot: 槽,HashTable有多个槽,一个bucket必须从属于具体的某一个slot,一个slot下可以有多个bucket。
哈希函数: 需要自己实现,在存储的时候,会对key应用哈希函数确定所在slot。
哈希冲突:当多个key经过哈希计算后,得出的slot的位置是同一个,那么就叫作哈希冲突。一般解决冲突的方法是链地址法和开放地址法。
PHP采用链地址法,将同一个slot中的bucket通过链表链接起来。
在具体实现中,PHP基于上述基本概念对bucket以及哈希函数进行了一些补充,增加了hash1函数以生成h值,然后通过hash2函数散列到不同的slot。
PHP5的数组源码

typedef struct bucket {

ulong h; /* 4字节 对char *key进行hash后的值,或者是用户指定的数字索引值 Used for numeric indexing */

uint nKeyLength; /* 4字节 字符串索引长度,如果是数字索引,则值为0 */

void *pData; /* 4字节 实际数据的存储地址,指向value,一般是用户数据的副本,如果是指针数据,则指向pDataPtr,这里又是个指针,zval存放在别的地方*/

void *pDataPtr; /* 4字节 引用数据的存储地址,如果是指针数据,此值会指向真正的value,同时上面pData会指向此值 */

struct bucket *pListNext; /* 4字节 整个哈希表的该元素的下一个元素*/

struct bucket *pListLast; /* 4字节 整个哈希表的该元素的上一个元素*/

struct bucket *pNext; /* 4字节 同一个槽,双向链表的下一个元素的地址 */

struct bucket *pLast; /* 4字节 同一个槽,双向链表的上一个元素的地址*/

char arKey[1]; /* 1字节 保存当前值所对于的key字符串,这个字段只能定义在最后,实现变长结构体*/

} Bucket;

 

 

typedef struct _hashtable {

uint nTableSize; /*4 哈希表中Bucket的槽的数量,初始值为8,每次resize时以2倍速度增长*/

uint nTableMask; /*4 nTableSize-1 ,索引取值的优化 */

uint nNumOfElements; /*4 哈希表中Bucket中当前存在的元素个数,count()函数会直接返回此值*/

ulong nNextFreeElement; /*4 下一个数字索引的位置 */

Bucket *pInternalPointer; /*4 当前遍历的指针(foreach比for快的原因之一) 用于元素遍历*/

Bucket *pListHead; /*4 存储数组头元素指针 */

Bucket *pListTail; /*4 存储数组尾元素指针 */

Bucket **arBuckets; /*4 指针数组,数组中每个元素都是指针,存储hash数组 */

dtor_func_t pDestructor; /*4 在删除元素时执行的回调函数,用于资源的释放 /*

persistent 指出了Bucket内存分配的方式。如果persisient为TRUE,则使用操作系统本身的内存分配函数为Bucket分配内存,否则使用PHP的内存分配函数。*/

zend_bool persistent; /*1 */

unsigned char nApplyCount; /*1 标记当前hash Bucket被递归访问的次数(防止多次递归)*/

zend_bool bApplyProtection;/*1 标记当前hash桶允许不允许多次访问,不允许时,最多只能递归3次 */

#if ZEND_DEBUG

int inconsistent; /*4 */

#endif

} HashTable;

bucket里面有pListLast、pListNext、pLast、pNext这4个指针,维护两种双向链表。一种是全局链表,按插入顺序将所有bucket全部串联起来,整个HashTable只有一个全局链表。
另一个是局部链表,为了解决哈希冲突,每个slot 维护着一个链表,将所有哈希冲突的bucket串联起来。也就是,每一个bucket都处在一个双向链表上。pLast和pNext分别指向局部链表的前一个和后一个bucket,pListLast和pListTNext则指向全局链表的前一个和后一个。
bucket的h是通过key映射的哈希值,让不同的key均匀分配到哈希表的各个位置,PHP选用的time33算法。
nKeyLength(字符的个数)如果使用的是关联索引,那么此处nKeyLength就是字符的个数,比如说$arr[‘key’]=’value’ ,那么这个值就为3,如果是索引数组,此字段就不会用上。
pNext和pLast (记录该bucket的前后bucket)
因为每一个bucket都需要分配一次内存。
key—value中的value都是zval。这种情况下,每个bucket需要维护指向zval的指针pDataPtr以及指向pDataPtr的指针pData。
每一个bucket需要维护4个指向bucket的指针
基于此PHP7重写了数组的相关代码
PHP7数组源码
typedef struct _Bucket {
zval val;
zend_ulong h; /* hash value (or numeric index) */
zend_string *key; /* string key or NULL for numerics */
} Bucket;
typedef struct _zend_array HashTable; /*typedef为C语言的关键字,作用是为一种数据类型定义一个新名字*/
struct _zend_array {
zend_refcounted_h gc;
union {
        struct {
               ZEND_ENDIAN_LOHI_4(
                             zend_uchar flags,
                             zend_uchar _unused,
                             zend_uchar nIteratorsCount,
                             zend_uchar _unused2)
        }v;
       uint32_t flags;
} u;
uint32_t nTableMask; /* 掩码,用于根据hash值计算存储位置,永远等于nTableSize-1 */
Bucket *arData; /*存放实际数据*/
uint32_t nNumUsed; /* arData数组已经使用的数量 */
uint32_t nNumOfElements; /* hash表中元素个数 */
uint32_t nTableSize; /* hash表的大小 HashTable的大小,始终为2的指数(8,16,32,64…)。最小为8,最大值根据机器不同而不同*/
uint32_t nInternalPointer;/* 用于HashTable遍历 */
zend_long nNextFreeElement;/* 下一个空闲可用位置的数字索引 */
dtor_func_t pDestructor; /* 析构函数 */
};
数组的有序性
我们知道 PHP 数组是基于哈希表实现的,而与一般哈希表不同的是 PHP 的数组还实现了元素的有序性,就是插入的元素从内存上来看是连续的而不是乱序的,为了实现这个有序性 PHP 采用了「映射表」技术。下面就通过图例说明我们是如何访问 PHP 数组的元素
映射表和数组元素在同一片连续的内存中,映射表是一个长度与存储元素相同的整型数组,它默认值为 -1 ,有效值为 Bucket 数组的下标。而 HashTable->arData 指向的是这片内存中 Bucket 数组的第一个元素。
举个例子 $a[‘key’] 访问数组 $a 中键名为 key 的成员,流程介绍:首先通过 Time 33 算法计算出 key 的哈希值,然后通过散列算法计算出该哈希值对应的映射表下标,因为映射表中保存的值就是 Bucket 数组中的下标值,所以就能获取到 Bucket 数组中对应的元素。
现在我们来聊一下散列算法,就是通过键名的哈希值映射到「映射表」的下标的算法。其实很简单就一行代码:
nIndex = h | ht->nTableMask; 复制代码
将哈希值和 nTableMask 进行或运算即可得出映射表的下标,其中 nTableMask 数值为 nTableSize 的负数。并且由于 nTableSize 的值为 2 的幂次方,所以 h | ht->nTableMask 的取值范围在 [-nTableSize, -1] 之间,正好在映射表的下标范围内。至于为何不用简单的「取余」运算而是费尽周折的采用「按位或」运算?因为「按位或」运算的速度要比「取余」运算要快很多,我觉得对于这种频繁使用的操作来说,复杂一点的实现带来的时间上的优化是值得的
散列冲突
同键名的哈希值通过散列计算得到的「映射表」下标有可能相同,此时便发生了散列冲突。对于这种情况 PHP 使用了「链地址法」解决。下图是访问发生散列冲突的元素的情况:
我们同样访问 $a[‘key’] 的过程多了一些步骤。首先通过散列运算得出映射表下标为 -2 ,然后访问映射表发现其内容指向 arData 数组下标为 1 的元素。此时我们将该元素的 key 和要访问的键名相比较,发现两者并不相等,则该元素并非我们所想访问的元素,而元素的 val.u2.next 保存的值正是下一个具有相同散列值的元素对应 arData 数组的下标,所以我们可以不断通过 next 的值遍历直到找到键名相同的元素或查找失败
数组的扩容
数组的长度是定长的,那么如果空间已满还需继续插入的时候怎么办呢?PHP 的数组在底层实现了自动扩容机制,当插入一个元素且没有空闲空间时,就会触发自动扩容机制,扩容后再执行插入。
需要提出的一点是,当删除某一个数组元素时,会先使用标志位对该元素进行逻辑删除,而不会立即删除该元素所在的 Bucket,因为后者在每次删除时进行一次排列操作,从而造成不必要的性能开销。
扩容的过程为:
  1. 如果已删除元素所占比例达到阈值,则会移除已被逻辑删除的 Bucket,然后将后面的 Bucket 向前补上空缺的 Bucket,因为 Bucket 的下标发生了变动,所以还需要更改每个元素在中间映射表中储存的实际下标值。
  2. 如果未达到阈值,PHP 则会申请一个大小是原数组两倍的新数组,并将旧数组中的数据复制到新数组中,因为数组长度发生了改变,所以 key-value 的映射关系需要重新计算,这个步骤为重建索引。
注:因为在重建索引时需要重新计算映射关系,所以将旧数组复制到新数组中时,中间映射表的数据是无需复制的
参考链接:

发表评论

电子邮件地址不会被公开。 必填项已用*标注