這篇文章將為大家詳細講解有關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數組的就分享到這里了,希望以上內容可以對大家有一定的幫助,可以學到更多知識。如果覺得文章不錯,可以把它分享出去讓更多的人看到。
免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。