PHP数组的实现

特性

• 不需要代码去指定需要分配的内存，自动分配2的幂次方
• 不会像go、c语言在数组的使用中出现越界的情况
• 同时支持索引数组和关联数组，即key值既可以为整数类型也可以为字符串类型
• 支持泛型value
• 正确使用的情况下查找元素的时间复杂度为O(1)
• 元素有序，插入的顺序和遍历的顺序一致

底层是如何实现的

PHP数组底层最核心的数据结构就是Hashtable和链表。

当我们定义一个key-value的数组时，在php底层，会见将key通过time33算法转换为一个整形数字，然后将这个整形数字再次经过散列计算，计算得到的结果作为Hashtable中的一个下标，最终将Bucket的下标存在Hashtable的value中。

<?php
$foo = ["key1" => "value1", "key2" => "value2"];

Hashtable是无序的， Bucket是有序的，PHP7.1后将Hashtable和Bucket统一在了arData里面

读取元素

随机读取

<?php
echo $foo["key1"];

通过 Key 访问数组时，只需要使用相同的算法计算出对应下标，然后取出对应元素中的 Value 值，即可实现随机读取。

顺序读取

<?php
foreach($foo as $k => $v) {
  echo $k . ":" . $v . PHP_EOL;
}
// result =
// ---------
// key1:value1
// key2:value2
// ---------

PHP数组进行for循环时，数组是有序的，从上图可以看出，我们只要循环遍历Bucket就可以顺序输出。

新增元素

新增元素和前面的元素初始化类似，但是值得注意的是，当新增元素后，发现当前arData已经满了的时候，PHP底层会申请新内存(初始大小位2，以2的倍数不断扩充)，把所有数据以内存的形式copy过去，然后扫描数组，把无用的数据移动到后面。采用移动的原因是因为删除元素的次数毕竟很少。

删除元素

<?php
unset($foo["key1"]);

PHP中删除元素不是直接回收空间，因为直接回收空间会严重的导致内存碎片化，降低内存的使用率。

删除分为以下两步：

• 将key1的bucket内容清空，不回收
• 将pListHead指向key2

Hash冲突

任何散列函数都会出现哈希冲突的问题，常见的解决哈希冲突的方法有以下几种（不全面）：

• 链地址法
• 重哈希法

PHP中采用的是链地址法。发生冲突时，新元素的插入分为以下两步：

• 新元素的next指向老元素
• Hashtable的中将老元素的下标更新为新元素的下标

所以Hashtable指向的就不是单个元素，而是元素组成的Bucket链表。在查找元素时，先找到对应的链表，然后遍历链表，匹配key后，才能找到目标元素。

不难发现在理想情况下，PHP的时间复杂度为O(1)。当key使用time33算法产生冲突时，这时候的时间复杂度就达到了O(n*(1+n)/2)=O(n^2)。