PHP底層代碼如何實現PHP 7數組的

這篇文章將為大家詳細講解有關PHP底層代碼如何實現PHP 7數組的，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

PHP 7 數組概述
PHP 中的數組實際上是一個有序映射。映射是一種把 values 關聯到 keys 的類型。此類型在很多方面做了優化，因此可以把它當成真正的數組，或列表（向量），散列表（是映射的一種實現），字典，集合，棧，隊列以及更多可能性。由于數組元素的值也可以是另一個數組，樹形結構和多維數組也是允許的。 —— PHP 官方文檔中文版
這里主要關注兩個點：

key 可以是整數，也可以是字符串。Float、Bool、Null 類型的 key 會被轉換為整數或者字符串存儲，其他類型的會報錯。
value 可以是任意類型。
遍歷數組時，數組元素按照其 key 添加的順序依次取出。
PHP 7 的數組分為 packed array 和 hash array 兩種類型，在滿足一定條件時可以互轉。

hash array 的 key 可以是整數也可以是字符串，在 hash 沖突時使用鏈表（沖突鏈）來解決沖突問題。
packed array 的所有 key 是自然數，且依次添加的元素的 key 逐漸增大（不要求連續）。它的耗時和內存占用都比 hash 數組低。
以下僅介紹 hash array 相關的內容。

主要數據類型
下圖是數組主要的數據類型：

Hash 區               arData                 Data 區

                                            +
                                            | 指 針 指 向 Data 區 的 開 始
                                            v

+----------+----------+----------+----------+----------+----------+----------+----------+
|          |          |          |          |          |          |          |          |
|nTableMask|nTableMask|  ......  |    -1    |    0     |    1     |  ......  |nTableSize|
|          |    +1    |          |          |          |          |          |    +1    |
+---------------------------------------------------------------------------------------+
|          |          |          |          |          |          |          |          |
| uint32_t | uint32_t |  ......  | uint32_t |  Bucket  |  Bucket  |  ......  |  Bucket  |
|          |          |          |          |          |          |          |          |
+----------+----------+----------+----------+----------+----------+----------+----------+

從整體看，這是一個數組。但入口是 arData 而不是處于最左側的一個元素。arData 把數組分為兩部分：

左邊是 Hash 區，其值為 uint32_t 類型，是沖突鏈的第一個元素在 Data 區的下標；
右邊是 Data 區，其值為 Bucket 類型，用于存儲數據及其相關信息。
由于 arData 主要指向 Data 區，因此其默認類型被配置為 Bucket 指針。

在申請內存時，會把 Hash 區所需的內存大小加上 Data 區所需的內存大小，然后一起申請。

Bucket 長什么樣？

zend_types.h：

/* 數組的基本元素 */
typedef struct _Bucket {
    zval              val;              /* 值 */
    zend_ulong        h;                /* hash 值（或者整數索引） */
    zend_string      *key;              /* 字符串 key（如果存儲時用整數索引，則該值為 NULL） */
} Bucket;

Bucket 把 key 和 value 放在一起了。

在沖突鏈中，Bucket 是一個節點。那么此時心里會有一個疑問：怎么獲取沖突鏈的下一個節點？

沖突鏈
說到鏈表，會很自然地想到鏈表元素的結構體里包含著指向下一個元素的指針 next 。例如單向鏈表：

typedef struct listNode {
    struct listNode *next;
    void *value;
} listNode;

但 Bucket 卻不包含這個指針。

會不會在 Bucket 上一層，也就是數組的結構體定義中有一個專門存放沖突鏈的地方？

zend_types.h：

typedef struct _zend_array HashTable;
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 值轉化為 [nTableMask, -1] 區間內的負數。根據 nTableSize 生成。
    Bucket     *arData;           // 指向 Data 區的指針。
    uint32_t    nNumUsed;         // Data 區最后一個有效 Bucket 的下標 + 1。
    uint32_t    nNumOfElements;   // 存在多少個有效 Bucket。刪除數組元素時，會使其減一。
    uint32_t    nTableSize;       // 總共有多少空間。
    uint32_t    nInternalPointer;
    zend_long   nNextFreeElement;
    dtor_func_t pDestructor;
};
想錯了，換個角度想想.jpg

那往 Bucket 下一層看看：
zend_types.h：

typedef struct _zval_struct     zval;
struct _zval_struct {
    zend_value        value;    // 通用值結構。存儲基礎類型（double）或指針（數組、對象等等）
    union {
        struct {
            // 省略其他定義
        } v;
        uint32_t type_info;        // 值的類型，例如 IS_ARRAY 、IS_UNDEF
    } u1;
    union {
        uint32_t     next;         // 指向 hash 沖突鏈的下一個元素    <--- 就是這里
        // 省略其他定義
    } u2;                       // u2 表示第二個 union
};

驚！鏈表元素的 next 居然藏在 PHP 的通用數據類型 zval 里面。

想不到吧？.jpg

補充一點：
PHP HashMap 的沖突鏈始終是一個鏈表，不會像 JAVA 的 HashMap 那樣在達成一定條件時轉成紅黑樹。這會帶來一定的問題。后面再詳細說明。

怎么看 HashTable ？
再看一遍結構體。

zend_types.h：

typedef struct _zend_array HashTable;
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;       // 根據 nTableSize 生成的負數。用于把 hash 值轉化為 [nTableMask, -1] 區間內的負整數，防止越界。
    Bucket     *arData;           // 指向 Data 區的指針。
    uint32_t    nNumUsed;         // Data 區最后一個有效 Bucket 的下標 + 1。
    uint32_t    nNumOfElements;   // 存在多少個有效 Bucket。刪除數組元素時，會使其減一。
    uint32_t    nTableSize;       // 總共有多少空間。
    uint32_t    nInternalPointer; // 內部指針。受到 reset() 、 end() 、 next() 等的影響。
    zend_long   nNextFreeElement;
    dtor_func_t pDestructor;
};

有效 Bucket 指的是 Bucket val 的類型不為 IS_UNDEF 。也就是不為未定義的（undefined）值。無效 Bucket 反之。

nNumUsed 、nNumOfElements 、 nTableSize 的區別：

nNumUsed        = 4
nNumOfElements  = 3
nTableSize      = 8

+----------+----------+-----------+----------+-----------+-----------+-----------+
|          |          |           |          |           |           |           |
|    0     |    1     |     2     |    3     |     4     |  ......   |     7     |
|          |          |           |          |           |           |           |
+--------------------------------------------------------------------------------+
|          |          |           |          |           |           |           |
|  Bucket  |  Bucket  | Undefined |  Bucket  | Undefined | Undefined | Undefined |
|          |          |   Bucket  |          |   Bucket  |  Buckets  |   Bucket  |
+----------+----------+-----------+----------+-----------+-----------+-----------+

數組的主要操作
PHP 數組主要用到的基本操作有：查找、添加、更新、刪除

PHP 內部操作有：rehash 、擴容

其中查找是較為簡單的，添加、更新、刪除都包含了查找的動作，因此先看查找。

查找
由于 key 有整數和字符串這兩種類型，因此查找的實現也分為兩種。這里以整數 key 為例。

讀源碼時要注意 HT_HASH_* 和 HT_DATA_* 開頭的函數，分別代表著在 Hash 區和 Data 區的操作。
zend_hash.c

static zend_always_inline Bucket *zend_hash_index_find_bucket(const HashTable *ht, zend_ulong h)
{
    uint32_t nIndex;
    uint32_t idx;
    Bucket *p, *arData;

    arData = ht->arData;
    nIndex = h | ht->nTableMask;                // 避免 Hash 區越界
    idx = HT_HASH_EX(arData, nIndex);           // 在 Hash 區取 nIndex 位置的值，結果是 Data 區某個 Bucket 的下標
    while (idx != HT_INVALID_IDX) {
        ZEND_ASSERT(idx < HT_IDX_TO_HASH(ht->nTableSize));  // 確保 Data 區沒有越界
        p = HT_HASH_TO_BUCKET_EX(arData, idx);  // 用 Data 區下標獲取 Bucket，即沖突鏈的第一個 Bucket
        if (p->h == h && !p->key) {             // 整數 key 存到 h，因此比對 h。p->key 為 NULL 表示 Bucket 的 key 為整數 key
            return p;
        }
        idx = Z_NEXT(p->val);                   // 沒有找到的話，從當前的 Bucket 獲取沖突鏈的下一個 Bucket
    }
    return NULL;                                // 鏈表遍歷完也沒找到，那就是不存在
}

舉個例子：

nTableSize = 8

 nTableMask = -(nTableSize + nTableSize)

            = (-16)            = (11111111111111111111111111110000)
                   10                                              2

 h          = (100000000)      = (00000101111101011110000100000000)
                         10                                        2

 nIndex     = (h | nTableMask) = (11111111111111111111111111110000)  = (-16)
                                                                   2     +  10
                                                                         |
     +-------------------------------------------------------------------+
     |
     |                  Hash          arData          Data
     |
     |                                   +
     |                                   |              +----------------------------+
     v                                   v              v                            |
                                                                                     |
+---------+---------+----------+---------+---------+---------+----------+---------+  |
|         |         |          |         |         |         |          |         |  |
|   -16   |   -15   |  ......  |   -1    |    0    |    1    |  ......  |    7    |  |
|         |         |          |         |         |         |          |         |  |
+---------------------------------------------------------------------------------+  |
|         |         |          |         |         |         |          |         |  |
|    1    |    6    |  ......  |    5    | Bucket0 | Bucket1 |  ......  | Bucket7 |  |
|         |         |          |         |         |         |          |         |  |
+---------+---------+----------+---------+---------+---------+----------+---------+  |
                                                                                     |
     +                                                 +                     ^       |
     |                                                 |        next         |       |
     |                                                 +---------------------+       |
     |                                                                               |
     +-------------------------------------------------------------------------------+

至于為什么 nTableMask = -(nTableSize + nTableSize) ，見下文的【負載因子】。

nTableMask 使得無論多大的 uint32_t ，在按位或以及轉成有符號整數后，都會變成負整數，并且其值會在 [nTableMask, -1] 這個區間。

介紹完整數 key 的查找，順便對比一下字符串 key 的查找，不同之處如下：

字符串 key 會存到 p->key 里面，而這個字符串的 hash 存到 p->h 里面。
在比較 key 的時候，整數 key 是比較兩個整數是否相等，而字符串 key 會先比較 hash 是否相等，然后比較兩個字符串是否相等。
添加
依然取整數 key 為例。這里不關注更新元素的部分和 packed array 的部分。

zend_hash.c:

static zend_always_inline zval *_zend_hash_index_add_or_update_i(HashTable *ht, zend_ulong h, zval *pData, uint32_t flag)
{
    // ... 省略代碼
    idx = ht->nNumUsed++;                       // 使用空間 + 1
    nIndex = h | ht->nTableMask;                // 取 hash 值對應的 Hash 區的下標
    p = ht->arData + idx;                       // 獲取指向新元素的指針
    Z_NEXT(p->val) = HT_HASH(ht, nIndex);       // 新 Bucket 指向 Hash 區下標所指的沖突鏈第一個 Bucket
    HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx);  // Hash 區下標指向新 Bucket
    if ((zend_long)h >= (zend_long)ht->nNextFreeElement) {
        ht->nNextFreeElement = h < ZEND_LONG_MAX ? h + 1 : ZEND_LONG_MAX;
    }
add:
    ht->nNumOfElements++;                       // 元素個數 + 1
    p->h = h;                                   // 整數 key 的下標就是 hash
    p->key = NULL;                              // 整數 key 時，必須把 p->key 設置為 NULL
    ZVAL_COPY_VALUE(&p->val, pData);            // 把要添加的值復制到新 Bucket 里面

    return &p->val;
}

小二，上圖！

nNumUsed       = 1

 nNumOfElements = 1

 nTableSize     = 8

 nTableMask     = (-16)            = (11111111111111111111111111110000)
                       10                                              2

 h              = (100000000)      = (00000101111101011110000100000000)
                             10                                        2

 nIndex         = (h + nTableMask) = (11111111111111111111111111110000)  = (-16)
                                                                       2        10
                                                                             +
                                                                             |
     +-----------------------------------------------------------------------+
     |
     |                 Hash          arData          Data
     |
     |                                  +
     |                                  |    +-------------------------------------+
     v                                  v    v                                     |
                                                                                   |
+---------+---------+---------+---------+---------+---------+---------+---------+  |
|         |         |         |         |         |         |         |         |  |
|   -16   |   -15   | ......  |   -1    |    0    |    1    |  ...... |    7    |  |
|         |         |         |         |         |         |         |         |  |
+-------------------------------------------------------------------------------+  |
|         |         |         |         |         |Undefined|Undefined|Undefined|  |
|    0    |   -1    | ......  |   -1    | Bucket0 | Bucket1 | Buckets | Bucket7 |  |
|         |         |         |         |         |         |         |         |  |
+---------+---------+---------+---------+---------+---------+---------+---------+  |
                                                                                   |
     +                                                                             |
     +-----------------------------------------------------------------------------+

                                                        ^
                                                        +

                                                   可 用 的 Bucket

 nNumUsed       = 2

 nNumOfElements = 2

                       Hash          arData          Data

                                        +
                                        |              +---------------------------+
                                        v              v                           |
                                                                                   |
+---------+---------+---------+---------+---------+---------+---------+---------+  |
|         |         |         |         |         |         |         |         |  |
|   -16   |   -15   | ......  |   -1    |    0    |    1    | ......  |    7    |  |
|         |         |         |         |         |         |         |         |  |
+-------------------------------------------------------------------------------+  |
|         |         |         |         |         |         |Undefined|undefined|  |
|    1    |   -1    | ......  |   -1    | Bucket0 | Bucket1 | Buckets | Bucket7 |  |
|         |         |         |         |         |         |         |         |  |
+---------+---------+---------+---------+---------+---------+---------+---------+  |
                                                                                   |
     +                                       ^   next   +                          |
     |                                       +----------+                          |
     |                                                                             |
     +-----------------------------------------------------------------------------+

文字表述為：

獲取數組 arData 最后一個元素之后的合法位置（這個位置的內存在之前已經申請好了）。把這里的 Bucket 稱為 BucketA。
把 BucketA 的下標放入 BucketA 的 h 中，把要添加的元素值放入 BucketA 的 val 。
把 Hash 區 (h | nTableMask) 位置指向的 Data 下標存儲的 Bucket 稱為 BucketB。
把 BucketA 的 val 的 next 指向 BucketB 。
更新Hash 區 (h | nTableMask) 位置的值為 BucketA 的下標。
Hash 區 -1 表示 HT_INVALID_IDX

在上面的添加部分，可以看到函數的定義是：

static zend_always_inline zval *_zend_hash_index_add_or_update_i(HashTable *ht, zend_ulong h, zva

它把添加和更新放在一起處理了。

實際上在添加的時候，會先使用：

zend_hash_index_find_bucket(const HashTable *ht, zend_ulong h)

來看 h 這個 key 是否存在。如果存在就執行更新，如果不在就執行添加。

更新的操作就是把 pData 復制到找到的 Bucket 里面，替換掉原先的值。

刪除
刪除分為三種情況：

目標 key 不存在
目標 key 存在，其指向的 Bucket 處于沖突鏈的第一個位置
目標 key 存在，其指向的 Bucket 不處于沖突鏈的第一個位置
目標 key 不存在，直接返回就可以了。

目標 key 存在時，包括兩個主要的操作：

處理沖突鏈指針
釋放內存
處理沖突鏈的指針時，分為兩種情況：

在第一個位置：直接讓 Hash 區的值指向沖突鏈第二個位置的 Bucket 在 Data 區的下標；
不在第一個位置：同鏈表刪除中間元素的操作。
釋放內存時：

如果 key 是字符串，則嘗試釋放 key 的空間；
把 Bucket 的 val 復制到另一個變量 data，把 Bucket 的 val 的類型設置為 undefined；
嘗試釋放 data 所占的空間。
做刪除動作的入口是：

zend_hash_del_bucket(HashTable *ht, Bucket *p)

做核心操作的是：

_zend_hash_del_el_ex(HashTable *ht, uint32_t idx, Bucket *p, Bucket *prev)

看一看源碼：

zend_hash.c:

static zend_always_inline void _zend_hash_del_el_ex(HashTable *ht, uint32_t idx, Bucket *p, Bucket *prev)
{
    if (!(HT_FLAGS(ht) & HASH_FLAG_PACKED)) {
        if (prev) {                                                 // 處于沖突鏈的中間
            Z_NEXT(prev->val) = Z_NEXT(p->val);
        } else {                                                    // 處于沖突鏈的第一個
            HT_HASH(ht, p->h | ht->nTableMask) = Z_NEXT(p->val);    // 讓 Hash 區的值指向下一個 Bucket 的 Data 區下標
        }
    }

    idx = HT_HASH_TO_IDX(idx);
    ht->nNumOfElements--;    // 數組元素計數器減一。此時 nNumUsed 保持不變。

    // 如果數組內部指針指向要刪除的這個 Bucket ，則讓其指向數組下一個有效 Bucket 。
    if (ht->nInternalPointer == idx || UNEXPECTED(HT_HAS_ITERATORS(ht))) {
        uint32_t new_idx;

        new_idx = idx;
        while (1) {
            new_idx++;
            if (new_idx >= ht->nNumUsed) {
                break;
            } else if (Z_TYPE(ht->arData[new_idx].val) != IS_UNDEF) {
                break;
            }
        }
        if (ht->nInternalPointer == idx) {
            ht->nInternalPointer = new_idx;
        }
        zend_hash_iterators_update(ht, idx, new_idx);
    }

    // 如果要刪除的元素是數組的最后一個元素，則嘗試從后往前多回收幾個無效 Bucket
    if (ht->nNumUsed - 1 == idx) {
        do {
            ht->nNumUsed--;
        } while (ht->nNumUsed > 0 && (UNEXPECTED(Z_TYPE(ht->arData[ht->nNumUsed-1].val) == IS_UNDEF)));
        ht->nInternalPointer = MIN(ht->nInternalPointer, ht->nNumUsed);
    }

    // key 為字符串時，釋放字符串內存
    if (p->key) {
        zend_string_release(p->key);
    }

    if (ht->pDestructor) {      // 如果配置了析構函數，則調用析構函數
        zval tmp;
        ZVAL_COPY_VALUE(&tmp, &p->val);
        ZVAL_UNDEF(&p->val);
        ht->pDestructor(&tmp);
    } else {
        ZVAL_UNDEF(&p->val);    // 沒有析構函數，則直接將 zval 的 u1.type_info 配置為 undefind。不用釋放空間，因為以后元素可以重用這個空間
    }
}

PHP 數組可擁有的最大容量

zend_types.h


#if SIZEOF_SIZE_T == 4
# define HT_MAX_SIZE 0x04000000 /* small enough to avoid overflow checks */
/* 省略代碼 */
#elif SIZEOF_SIZE_T == 8
# define HT_MAX_SIZE 0x80000000
/* 省略代碼 */
#else
# error "Unknown SIZEOF_SIZE_T"
#endif

根據 sizeof(size_t) 的執行結果判斷應該設置為 67108864 還是 2147483648 。

0x04000000 轉為二進制是： 00000100000000000000000000000000 0x80000000 轉為二進制是：
10000000000000000000000000000000

當 nNumUsed 大于等于 nTableSize 時，會觸發 Resize 操作，以此獲取更多可使用的 Bucket 。

Resize 策略
Resize 的定義是：

zend_hash.c：

static void ZEND_FASTCALL zend_hash_do_resize(HashTable *ht)

Resize 有兩種策略：

rehash
雙倍擴容 + rehash
之所以有不用雙倍擴容的選擇，是因為 PHP 在刪除元素時，只是將對應 Data 區的 Bucket 的值設置為 undefined，并沒有移動后面的元素。

選擇的條件主要涉及 HashTable 的三個成員：

struct _zend_array {
    // ...省略
    uint32_t    nNumUsed;         // Data 區最后一個有效 Bucket 的下標 + 1。
    uint32_t    nNumOfElements;   // 存在多少個有效 Bucket。刪除數組元素時，會使其減一。
    uint32_t    nTableSize;       // 總共有多少空間。
    // ...省略
}

什么情況下只需要 rehash ？

源碼是：ht->nNumUsed > ht->nNumOfElements + (ht->nNumOfElements >> 5)

這里做一個轉換，方便理解：

ht->nNumUsed - ht->nNumOfElements > (ht->nNumOfElements >> 5)

也就是被設置為 undefined 的 Bucket 數量大于當前元素個數除以 32 向下取整的值。

例如：

當 nNumUsed 為 2048 ， nNumOfElements 為 2000 的時候，得到 2048 - 2000 < 62 ，因此執行擴容。
當 nNumUsed 為 2048 ， nNumOfElements 為 1900 的時候，得到 2048 - 1900 > 59 ，因此執行 rehash。
rehash 做以下操作：

清空 Hash 區；
取兩個指針，一個指向當前掃描的位置（叫做 p），一個指向遷移后的位置（叫做 q），遍歷直到 p 到達 nNumUsed ；
p 在碰到無效 Bucket 時，會繼續往前走一步，不做其他事。
p 在碰到有效 Bucket 時，會把 Bucket 的值復制到 q 指向的 Bucket 的值，并且 p 和 q 一起往前走一步。
這種做法的效率會比每次移動有效 Bucket 都把后面的數據一起往前移動來得高。
重新創建沖突鏈；
更新內部指針，使其指向更新位置后的 Bucket；
更新 nNumUsed，使其等于 nNumOfElements 。

什么情況下雙倍擴容 + rehash ？
滿足只 rehash 的條件就只做 rehash，如果不滿足條件并且 nTableSize 小于數組可擁有的最大容量（HT_MAX_SIZE），則雙倍擴容。

由于 HT_MAX_SIZE 是 0x04000000 或者 0x80000000，并且 nTableSize 始終是 2 的次方，所以最后一次雙倍擴容后的容量剛好是 HT_MAX_SIZE 。

0x04000000 轉為二進制是： 00000100000000000000000000000000 0x80000000 轉為二進制是：
10000000000000000000000000000000

雙倍擴容時，做以下操作：

nTableSize 變為原先的兩倍；
重新申請一次 Hash 區和 Data 區的內存，然后把原先 Data 區的數據以內存拷貝的方式復制到新的 Data 區；
重新計算 nTableMask；
釋放掉原先 Data 區的內存；
做 rehash 。主要是為了重建 Hash 區。

負載因子（Load Factor）

負載因子會影響 hash 碰撞的概率從而影響到耗時，也會影響 Hash 區的大小來影響內存消耗。

在 PHP 中，用 nTableMask 和 nTableSize 的關系來體現：

負載因子 = |nTableMask / nTableSize|

負載因子為 1 的時候（PHP 5），nTableMask == - (nTableSize) 。
負載因子為 0.5 的時候（PHP 7）， nTableMask == - (nTableSize + nTableSize) 。

為什么負載因子會影響時間消耗和內存消耗？

負載因子越大， nTableMask 絕對值就越?。╪TableMask 本身受到 nTableSize 的影響），從而導致 Hash 區變小。

Hash 區一旦變小，更容易產生碰撞。也就使得沖突鏈更長，執行的操作會在沖突鏈的時間消耗變得更長。

負載因子越小，Hash 區變大，使得內存消耗更多，但沖突鏈變短，操作耗時變小。

負載因子時間消耗內存消耗大小大小大小

所以要根據對內存和時間的要求來做調整。

PHP 的負載因子從 1 （PHP5） 降到 0.5 （PHP7），使得速度變快了，但同時內存消耗變大。

針對內存消耗，PHP 還做了個改進，增加了 packed array。

packed array

packed array 的所有 key 是自然數，且依次添加的元素的 key 逐漸增大（不要求連續）。

packed array 查詢時可以直接根據下標計算目標元素的位置（相當于 c 語言的數組），因此它不需要 Hash 區來加速。

不過由于在某些條件下， packed array 會轉成 hash array ，所以它仍然保留 nTableMask 。只是 nTableMask 固定為最小值，當前為 -2 。

Hash 區只有兩個位置，其值都是 HT_INVALID_IDX ，也就是 -1 。

以上內容希望幫助到大家，很多PHPer在進階的時候總會遇到一些問題和瓶頸，業務代碼寫多了沒有方向感，不知道該從那里入手去提升，對此我整理了一些資料，包括但不限于：分布式架構、高可擴展、高性能、高并發、服務器性能調優、TP6，laravel，YII2，Redis，Swoole、Swoft、Kafka、Mysql優化、shell腳本、Docker、微服務、Nginx等多個知識點高級進階干貨需要的可以免費分享給大家，需要戳這里PHP進階架構師>>>視頻、面試文檔免費獲取

本文所用源碼為 PHP 7.4.4 的版本。

PHP 7 數組概述
PHP 中的數組實際上是一個有序映射。映射是一種把 values 關聯到 keys 的類型。此類型在很多方面做了優化，因此可以把它當成真正的數組，或列表（向量），散列表（是映射的一種實現），字典，集合，棧，隊列以及更多可能性。由于數組元素的值也可以是另一個數組，樹形結構和多維數組也是允許的。 —— PHP 官方文檔中文版
這里主要關注兩個點：

key 可以是整數，也可以是字符串。Float、Bool、Null 類型的 key 會被轉換為整數或者字符串存儲，其他類型的會報錯。
value 可以是任意類型。
遍歷數組時，數組元素按照其 key 添加的順序依次取出。
PHP 7 的數組分為 packed array 和 hash array 兩種類型，在滿足一定條件時可以互轉。

hash array 的 key 可以是整數也可以是字符串，在 hash 沖突時使用鏈表（沖突鏈）來解決沖突問題。
packed array 的所有 key 是自然數，且依次添加的元素的 key 逐漸增大（不要求連續）。它的耗時和內存占用都比 hash 數組低。
以下僅介紹 hash array 相關的內容。

主要數據類型
下圖是數組主要的數據類型：

Hash 區               arData                 Data 區

                                            +
                                            | 指 針 指 向 Data 區 的 開 始
                                            v

+----------+----------+----------+----------+----------+----------+----------+----------+
|          |          |          |          |          |          |          |          |
|nTableMask|nTableMask|  ......  |    -1    |    0     |    1     |  ......  |nTableSize|
|          |    +1    |          |          |          |          |          |    +1    |
+---------------------------------------------------------------------------------------+
|          |          |          |          |          |          |          |          |
| uint32_t | uint32_t |  ......  | uint32_t |  Bucket  |  Bucket  |  ......  |  Bucket  |
|          |          |          |          |          |          |          |          |
+----------+----------+----------+----------+----------+----------+----------+----------+

從整體看，這是一個數組。但入口是 arData 而不是處于最左側的一個元素。arData 把數組分為兩部分：

左邊是 Hash 區，其值為 uint32_t 類型，是沖突鏈的第一個元素在 Data 區的下標；
右邊是 Data 區，其值為 Bucket 類型，用于存儲數據及其相關信息。
由于 arData 主要指向 Data 區，因此其默認類型被配置為 Bucket 指針。

在申請內存時，會把 Hash 區所需的內存大小加上 Data 區所需的內存大小，然后一起申請。

Bucket 長什么樣？

zend_types.h：

/* 數組的基本元素 */
typedef struct _Bucket {
    zval              val;              /* 值 */
    zend_ulong        h;                /* hash 值（或者整數索引） */
    zend_string      *key;              /* 字符串 key（如果存儲時用整數索引，則該值為 NULL） */
} Bucket;

Bucket 把 key 和 value 放在一起了。

在沖突鏈中，Bucket 是一個節點。那么此時心里會有一個疑問：怎么獲取沖突鏈的下一個節點？

沖突鏈
說到鏈表，會很自然地想到鏈表元素的結構體里包含著指向下一個元素的指針 next 。例如單向鏈表：

typedef struct listNode {
    struct listNode *next;
    void *value;
} listNode;

但 Bucket 卻不包含這個指針。

會不會在 Bucket 上一層，也就是數組的結構體定義中有一個專門存放沖突鏈的地方？

zend_types.h：

typedef struct _zend_array HashTable;
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 值轉化為 [nTableMask, -1] 區間內的負數。根據 nTableSize 生成。
    Bucket     *arData;           // 指向 Data 區的指針。
    uint32_t    nNumUsed;         // Data 區最后一個有效 Bucket 的下標 + 1。
    uint32_t    nNumOfElements;   // 存在多少個有效 Bucket。刪除數組元素時，會使其減一。
    uint32_t    nTableSize;       // 總共有多少空間。
    uint32_t    nInternalPointer;
    zend_long   nNextFreeElement;
    dtor_func_t pDestructor;
};
想錯了，換個角度想想.jpg

那往 Bucket 下一層看看：
zend_types.h：

typedef struct _zval_struct     zval;
struct _zval_struct {
    zend_value        value;    // 通用值結構。存儲基礎類型（double）或指針（數組、對象等等）
    union {
        struct {
            // 省略其他定義
        } v;
        uint32_t type_info;        // 值的類型，例如 IS_ARRAY 、IS_UNDEF
    } u1;
    union {
        uint32_t     next;         // 指向 hash 沖突鏈的下一個元素    <--- 就是這里
        // 省略其他定義
    } u2;                       // u2 表示第二個 union
};

驚！鏈表元素的 next 居然藏在 PHP 的通用數據類型 zval 里面。

想不到吧？.jpg

補充一點：
PHP HashMap 的沖突鏈始終是一個鏈表，不會像 JAVA 的 HashMap 那樣在達成一定條件時轉成紅黑樹。這會帶來一定的問題。后面再詳細說明。

怎么看 HashTable ？
再看一遍結構體。

zend_types.h：

typedef struct _zend_array HashTable;
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;       // 根據 nTableSize 生成的負數。用于把 hash 值轉化為 [nTableMask, -1] 區間內的負整數，防止越界。
    Bucket     *arData;           // 指向 Data 區的指針。
    uint32_t    nNumUsed;         // Data 區最后一個有效 Bucket 的下標 + 1。
    uint32_t    nNumOfElements;   // 存在多少個有效 Bucket。刪除數組元素時，會使其減一。
    uint32_t    nTableSize;       // 總共有多少空間。
    uint32_t    nInternalPointer; // 內部指針。受到 reset() 、 end() 、 next() 等的影響。
    zend_long   nNextFreeElement;
    dtor_func_t pDestructor;
};

有效 Bucket 指的是 Bucket val 的類型不為 IS_UNDEF 。也就是不為未定義的（undefined）值。無效 Bucket 反之。

nNumUsed 、nNumOfElements 、 nTableSize 的區別：

nNumUsed        = 4
nNumOfElements  = 3
nTableSize      = 8

+----------+----------+-----------+----------+-----------+-----------+-----------+
|          |          |           |          |           |           |           |
|    0     |    1     |     2     |    3     |     4     |  ......   |     7     |
|          |          |           |          |           |           |           |
+--------------------------------------------------------------------------------+
|          |          |           |          |           |           |           |
|  Bucket  |  Bucket  | Undefined |  Bucket  | Undefined | Undefined | Undefined |
|          |          |   Bucket  |          |   Bucket  |  Buckets  |   Bucket  |
+----------+----------+-----------+----------+-----------+-----------+-----------+

數組的主要操作
PHP 數組主要用到的基本操作有：查找、添加、更新、刪除

PHP 內部操作有：rehash 、擴容

其中查找是較為簡單的，添加、更新、刪除都包含了查找的動作，因此先看查找。

查找
由于 key 有整數和字符串這兩種類型，因此查找的實現也分為兩種。這里以整數 key 為例。

讀源碼時要注意 HT_HASH_* 和 HT_DATA_* 開頭的函數，分別代表著在 Hash 區和 Data 區的操作。
zend_hash.c

static zend_always_inline Bucket *zend_hash_index_find_bucket(const HashTable *ht, zend_ulong h)
{
    uint32_t nIndex;
    uint32_t idx;
    Bucket *p, *arData;

    arData = ht->arData;
    nIndex = h | ht->nTableMask;                // 避免 Hash 區越界
    idx = HT_HASH_EX(arData, nIndex);           // 在 Hash 區取 nIndex 位置的值，結果是 Data 區某個 Bucket 的下標
    while (idx != HT_INVALID_IDX) {
        ZEND_ASSERT(idx < HT_IDX_TO_HASH(ht->nTableSize));  // 確保 Data 區沒有越界
        p = HT_HASH_TO_BUCKET_EX(arData, idx);  // 用 Data 區下標獲取 Bucket，即沖突鏈的第一個 Bucket
        if (p->h == h && !p->key) {             // 整數 key 存到 h，因此比對 h。p->key 為 NULL 表示 Bucket 的 key 為整數 key
            return p;
        }
        idx = Z_NEXT(p->val);                   // 沒有找到的話，從當前的 Bucket 獲取沖突鏈的下一個 Bucket
    }
    return NULL;                                // 鏈表遍歷完也沒找到，那就是不存在
}

舉個例子：

nTableSize = 8

 nTableMask = -(nTableSize + nTableSize)

            = (-16)            = (11111111111111111111111111110000)
                   10                                              2

 h          = (100000000)      = (00000101111101011110000100000000)
                         10                                        2

 nIndex     = (h | nTableMask) = (11111111111111111111111111110000)  = (-16)
                                                                   2     +  10
                                                                         |
     +-------------------------------------------------------------------+
     |
     |                  Hash          arData          Data
     |
     |                                   +
     |                                   |              +----------------------------+
     v                                   v              v                            |
                                                                                     |
+---------+---------+----------+---------+---------+---------+----------+---------+  |
|         |         |          |         |         |         |          |         |  |
|   -16   |   -15   |  ......  |   -1    |    0    |    1    |  ......  |    7    |  |
|         |         |          |         |         |         |          |         |  |
+---------------------------------------------------------------------------------+  |
|         |         |          |         |         |         |          |         |  |
|    1    |    6    |  ......  |    5    | Bucket0 | Bucket1 |  ......  | Bucket7 |  |
|         |         |          |         |         |         |          |         |  |
+---------+---------+----------+---------+---------+---------+----------+---------+  |
                                                                                     |
     +                                                 +                     ^       |
     |                                                 |        next         |       |
     |                                                 +---------------------+       |
     |                                                                               |
     +-------------------------------------------------------------------------------+

至于為什么 nTableMask = -(nTableSize + nTableSize) ，見下文的【負載因子】。

nTableMask 使得無論多大的 uint32_t ，在按位或以及轉成有符號整數后，都會變成負整數，并且其值會在 [nTableMask, -1] 這個區間。

介紹完整數 key 的查找，順便對比一下字符串 key 的查找，不同之處如下：

字符串 key 會存到 p->key 里面，而這個字符串的 hash 存到 p->h 里面。
在比較 key 的時候，整數 key 是比較兩個整數是否相等，而字符串 key 會先比較 hash 是否相等，然后比較兩個字符串是否相等。
添加
依然取整數 key 為例。這里不關注更新元素的部分和 packed array 的部分。

zend_hash.c:

static zend_always_inline zval *_zend_hash_index_add_or_update_i(HashTable *ht, zend_ulong h, zval *pData, uint32_t flag)
{
    // ... 省略代碼
    idx = ht->nNumUsed++;                       // 使用空間 + 1
    nIndex = h | ht->nTableMask;                // 取 hash 值對應的 Hash 區的下標
    p = ht->arData + idx;                       // 獲取指向新元素的指針
    Z_NEXT(p->val) = HT_HASH(ht, nIndex);       // 新 Bucket 指向 Hash 區下標所指的沖突鏈第一個 Bucket
    HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx);  // Hash 區下標指向新 Bucket
    if ((zend_long)h >= (zend_long)ht->nNextFreeElement) {
        ht->nNextFreeElement = h < ZEND_LONG_MAX ? h + 1 : ZEND_LONG_MAX;
    }
add:
    ht->nNumOfElements++;                       // 元素個數 + 1
    p->h = h;                                   // 整數 key 的下標就是 hash
    p->key = NULL;                              // 整數 key 時，必須把 p->key 設置為 NULL
    ZVAL_COPY_VALUE(&p->val, pData);            // 把要添加的值復制到新 Bucket 里面

    return &p->val;
}

小二，上圖！

nNumUsed       = 1

 nNumOfElements = 1

 nTableSize     = 8

 nTableMask     = (-16)            = (11111111111111111111111111110000)
                       10                                              2

 h              = (100000000)      = (00000101111101011110000100000000)
                             10                                        2

 nIndex         = (h + nTableMask) = (11111111111111111111111111110000)  = (-16)
                                                                       2        10
                                                                             +
                                                                             |
     +-----------------------------------------------------------------------+
     |
     |                 Hash          arData          Data
     |
     |                                  +
     |                                  |    +-------------------------------------+
     v                                  v    v                                     |
                                                                                   |
+---------+---------+---------+---------+---------+---------+---------+---------+  |
|         |         |         |         |         |         |         |         |  |
|   -16   |   -15   | ......  |   -1    |    0    |    1    |  ...... |    7    |  |
|         |         |         |         |         |         |         |         |  |
+-------------------------------------------------------------------------------+  |
|         |         |         |         |         |Undefined|Undefined|Undefined|  |
|    0    |   -1    | ......  |   -1    | Bucket0 | Bucket1 | Buckets | Bucket7 |  |
|         |         |         |         |         |         |         |         |  |
+---------+---------+---------+---------+---------+---------+---------+---------+  |
                                                                                   |
     +                                                                             |
     +-----------------------------------------------------------------------------+

                                                        ^
                                                        +

                                                   可 用 的 Bucket

 nNumUsed       = 2

 nNumOfElements = 2

                       Hash          arData          Data

                                        +
                                        |              +---------------------------+
                                        v              v                           |
                                                                                   |
+---------+---------+---------+---------+---------+---------+---------+---------+  |
|         |         |         |         |         |         |         |         |  |
|   -16   |   -15   | ......  |   -1    |    0    |    1    | ......  |    7    |  |
|         |         |         |         |         |         |         |         |  |
+-------------------------------------------------------------------------------+  |
|         |         |         |         |         |         |Undefined|undefined|  |
|    1    |   -1    | ......  |   -1    | Bucket0 | Bucket1 | Buckets | Bucket7 |  |
|         |         |         |         |         |         |         |         |  |
+---------+---------+---------+---------+---------+---------+---------+---------+  |
                                                                                   |
     +                                       ^   next   +                          |
     |                                       +----------+                          |
     |                                                                             |
     +-----------------------------------------------------------------------------+

文字表述為：

獲取數組 arData 最后一個元素之后的合法位置（這個位置的內存在之前已經申請好了）。把這里的 Bucket 稱為 BucketA。
把 BucketA 的下標放入 BucketA 的 h 中，把要添加的元素值放入 BucketA 的 val 。
把 Hash 區 (h | nTableMask) 位置指向的 Data 下標存儲的 Bucket 稱為 BucketB。
把 BucketA 的 val 的 next 指向 BucketB 。
更新Hash 區 (h | nTableMask) 位置的值為 BucketA 的下標。
Hash 區 -1 表示 HT_INVALID_IDX

在上面的添加部分，可以看到函數的定義是：

static zend_always_inline zval *_zend_hash_index_add_or_update_i(HashTable *ht, zend_ulong h, zva

它把添加和更新放在一起處理了。

實際上在添加的時候，會先使用：

zend_hash_index_find_bucket(const HashTable *ht, zend_ulong h)

來看 h 這個 key 是否存在。如果存在就執行更新，如果不在就執行添加。

更新的操作就是把 pData 復制到找到的 Bucket 里面，替換掉原先的值。

刪除
刪除分為三種情況：

目標 key 不存在
目標 key 存在，其指向的 Bucket 處于沖突鏈的第一個位置
目標 key 存在，其指向的 Bucket 不處于沖突鏈的第一個位置
目標 key 不存在，直接返回就可以了。

目標 key 存在時，包括兩個主要的操作：

處理沖突鏈指針
釋放內存
處理沖突鏈的指針時，分為兩種情況：

在第一個位置：直接讓 Hash 區的值指向沖突鏈第二個位置的 Bucket 在 Data 區的下標；
不在第一個位置：同鏈表刪除中間元素的操作。
釋放內存時：

如果 key 是字符串，則嘗試釋放 key 的空間；
把 Bucket 的 val 復制到另一個變量 data，把 Bucket 的 val 的類型設置為 undefined；
嘗試釋放 data 所占的空間。
做刪除動作的入口是：

zend_hash_del_bucket(HashTable *ht, Bucket *p)

做核心操作的是：

_zend_hash_del_el_ex(HashTable *ht, uint32_t idx, Bucket *p, Bucket *prev)

看一看源碼：

zend_hash.c:

static zend_always_inline void _zend_hash_del_el_ex(HashTable *ht, uint32_t idx, Bucket *p, Bucket *prev)
{
    if (!(HT_FLAGS(ht) & HASH_FLAG_PACKED)) {
        if (prev) {                                                 // 處于沖突鏈的中間
            Z_NEXT(prev->val) = Z_NEXT(p->val);
        } else {                                                    // 處于沖突鏈的第一個
            HT_HASH(ht, p->h | ht->nTableMask) = Z_NEXT(p->val);    // 讓 Hash 區的值指向下一個 Bucket 的 Data 區下標
        }
    }

    idx = HT_HASH_TO_IDX(idx);
    ht->nNumOfElements--;    // 數組元素計數器減一。此時 nNumUsed 保持不變。

    // 如果數組內部指針指向要刪除的這個 Bucket ，則讓其指向數組下一個有效 Bucket 。
    if (ht->nInternalPointer == idx || UNEXPECTED(HT_HAS_ITERATORS(ht))) {
        uint32_t new_idx;

        new_idx = idx;
        while (1) {
            new_idx++;
            if (new_idx >= ht->nNumUsed) {
                break;
            } else if (Z_TYPE(ht->arData[new_idx].val) != IS_UNDEF) {
                break;
            }
        }
        if (ht->nInternalPointer == idx) {
            ht->nInternalPointer = new_idx;
        }
        zend_hash_iterators_update(ht, idx, new_idx);
    }

    // 如果要刪除的元素是數組的最后一個元素，則嘗試從后往前多回收幾個無效 Bucket
    if (ht->nNumUsed - 1 == idx) {
        do {
            ht->nNumUsed--;
        } while (ht->nNumUsed > 0 && (UNEXPECTED(Z_TYPE(ht->arData[ht->nNumUsed-1].val) == IS_UNDEF)));
        ht->nInternalPointer = MIN(ht->nInternalPointer, ht->nNumUsed);
    }

    // key 為字符串時，釋放字符串內存
    if (p->key) {
        zend_string_release(p->key);
    }

    if (ht->pDestructor) {      // 如果配置了析構函數，則調用析構函數
        zval tmp;
        ZVAL_COPY_VALUE(&tmp, &p->val);
        ZVAL_UNDEF(&p->val);
        ht->pDestructor(&tmp);
    } else {
        ZVAL_UNDEF(&p->val);    // 沒有析構函數，則直接將 zval 的 u1.type_info 配置為 undefind。不用釋放空間，因為以后元素可以重用這個空間
    }
}

PHP 數組可擁有的最大容量

zend_types.h


#if SIZEOF_SIZE_T == 4
# define HT_MAX_SIZE 0x04000000 /* small enough to avoid overflow checks */
/* 省略代碼 */
#elif SIZEOF_SIZE_T == 8
# define HT_MAX_SIZE 0x80000000
/* 省略代碼 */
#else
# error "Unknown SIZEOF_SIZE_T"
#endif

根據 sizeof(size_t) 的執行結果判斷應該設置為 67108864 還是 2147483648 。

0x04000000 轉為二進制是： 00000100000000000000000000000000 0x80000000 轉為二進制是：
10000000000000000000000000000000

當 nNumUsed 大于等于 nTableSize 時，會觸發 Resize 操作，以此獲取更多可使用的 Bucket 。

Resize 策略
Resize 的定義是：

zend_hash.c：

static void ZEND_FASTCALL zend_hash_do_resize(HashTable *ht)

Resize 有兩種策略：

rehash
雙倍擴容 + rehash
之所以有不用雙倍擴容的選擇，是因為 PHP 在刪除元素時，只是將對應 Data 區的 Bucket 的值設置為 undefined，并沒有移動后面的元素。

選擇的條件主要涉及 HashTable 的三個成員：

struct _zend_array {
    // ...省略
    uint32_t    nNumUsed;         // Data 區最后一個有效 Bucket 的下標 + 1。
    uint32_t    nNumOfElements;   // 存在多少個有效 Bucket。刪除數組元素時，會使其減一。
    uint32_t    nTableSize;       // 總共有多少空間。
    // ...省略
}

什么情況下只需要 rehash ？

源碼是：ht->nNumUsed > ht->nNumOfElements + (ht->nNumOfElements >> 5)

這里做一個轉換，方便理解：

ht->nNumUsed - ht->nNumOfElements > (ht->nNumOfElements >> 5)

也就是被設置為 undefined 的 Bucket 數量大于當前元素個數除以 32 向下取整的值。

例如：

當 nNumUsed 為 2048 ， nNumOfElements 為 2000 的時候，得到 2048 - 2000 < 62 ，因此執行擴容。
當 nNumUsed 為 2048 ， nNumOfElements 為 1900 的時候，得到 2048 - 1900 > 59 ，因此執行 rehash。
rehash 做以下操作：

清空 Hash 區；
取兩個指針，一個指向當前掃描的位置（叫做 p），一個指向遷移后的位置（叫做 q），遍歷直到 p 到達 nNumUsed ；
p 在碰到無效 Bucket 時，會繼續往前走一步，不做其他事。
p 在碰到有效 Bucket 時，會把 Bucket 的值復制到 q 指向的 Bucket 的值，并且 p 和 q 一起往前走一步。
這種做法的效率會比每次移動有效 Bucket 都把后面的數據一起往前移動來得高。
重新創建沖突鏈；
更新內部指針，使其指向更新位置后的 Bucket；
更新 nNumUsed，使其等于 nNumOfElements 。

什么情況下雙倍擴容 + rehash ？
滿足只 rehash 的條件就只做 rehash，如果不滿足條件并且 nTableSize 小于數組可擁有的最大容量（HT_MAX_SIZE），則雙倍擴容。

由于 HT_MAX_SIZE 是 0x04000000 或者 0x80000000，并且 nTableSize 始終是 2 的次方，所以最后一次雙倍擴容后的容量剛好是 HT_MAX_SIZE 。

0x04000000 轉為二進制是： 00000100000000000000000000000000 0x80000000 轉為二進制是：
10000000000000000000000000000000

雙倍擴容時，做以下操作：

nTableSize 變為原先的兩倍；
重新申請一次 Hash 區和 Data 區的內存，然后把原先 Data 區的數據以內存拷貝的方式復制到新的 Data 區；
重新計算 nTableMask；
釋放掉原先 Data 區的內存；
做 rehash 。主要是為了重建 Hash 區。

負載因子（Load Factor）

負載因子會影響 hash 碰撞的概率從而影響到耗時，也會影響 Hash 區的大小來影響內存消耗。

在 PHP 中，用 nTableMask 和 nTableSize 的關系來體現：

負載因子 = |nTableMask / nTableSize|

負載因子為 1 的時候（PHP 5），nTableMask == - (nTableSize) 。
負載因子為 0.5 的時候（PHP 7）， nTableMask == - (nTableSize + nTableSize) 。

為什么負載因子會影響時間消耗和內存消耗？

負載因子越大， nTableMask 絕對值就越?。╪TableMask 本身受到 nTableSize 的影響），從而導致 Hash 區變小。

Hash 區一旦變小，更容易產生碰撞。也就使得沖突鏈更長，執行的操作會在沖突鏈的時間消耗變得更長。

負載因子越小，Hash 區變大，使得內存消耗更多，但沖突鏈變短，操作耗時變小。

負載因子時間消耗內存消耗大小大小大小

所以要根據對內存和時間的要求來做調整。

PHP 的負載因子從 1 （PHP5） 降到 0.5 （PHP7），使得速度變快了，但同時內存消耗變大。

針對內存消耗，PHP 還做了個改進，增加了 packed array。

packed array

packed array 的所有 key 是自然數，且依次添加的元素的 key 逐漸增大（不要求連續）。

packed array 查詢時可以直接根據下標計算目標元素的位置（相當于 c 語言的數組），因此它不需要 Hash 區來加速。

不過由于在某些條件下， packed array 會轉成 hash array ，所以它仍然保留 nTableMask 。只是 nTableMask 固定為最小值，當前為 -2 。

Hash 區只有兩個位置，其值都是 HT_INVALID_IDX ，也就是 -1 。

關于PHP底層代碼如何實現PHP 7數組的就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。