PHP7数组的底层实现示例

日期：2020-05-21 栏目：程序人生浏览：次

PHP 数组具有的特性

PHP 的数组是一种非常强大灵活的数据类型，在讲它的底层实现之前，先看一下 PHP 的数组都具有哪些特性。

可以使用数字或字符串作为数组健值

$arr = [1 => 'ok', 'one' => 'hello'];

可按顺序读取数组

foreach($arr as $key => $value){
 echo $arr[$key];
}

可随机读取数组中的元素

$arr = [1 => 'ok', 'one' => 'hello', 'a' => 'world'];

echo $arr['one'];

echo current($arr);

数组的长度是可变的

$arr = [1, 2, 3];

$arr[] = 4;

array_push($arr, 5);

正是基于这些特性，我们可以使用 PHP 中的数组轻易的实现集合、栈、列表、字典等多种数据结构。那么这些特性在底层是如何实现的呢？这就得从数据结构说起了。

数据结构

PHP 中的数组实际上是一个有序映射。映射是一种把 values 关联到 keys 的类型。

PHP 数组的底层实现是散列表（也叫 hashTable )，散列表是根据键（Key）直接访问内存存储位置的数据结构，它的key - value 之间存在一个映射函数，可以根据 key 通过映射函数得到的散列值直接索引到对应的 value 值，无需通过关键字比较，在理想情况下，不考虑散列冲突，散列表的查找效率是非常高的，时间复杂度是 O(1)。

从源码中我们可以看到 zend_array 的结构如下：

typedef struct _zend_array zend_array;
typedef struct _zend_array hashTable;

struct _zend_array {
  zend_refcounted_h gc;
  union {
    struct {
      ZEND_ENDIAN_LOHI_4(
          zend_uchar  flags,
          zend_uchar  nApplyCount,
          zend_uchar  nIteratorsCount,
          zend_uchar  reserve)
    } v;
    uint32_t flags;
  } u;
  uint32_t     nTableMask; // 哈希值计算掩码，等于nTableSize的负值(nTableMask = -nTableSize)
  Bucket      *arData;   // 存储元素数组，指向第一个Bucket
  uint32_t     nNumUsed;  // 已用Bucket数（含失效的 Bucket）
  uint32_t     nNumOfElements; // 哈希表有效元素数
  uint32_t     nTableSize;   // 哈希表总大小，为2的n次方（包括无效的元素）
  uint32_t     nInternalPointer; // 内部指针，用于遍历
  zend_long     nNextFreeElement; // 下一个可用的数值索引,如:arr[] = 1;arr["a"] = 2;arr[] = 3; 则nNextFreeElement = 2;
  dtor_func_t    pDestructor;
};

该结构中的 Bucket 即储存元素的数组，arData 指向数组的起始位置，使用映射函数对 key 值进行映射后可以得到偏移值，通过内存起始位置 + 偏移值即可在散列表中进行寻址操作。

转载注明出处：http://www.heiqu.com/5292.html

PHP7数组的底层实现示例

相关推荐