# PHP数组的内部实现

* 实现数组使用了两个数据结构，一个是HashTable,另一个是bucket。
* HashTable结构体用于保存整个数组需要的基本信息。
* Bucket结构体用于保存具体的数据内容。

![](https://1303647163-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LfnT30woYyQ9bJF96Hh%2F-LfnTB5KYnkOx0V3e4EY%2F-LfnTHa6IP1YlOPjgCvt%2F%E6%95%B0%E7%BB%84%E5%AE%9E%E7%8E%B0.png?generation=1558862966001954\&alt=media)

## 什么是HashTable ？

哈希表，是根据关键字（Key value）而直接访问在内存存储位置的**数据结构**。也就是说，它**通过把键值通过一个函数的计算，映射到表中一个位置来访问记录，**这加快了查找速度。这个映射函数称做**哈希函数**，存放记录的数组称做哈希表。

![](https://1303647163-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LfnT30woYyQ9bJF96Hh%2F-LfnTB5KYnkOx0V3e4EY%2F-LfnTHa8ariypc2jTmWd%2F%E5%93%88%E5%B8%8C%E8%A1%A8.png?generation=1558862975628024\&alt=media)

**哈希表**

* hash table，又叫哈希表，散列表，Hash表。
* 这种数据结构通过key->value的映射关系，使得普通的查找和插入、删除操作都可以在O(1) 的时间内完成。
* key->value的映射是通过Hash函数来实现的。

![](https://1303647163-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LfnT30woYyQ9bJF96Hh%2F-LfnTB5KYnkOx0V3e4EY%2F-LfnTHaAbv1S5Q4EDGZW%2Fhash%E8%A1%A8.png?generation=1558862973666903\&alt=media)

## PHP数组Hashtable结构体

```
typedef struct _hashtable {
    uint nTableSize;        // hash Bucket的大小，最小为8，以2x增长。
    uint nTableMask;        // nTableSize-1 ， 索引取值的优化，193491849 & 127
    uint nNumOfElements;    // hash Bucket中当前存在的元素个数，count()函数会直接返回此值。
    ulong nNextFreeElement; // 下一个数字索引的位置
    Bucket *pInternalPointer;   // 当前遍历的指针foreach比for快的原因之一,reset, current遍历函数使用
    Bucket *pListHead;          // 存储数组头元素指针
    Bucket *pListTail;          // 存储数组尾元素指针
    Bucket **arBuckets;         // 存储hash数组,实际的存储容器
    unsigned char nApplyCount; // 标记当前hash Bucket被递归访问的次数（防止多次递归）
} HashTable;
```

nTableSize : 表长度，并非元素个数

nTableMask:表的掩码，始终等于nTableSize-1

nNumOfElements:存储的元素个数

nNextFreeElement:指向下一个空的元素位置

pInternalPointer:foreach循环时，用来记录当前遍历到的元素位置

## Bucket结构体

```
typedef struct bucket {
    ulong h;            // 对char *key进行hash后的值，或者是用户指定的数字索引值
    uint nKeyLength;    // hash关键字的长度，如果数组索引为数字，此值为0
    void *pData;        // 指向value，一般是用户数据的副本，如果是指针数据，则指向pDataPtr
    void *pDataPtr;     //如果是指针数据，此值会指向真正的value，同时上面pData会指向此值
    struct bucket *pListNext;   // 整个hash表的下一元素
    struct bucket *pListLast;   // 整个hash表该元素的上一个元素
    struct bucket *pNext;       // 存放在同一个hash Bucket内的下一个元素
    struct bucket *pLast;       // 同一个hash bucket的上一个元素
    const char *arKey;          // 保存当前key所对应的字符串值
} Bucket;
```

## hash key

```
typedef struct _zend_hash_key {
    const char *arKey;
    uint nKeyLength;
    ulong h;
} zend_hash_key;
```

**数字索引**

直接使用h作为hash值。

arKey=NULL 且nKeyLength=0

**字符串索引（关联数组）**

h则是该字符串通过hash函数计算后的hash值。

arKey保存字符串key,

nKeyLength保存该key的长度，

> 在PHP数组中如果索引字符串可以被转换成数字也会被转换成数字索引。
>
> 所以在PHP中例如'10'，'11'这类的字符索引和数字索引10， 11没有区别。

![](https://1303647163-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LfnT30woYyQ9bJF96Hh%2F-LfnTB5KYnkOx0V3e4EY%2F-LfnTHaCTOUc16jFO5IF%2Fphp%E6%95%B0%E7%BB%84%E5%86%85%E9%83%A8%E5%8E%9F%E7%90%861.png?generation=1558862966065974\&alt=media)

![](https://1303647163-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LfnT30woYyQ9bJF96Hh%2F-LfnTB5KYnkOx0V3e4EY%2F-LfnTHaEz62BdHNpNuWA%2Fphp%E6%95%B0%E7%BB%84%E5%86%85%E9%83%A8%E5%8E%9F%E7%90%862.png?generation=1558862966374240\&alt=media)

## HashTable扩容

HashTable的大小并不是固定不变的，当nNumOfElements > nTableSize时，会对HashTable进行扩容，以便于容纳更多的元素。

扩容之后需要对原来hashTable的元素rehash。

```php
<?php 
$a = array();
$p = (1 << 14) - 1; //每一次移动都表示"乘以 2"
$b = 1;
for ($i = 0; $i < $p; $i++) {
    $a[] = $b;
}
echo memory_get_usage(true) . "\n";
$a['as1'] = 1;
echo memory_get_usage(true) . "\n";
$a['as2'] = 1;
echo memory_get_usage(true) . "\n";
```

## prev() 的指针实现

* HashTable结构体中，有一个成员pInternalPointer, 这个成员便是控制数组的访问指针的。
* 先找到数组的当前位置或指针
* 然后访问这个指针的pListLast找到上一个元素：
* 由于访问指针已经移动到了适当的位置，则直接获取当前指针指向的元素。