從源碼看 PHP 7 數組的實現
- 2020 年 3 月 18 日
- 筆記
本文所用源碼為 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, zval *pData, uint32_t flag)它把添加和更新放在一起處理了。
實際上在添加的時候，會先使用：
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)。
上一次修改負載因子的提交是：
https://github.com/php/php-src/commit/34ed8e53fea63903f85326ea1d5bd91ece86b7ae
為什麼負載因子會影響時間消耗和記憶體消耗？
負載因子越大， nTableMask 絕對值就越小（nTableMask 本身受到 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 。
