這篇文章將為大家詳細(xì)講解有關(guān)PHP底層代碼如何實(shí)現(xiàn)PHP 7數(shù)組的，小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

站在用戶的角度思考問題，與客戶深入溝通，找到保亭黎族網(wǎng)站設(shè)計(jì)與保亭黎族網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗(yàn)，讓設(shè)計(jì)與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個(gè)性化、用戶體驗(yàn)好的作品，建站類型包括：成都網(wǎng)站建設(shè)、網(wǎng)站制作、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣、主機(jī)域名、虛擬主機(jī)、企業(yè)郵箱。業(yè)務(wù)覆蓋保亭黎族地區(qū)。

PHP 7 數(shù)組概述
PHP 中的數(shù)組實(shí)際上是一個(gè)有序映射。映射是一種把 values 關(guān)聯(lián)到 keys 的類型。此類型在很多方面做了優(yōu)化，因此可以把它當(dāng)成真正的數(shù)組，或列表（向量），散列表（是映射的一種實(shí)現(xiàn)），字典，集合，棧，隊(duì)列以及更多可能性。由于數(shù)組元素的值也可以是另一個(gè)數(shù)組，樹形結(jié)構(gòu)和多維數(shù)組也是允許的。 —— PHP 官方文檔中文版
這里主要關(guān)注兩個(gè)點(diǎn)：

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

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

主要數(shù)據(jù)類型
下圖是數(shù)組主要的數(shù)據(jù)類型：

Hash 區(qū)               arData                 Data 區(qū)

                                            +
                                            | 指 針 指 向 Data 區(qū) 的 開 始
                                            v

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

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

左邊是 Hash 區(qū)，其值為 uint32_t 類型，是沖突鏈的第一個(gè)元素在 Data 區(qū)的下標(biāo)；
右邊是 Data 區(qū)，其值為 Bucket 類型，用于存儲(chǔ)數(shù)據(jù)及其相關(guān)信息。
由于 arData 主要指向 Data 區(qū)，因此其默認(rèn)類型被配置為 Bucket 指針。

在申請(qǐng)內(nèi)存時(shí)，會(huì)把 Hash 區(qū)所需的內(nèi)存大小加上 Data 區(qū)所需的內(nèi)存大小，然后一起申請(qǐng)。

Bucket 長什么樣？

zend_types.h：

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

Bucket 把 key 和 value 放在一起了。

在沖突鏈中，Bucket 是一個(gè)節(jié)點(diǎn)。那么此時(shí)心里會(huì)有一個(gè)疑問：怎么獲取沖突鏈的下一個(gè)節(jié)點(diǎn)？

沖突鏈
說到鏈表，會(huì)很自然地想到鏈表元素的結(jié)構(gòu)體里包含著指向下一個(gè)元素的指針 next 。例如單向鏈表：

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

但 Bucket 卻不包含這個(gè)指針。

會(huì)不會(huì)在 Bucket 上一層，也就是數(shù)組的結(jié)構(gòu)體定義中有一個(gè)專門存放沖突鏈的地方？

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 值轉(zhuǎn)化為 [nTableMask, -1] 區(qū)間內(nèi)的負(fù)數(shù)。根據(jù) nTableSize 生成。
    Bucket     *arData;           // 指向 Data 區(qū)的指針。
    uint32_t    nNumUsed;         // Data 區(qū)最后一個(gè)有效 Bucket 的下標(biāo) + 1。
    uint32_t    nNumOfElements;   // 存在多少個(gè)有效 Bucket。刪除數(shù)組元素時(shí)，會(huì)使其減一。
    uint32_t    nTableSize;       // 總共有多少空間。
    uint32_t    nInternalPointer;
    zend_long   nNextFreeElement;
    dtor_func_t pDestructor;
};
想錯(cuò)了，換個(gè)角度想想.jpg

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

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

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

想不到吧？.jpg

補(bǔ)充一點(diǎn)：
PHP HashMap 的沖突鏈?zhǔn)冀K是一個(gè)鏈表，不會(huì)像 JAVA 的 HashMap 那樣在達(dá)成一定條件時(shí)轉(zhuǎn)成紅黑樹。這會(huì)帶來一定的問題。后面再詳細(xì)說明。

怎么看 HashTable ？
再看一遍結(jié)構(gòu)體。

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

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

nNumUsed 、nNumOfElements 、 nTableSize 的區(qū)別：

nNumUsed        = 4
nNumOfElements  = 3
nTableSize      = 8

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

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

PHP 內(nèi)部操作有：rehash 、擴(kuò)容

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

查找
由于 key 有整數(shù)和字符串這兩種類型，因此查找的實(shí)現(xiàn)也分為兩種。這里以整數(shù) key 為例。

讀源碼時(shí)要注意 HT_HASH_* 和 HT_DATA_* 開頭的函數(shù)，分別代表著在 Hash 區(qū)和 Data 區(qū)的操作。
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 區(qū)越界
    idx = HT_HASH_EX(arData, nIndex);           // 在 Hash 區(qū)取 nIndex 位置的值，結(jié)果是 Data 區(qū)某個(gè) Bucket 的下標(biāo)
    while (idx != HT_INVALID_IDX) {
        ZEND_ASSERT(idx < HT_IDX_TO_HASH(ht->nTableSize));  // 確保 Data 區(qū)沒有越界
        p = HT_HASH_TO_BUCKET_EX(arData, idx);  // 用 Data 區(qū)下標(biāo)獲取 Bucket，即沖突鏈的第一個(gè) Bucket
        if (p->h == h && !p->key) {             // 整數(shù) key 存到 h，因此比對(duì) h。p->key 為 NULL 表示 Bucket 的 key 為整數(shù) key
            return p;
        }
        idx = Z_NEXT(p->val);                   // 沒有找到的話，從當(dāng)前的 Bucket 獲取沖突鏈的下一個(gè) Bucket
    }
    return NULL;                                // 鏈表遍歷完也沒找到，那就是不存在
}

舉個(gè)例子：

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) ，見下文的【負(fù)載因子】。

nTableMask 使得無論多大的 uint32_t ，在按位或以及轉(zhuǎn)成有符號(hào)整數(shù)后，都會(huì)變成負(fù)整數(shù)，并且其值會(huì)在 [nTableMask, -1] 這個(gè)區(qū)間。

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

字符串 key 會(huì)存到 p->key 里面，而這個(gè)字符串的 hash 存到 p->h 里面。
在比較 key 的時(shí)候，整數(shù) key 是比較兩個(gè)整數(shù)是否相等，而字符串 key 會(huì)先比較 hash 是否相等，然后比較兩個(gè)字符串是否相等。
添加
依然取整數(shù) key 為例。這里不關(guān)注更新元素的部分和 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 值對(duì)應(yīng)的 Hash 區(qū)的下標(biāo)
    p = ht->arData + idx;                       // 獲取指向新元素的指針
    Z_NEXT(p->val) = HT_HASH(ht, nIndex);       // 新 Bucket 指向 Hash 區(qū)下標(biāo)所指的沖突鏈第一個(gè) Bucket
    HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx);  // Hash 區(qū)下標(biāo)指向新 Bucket
    if ((zend_long)h >= (zend_long)ht->nNextFreeElement) {
        ht->nNextFreeElement = h < ZEND_LONG_MAX ? h + 1 : ZEND_LONG_MAX;
    }
add:
    ht->nNumOfElements++;                       // 元素個(gè)數(shù) + 1
    p->h = h;                                   // 整數(shù) key 的下標(biāo)就是 hash
    p->key = NULL;                              // 整數(shù) key 時(shí)，必須把 p->key 設(shè)置為 NULL
    ZVAL_COPY_VALUE(&p->val, pData);            // 把要添加的值復(fù)制到新 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   +                          |
     |                                       +----------+                          |
     |                                                                             |
     +-----------------------------------------------------------------------------+

文字表述為：

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

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

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

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

實(shí)際上在添加的時(shí)候，會(huì)先使用：

zend_hash_index_find_bucket(const HashTable *ht, zend_ulong h)

來看 h 這個(gè) key 是否存在。如果存在就執(zhí)行更新，如果不在就執(zhí)行添加。

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

刪除
刪除分為三種情況：

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

目標(biāo) key 存在時(shí)，包括兩個(gè)主要的操作：

處理沖突鏈指針
釋放內(nèi)存
處理沖突鏈的指針時(shí)，分為兩種情況：

在第一個(gè)位置：直接讓 Hash 區(qū)的值指向沖突鏈第二個(gè)位置的 Bucket 在 Data 區(qū)的下標(biāo)；
不在第一個(gè)位置：同鏈表刪除中間元素的操作。
釋放內(nèi)存時(shí)：

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

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 {                                                    // 處于沖突鏈的第一個(gè)
            HT_HASH(ht, p->h | ht->nTableMask) = Z_NEXT(p->val);    // 讓 Hash 區(qū)的值指向下一個(gè) Bucket 的 Data 區(qū)下標(biāo)
        }
    }

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

    // 如果數(shù)組內(nèi)部指針指向要?jiǎng)h除的這個(gè) Bucket ，則讓其指向數(shù)組下一個(gè)有效 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);
    }

    // 如果要?jiǎng)h除的元素是數(shù)組的最后一個(gè)元素，則嘗試從后往前多回收幾個(gè)無效 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 為字符串時(shí)，釋放字符串內(nèi)存
    if (p->key) {
        zend_string_release(p->key);
    }

    if (ht->pDestructor) {      // 如果配置了析構(gòu)函數(shù)，則調(diào)用析構(gòu)函數(shù)
        zval tmp;
        ZVAL_COPY_VALUE(&tmp, &p->val);
        ZVAL_UNDEF(&p->val);
        ht->pDestructor(&tmp);
    } else {
        ZVAL_UNDEF(&p->val);    // 沒有析構(gòu)函數(shù)，則直接將 zval 的 u1.type_info 配置為 undefind。不用釋放空間，因?yàn)橐院笤乜梢灾赜眠@個(gè)空間
    }
}

PHP 數(shù)組可擁有的最大容量

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

根據(jù) sizeof(size_t) 的執(zhí)行結(jié)果判斷應(yīng)該設(shè)置為 67108864 還是 2147483648 。

0x04000000 轉(zhuǎn)為二進(jìn)制是： 00000100000000000000000000000000 0x80000000 轉(zhuǎn)為二進(jìn)制是：
10000000000000000000000000000000

當(dāng) nNumUsed 大于等于 nTableSize 時(shí)，會(huì)觸發(fā) Resize 操作，以此獲取更多可使用的 Bucket 。

Resize 策略
Resize 的定義是：

zend_hash.c：

static void ZEND_FASTCALL zend_hash_do_resize(HashTable *ht)

Resize 有兩種策略：

rehash
雙倍擴(kuò)容 + rehash
之所以有不用雙倍擴(kuò)容的選擇，是因?yàn)?PHP 在刪除元素時(shí)，只是將對(duì)應(yīng) Data 區(qū)的 Bucket 的值設(shè)置為 undefined，并沒有移動(dòng)后面的元素。

選擇的條件主要涉及 HashTable 的三個(gè)成員：

struct _zend_array {
    // ...省略
    uint32_t    nNumUsed;         // Data 區(qū)最后一個(gè)有效 Bucket 的下標(biāo) + 1。
    uint32_t    nNumOfElements;   // 存在多少個(gè)有效 Bucket。刪除數(shù)組元素時(shí)，會(huì)使其減一。
    uint32_t    nTableSize;       // 總共有多少空間。
    // ...省略
}

什么情況下只需要 rehash ？

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

這里做一個(gè)轉(zhuǎn)換，方便理解：

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

也就是被設(shè)置為 undefined 的 Bucket 數(shù)量大于當(dāng)前元素個(gè)數(shù)除以 32 向下取整的值。

例如：

當(dāng) nNumUsed 為 2048 ， nNumOfElements 為 2000 的時(shí)候，得到 2048 - 2000 < 62 ，因此執(zhí)行擴(kuò)容。
當(dāng) nNumUsed 為 2048 ， nNumOfElements 為 1900 的時(shí)候，得到 2048 - 1900 > 59 ，因此執(zhí)行 rehash。
rehash 做以下操作：

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

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

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

0x04000000 轉(zhuǎn)為二進(jìn)制是： 00000100000000000000000000000000 0x80000000 轉(zhuǎn)為二進(jìn)制是：
10000000000000000000000000000000

雙倍擴(kuò)容時(shí)，做以下操作：

nTableSize 變?yōu)樵鹊膬杀叮?br/>重新申請(qǐng)一次 Hash 區(qū)和 Data 區(qū)的內(nèi)存，然后把原先 Data 區(qū)的數(shù)據(jù)以內(nèi)存拷貝的方式復(fù)制到新的 Data 區(qū)；
重新計(jì)算 nTableMask；
釋放掉原先 Data 區(qū)的內(nèi)存；
做 rehash 。主要是為了重建 Hash 區(qū)。

負(fù)載因子（Load Factor）

負(fù)載因子會(huì)影響 hash 碰撞的概率從而影響到耗時(shí)，也會(huì)影響 Hash 區(qū)的大小來影響內(nèi)存消耗。

在 PHP 中，用 nTableMask 和 nTableSize 的關(guān)系來體現(xiàn)：

負(fù)載因子 = |nTableMask / nTableSize|

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

為什么負(fù)載因子會(huì)影響時(shí)間消耗和內(nèi)存消耗？

負(fù)載因子越大， nTableMask 絕對(duì)值就越?。╪TableMask 本身受到 nTableSize 的影響），從而導(dǎo)致 Hash 區(qū)變小。

Hash 區(qū)一旦變小，更容易產(chǎn)生碰撞。也就使得沖突鏈更長，執(zhí)行的操作會(huì)在沖突鏈的時(shí)間消耗變得更長。

負(fù)載因子越小，Hash 區(qū)變大，使得內(nèi)存消耗更多，但沖突鏈變短，操作耗時(shí)變小。

負(fù)載因子時(shí)間消耗內(nèi)存消耗大小大小大小

所以要根據(jù)對(duì)內(nèi)存和時(shí)間的要求來做調(diào)整。

PHP 的負(fù)載因子從 1 （PHP5） 降到 0.5 （PHP7），使得速度變快了，但同時(shí)內(nèi)存消耗變大。

針對(duì)內(nèi)存消耗，PHP 還做了個(gè)改進(jìn)，增加了 packed array。

packed array

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

packed array 查詢時(shí)可以直接根據(jù)下標(biāo)計(jì)算目標(biāo)元素的位置（相當(dāng)于 c 語言的數(shù)組），因此它不需要 Hash 區(qū)來加速。

不過由于在某些條件下， packed array 會(huì)轉(zhuǎn)成 hash array ，所以它仍然保留 nTableMask 。只是 nTableMask 固定為最小值，當(dāng)前為 -2 。

Hash 區(qū)只有兩個(gè)位置，其值都是 HT_INVALID_IDX ，也就是 -1 。

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

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

PHP 7 數(shù)組概述
PHP 中的數(shù)組實(shí)際上是一個(gè)有序映射。映射是一種把 values 關(guān)聯(lián)到 keys 的類型。此類型在很多方面做了優(yōu)化，因此可以把它當(dāng)成真正的數(shù)組，或列表（向量），散列表（是映射的一種實(shí)現(xiàn)），字典，集合，棧，隊(duì)列以及更多可能性。由于數(shù)組元素的值也可以是另一個(gè)數(shù)組，樹形結(jié)構(gòu)和多維數(shù)組也是允許的。 —— PHP 官方文檔中文版
這里主要關(guān)注兩個(gè)點(diǎn)：

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

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

主要數(shù)據(jù)類型
下圖是數(shù)組主要的數(shù)據(jù)類型：

Hash 區(qū)               arData                 Data 區(qū)

                                            +
                                            | 指 針 指 向 Data 區(qū) 的 開 始
                                            v

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

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

左邊是 Hash 區(qū)，其值為 uint32_t 類型，是沖突鏈的第一個(gè)元素在 Data 區(qū)的下標(biāo)；
右邊是 Data 區(qū)，其值為 Bucket 類型，用于存儲(chǔ)數(shù)據(jù)及其相關(guān)信息。
由于 arData 主要指向 Data 區(qū)，因此其默認(rèn)類型被配置為 Bucket 指針。

在申請(qǐng)內(nèi)存時(shí)，會(huì)把 Hash 區(qū)所需的內(nèi)存大小加上 Data 區(qū)所需的內(nèi)存大小，然后一起申請(qǐng)。

Bucket 長什么樣？

zend_types.h：

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

Bucket 把 key 和 value 放在一起了。

在沖突鏈中，Bucket 是一個(gè)節(jié)點(diǎn)。那么此時(shí)心里會(huì)有一個(gè)疑問：怎么獲取沖突鏈的下一個(gè)節(jié)點(diǎn)？

沖突鏈
說到鏈表，會(huì)很自然地想到鏈表元素的結(jié)構(gòu)體里包含著指向下一個(gè)元素的指針 next 。例如單向鏈表：

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

但 Bucket 卻不包含這個(gè)指針。

會(huì)不會(huì)在 Bucket 上一層，也就是數(shù)組的結(jié)構(gòu)體定義中有一個(gè)專門存放沖突鏈的地方？

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 值轉(zhuǎn)化為 [nTableMask, -1] 區(qū)間內(nèi)的負(fù)數(shù)。根據(jù) nTableSize 生成。
    Bucket     *arData;           // 指向 Data 區(qū)的指針。
    uint32_t    nNumUsed;         // Data 區(qū)最后一個(gè)有效 Bucket 的下標(biāo) + 1。
    uint32_t    nNumOfElements;   // 存在多少個(gè)有效 Bucket。刪除數(shù)組元素時(shí)，會(huì)使其減一。
    uint32_t    nTableSize;       // 總共有多少空間。
    uint32_t    nInternalPointer;
    zend_long   nNextFreeElement;
    dtor_func_t pDestructor;
};
想錯(cuò)了，換個(gè)角度想想.jpg

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

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

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

想不到吧？.jpg

補(bǔ)充一點(diǎn)：
PHP HashMap 的沖突鏈?zhǔn)冀K是一個(gè)鏈表，不會(huì)像 JAVA 的 HashMap 那樣在達(dá)成一定條件時(shí)轉(zhuǎn)成紅黑樹。這會(huì)帶來一定的問題。后面再詳細(xì)說明。

怎么看 HashTable ？
再看一遍結(jié)構(gòu)體。

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

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

nNumUsed 、nNumOfElements 、 nTableSize 的區(qū)別：

nNumUsed        = 4
nNumOfElements  = 3
nTableSize      = 8

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

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

PHP 內(nèi)部操作有：rehash 、擴(kuò)容

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

查找
由于 key 有整數(shù)和字符串這兩種類型，因此查找的實(shí)現(xiàn)也分為兩種。這里以整數(shù) key 為例。

讀源碼時(shí)要注意 HT_HASH_* 和 HT_DATA_* 開頭的函數(shù)，分別代表著在 Hash 區(qū)和 Data 區(qū)的操作。
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 區(qū)越界
    idx = HT_HASH_EX(arData, nIndex);           // 在 Hash 區(qū)取 nIndex 位置的值，結(jié)果是 Data 區(qū)某個(gè) Bucket 的下標(biāo)
    while (idx != HT_INVALID_IDX) {
        ZEND_ASSERT(idx < HT_IDX_TO_HASH(ht->nTableSize));  // 確保 Data 區(qū)沒有越界
        p = HT_HASH_TO_BUCKET_EX(arData, idx);  // 用 Data 區(qū)下標(biāo)獲取 Bucket，即沖突鏈的第一個(gè) Bucket
        if (p->h == h && !p->key) {             // 整數(shù) key 存到 h，因此比對(duì) h。p->key 為 NULL 表示 Bucket 的 key 為整數(shù) key
            return p;
        }
        idx = Z_NEXT(p->val);                   // 沒有找到的話，從當(dāng)前的 Bucket 獲取沖突鏈的下一個(gè) Bucket
    }
    return NULL;                                // 鏈表遍歷完也沒找到，那就是不存在
}

舉個(gè)例子：

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) ，見下文的【負(fù)載因子】。

nTableMask 使得無論多大的 uint32_t ，在按位或以及轉(zhuǎn)成有符號(hào)整數(shù)后，都會(huì)變成負(fù)整數(shù)，并且其值會(huì)在 [nTableMask, -1] 這個(gè)區(qū)間。

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

字符串 key 會(huì)存到 p->key 里面，而這個(gè)字符串的 hash 存到 p->h 里面。
在比較 key 的時(shí)候，整數(shù) key 是比較兩個(gè)整數(shù)是否相等，而字符串 key 會(huì)先比較 hash 是否相等，然后比較兩個(gè)字符串是否相等。
添加
依然取整數(shù) key 為例。這里不關(guān)注更新元素的部分和 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 值對(duì)應(yīng)的 Hash 區(qū)的下標(biāo)
    p = ht->arData + idx;                       // 獲取指向新元素的指針
    Z_NEXT(p->val) = HT_HASH(ht, nIndex);       // 新 Bucket 指向 Hash 區(qū)下標(biāo)所指的沖突鏈第一個(gè) Bucket
    HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx);  // Hash 區(qū)下標(biāo)指向新 Bucket
    if ((zend_long)h >= (zend_long)ht->nNextFreeElement) {
        ht->nNextFreeElement = h < ZEND_LONG_MAX ? h + 1 : ZEND_LONG_MAX;
    }
add:
    ht->nNumOfElements++;                       // 元素個(gè)數(shù) + 1
    p->h = h;                                   // 整數(shù) key 的下標(biāo)就是 hash
    p->key = NULL;                              // 整數(shù) key 時(shí)，必須把 p->key 設(shè)置為 NULL
    ZVAL_COPY_VALUE(&p->val, pData);            // 把要添加的值復(fù)制到新 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   +                          |
     |                                       +----------+                          |
     |                                                                             |
     +-----------------------------------------------------------------------------+

文字表述為：

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

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

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

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

實(shí)際上在添加的時(shí)候，會(huì)先使用：

zend_hash_index_find_bucket(const HashTable *ht, zend_ulong h)

來看 h 這個(gè) key 是否存在。如果存在就執(zhí)行更新，如果不在就執(zhí)行添加。

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

刪除
刪除分為三種情況：

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

目標(biāo) key 存在時(shí)，包括兩個(gè)主要的操作：

處理沖突鏈指針
釋放內(nèi)存
處理沖突鏈的指針時(shí)，分為兩種情況：

在第一個(gè)位置：直接讓 Hash 區(qū)的值指向沖突鏈第二個(gè)位置的 Bucket 在 Data 區(qū)的下標(biāo)；
不在第一個(gè)位置：同鏈表刪除中間元素的操作。
釋放內(nèi)存時(shí)：

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

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 {                                                    // 處于沖突鏈的第一個(gè)
            HT_HASH(ht, p->h | ht->nTableMask) = Z_NEXT(p->val);    // 讓 Hash 區(qū)的值指向下一個(gè) Bucket 的 Data 區(qū)下標(biāo)
        }
    }

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

    // 如果數(shù)組內(nèi)部指針指向要?jiǎng)h除的這個(gè) Bucket ，則讓其指向數(shù)組下一個(gè)有效 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);
    }

    // 如果要?jiǎng)h除的元素是數(shù)組的最后一個(gè)元素，則嘗試從后往前多回收幾個(gè)無效 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 為字符串時(shí)，釋放字符串內(nèi)存
    if (p->key) {
        zend_string_release(p->key);
    }

    if (ht->pDestructor) {      // 如果配置了析構(gòu)函數(shù)，則調(diào)用析構(gòu)函數(shù)
        zval tmp;
        ZVAL_COPY_VALUE(&tmp, &p->val);
        ZVAL_UNDEF(&p->val);
        ht->pDestructor(&tmp);
    } else {
        ZVAL_UNDEF(&p->val);    // 沒有析構(gòu)函數(shù)，則直接將 zval 的 u1.type_info 配置為 undefind。不用釋放空間，因?yàn)橐院笤乜梢灾赜眠@個(gè)空間
    }
}

PHP 數(shù)組可擁有的最大容量

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

根據(jù) sizeof(size_t) 的執(zhí)行結(jié)果判斷應(yīng)該設(shè)置為 67108864 還是 2147483648 。

0x04000000 轉(zhuǎn)為二進(jìn)制是： 00000100000000000000000000000000 0x80000000 轉(zhuǎn)為二進(jìn)制是：
10000000000000000000000000000000

當(dāng) nNumUsed 大于等于 nTableSize 時(shí)，會(huì)觸發(fā) Resize 操作，以此獲取更多可使用的 Bucket 。

Resize 策略
Resize 的定義是：

zend_hash.c：

static void ZEND_FASTCALL zend_hash_do_resize(HashTable *ht)

Resize 有兩種策略：

rehash
雙倍擴(kuò)容 + rehash
之所以有不用雙倍擴(kuò)容的選擇，是因?yàn)?PHP 在刪除元素時(shí)，只是將對(duì)應(yīng) Data 區(qū)的 Bucket 的值設(shè)置為 undefined，并沒有移動(dòng)后面的元素。

選擇的條件主要涉及 HashTable 的三個(gè)成員：

struct _zend_array {
    // ...省略
    uint32_t    nNumUsed;         // Data 區(qū)最后一個(gè)有效 Bucket 的下標(biāo) + 1。
    uint32_t    nNumOfElements;   // 存在多少個(gè)有效 Bucket。刪除數(shù)組元素時(shí)，會(huì)使其減一。
    uint32_t    nTableSize;       // 總共有多少空間。
    // ...省略
}

什么情況下只需要 rehash ？

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

這里做一個(gè)轉(zhuǎn)換，方便理解：

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

也就是被設(shè)置為 undefined 的 Bucket 數(shù)量大于當(dāng)前元素個(gè)數(shù)除以 32 向下取整的值。

例如：

當(dāng) nNumUsed 為 2048 ， nNumOfElements 為 2000 的時(shí)候，得到 2048 - 2000 < 62 ，因此執(zhí)行擴(kuò)容。
當(dāng) nNumUsed 為 2048 ， nNumOfElements 為 1900 的時(shí)候，得到 2048 - 1900 > 59 ，因此執(zhí)行 rehash。
rehash 做以下操作：

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

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

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

0x04000000 轉(zhuǎn)為二進(jìn)制是： 00000100000000000000000000000000 0x80000000 轉(zhuǎn)為二進(jìn)制是：
10000000000000000000000000000000

雙倍擴(kuò)容時(shí)，做以下操作：

nTableSize 變?yōu)樵鹊膬杀叮?br/>重新申請(qǐng)一次 Hash 區(qū)和 Data 區(qū)的內(nèi)存，然后把原先 Data 區(qū)的數(shù)據(jù)以內(nèi)存拷貝的方式復(fù)制到新的 Data 區(qū)；
重新計(jì)算 nTableMask；
釋放掉原先 Data 區(qū)的內(nèi)存；
做 rehash 。主要是為了重建 Hash 區(qū)。

負(fù)載因子（Load Factor）

負(fù)載因子會(huì)影響 hash 碰撞的概率從而影響到耗時(shí)，也會(huì)影響 Hash 區(qū)的大小來影響內(nèi)存消耗。

在 PHP 中，用 nTableMask 和 nTableSize 的關(guān)系來體現(xiàn)：

負(fù)載因子 = |nTableMask / nTableSize|

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

為什么負(fù)載因子會(huì)影響時(shí)間消耗和內(nèi)存消耗？

負(fù)載因子越大， nTableMask 絕對(duì)值就越?。╪TableMask 本身受到 nTableSize 的影響），從而導(dǎo)致 Hash 區(qū)變小。

Hash 區(qū)一旦變小，更容易產(chǎn)生碰撞。也就使得沖突鏈更長，執(zhí)行的操作會(huì)在沖突鏈的時(shí)間消耗變得更長。

負(fù)載因子越小，Hash 區(qū)變大，使得內(nèi)存消耗更多，但沖突鏈變短，操作耗時(shí)變小。

負(fù)載因子時(shí)間消耗內(nèi)存消耗大小大小大小

所以要根據(jù)對(duì)內(nèi)存和時(shí)間的要求來做調(diào)整。

PHP 的負(fù)載因子從 1 （PHP5） 降到 0.5 （PHP7），使得速度變快了，但同時(shí)內(nèi)存消耗變大。

針對(duì)內(nèi)存消耗，PHP 還做了個(gè)改進(jìn)，增加了 packed array。

packed array

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

packed array 查詢時(shí)可以直接根據(jù)下標(biāo)計(jì)算目標(biāo)元素的位置（相當(dāng)于 c 語言的數(shù)組），因此它不需要 Hash 區(qū)來加速。

不過由于在某些條件下， packed array 會(huì)轉(zhuǎn)成 hash array ，所以它仍然保留 nTableMask 。只是 nTableMask 固定為最小值，當(dāng)前為 -2 。

Hash 區(qū)只有兩個(gè)位置，其值都是 HT_INVALID_IDX ，也就是 -1 。

關(guān)于PHP底層代碼如何實(shí)現(xiàn)PHP 7數(shù)組的就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到。