# PHP数组的内部实现

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

![](/files/-LfnTHa6IP1YlOPjgCvt)

## 什么是HashTable ？

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

![](/files/-LfnTHa8ariypc2jTmWd)

**哈希表**

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

![](/files/-LfnTHaAbv1S5Q4EDGZW)

## 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没有区别。

![](/files/-LfnTHaCTOUc16jFO5IF)

![](/files/-LfnTHaEz62BdHNpNuWA)

## 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找到上一个元素：
* 由于访问指针已经移动到了适当的位置，则直接获取当前指针指向的元素。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://phper.shujuwajue.com/shu-zu/phpshu-zu-de-nei-bu-shi-xian.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.