前言
php小編香蕉全面剖析php數組底層實現邏輯。php中的數組是一種靈活且強大的數據結構，背后的實現邏輯卻是相當復雜的。在本文中，我們將深入探討php數組的底層原理，包括數組的內部結構、索引與哈希表的關系，以及數組的增刪改查操作的實現方式。通過了解php數組的底層實現邏輯，可以幫助開發者更好地理解和利用數組這一重要的數據結構。
數組的結構
一個數組在 PHP 內核里是長什么樣的呢？我們可以從 PHP 的源碼里看到其結構如下：
<code>//?定義結構體別名為?HashTable
<a style="color:#f60; text-decoration:underline;" href="https://www.php.cn/zt/58423.html" target="_blank">typedef</a>?struct?_zend_array?HashTable;
struct?_zend_array?{
//?<strong class="keylink">GC</strong>?保存引用計數，內存管理相關；本文不涉及
zend_refcounted_h?gc;
//?u?儲存輔助信息；本文不涉及
u<strong class="keylink">NIO</strong>n?{
struct?{
ZEND_ENDIAN_LOHI_4(
zend_uchar????flags,
zend_uchar????nApplyCount,
zend_uchar????nIteratorsCount,
zend_uchar????consistency)
}?v;
uint32_t?flags;
}?u;
//?用于散列函數
uint32_t??????????nTableMask;
//?arData?指向儲存元素的數組第一個?Bucket，Bucket?為統一的數組元素類型
Bucket???????????*arData;
//?已使用?Bucket?數
uint32_t??????????nNumUsed;
//?數組內有效元素個數
uint32_t??????????nNumOfElements;
//?數組總容量
uint32_t??????????nTableSize;
//?內部指針，用于遍歷
uint32_t??????????nInternalPointer;
//?下一個可用數字<strong class="keylink">索引</strong>
zend_long?????????nNextFreeElement;
//?析構函數
dtor_func_t???????pDestructor;
};</code>
登錄后復制
nNumUsed 和 nNumOfElements 的區別：nNumUsed 指的是 arData 數組中已使用的 Bucket 數，因為數組在刪除元素后只是將該元素 Bucket 對應值的類型設置為 IS_UNDEF（因為如果每次刪除元素都要將數組移動并重新索引太浪費時間），而 nNumOfElements 對應的是數組中真正的元素個數。
nTableSize 數組的容量，該值為 2 的冪次方。PHP 的數組是不定長度但 C 語言的數組定長的，為了實現 PHP 的不定長數組的功能，采用了「擴容」的機制，就是在每次插入元素的時候判斷 nTableSize 是否足以儲存。如果不足則重新申請 2 倍 nTableSize 大小的新數組，并將原數組復制過來（此時正是清除原數組中類型為 IS_UNDEF 元素的時機）并且重新索引。
nNextFreeElement 保存下一個可用數字索引，例如在 PHP 中 $a[] = 1; 這種用法將插入一個索引為 nNextFreeElement 的元素，然后 nNextFreeElement ?自增 1。
_zend_array 這個結構先講到這里，有些結構體成員的作用在下文會解釋，不用緊張O(∩_∩)O哈哈~。下面來看看作為數組成員的 Bucket 結構：
<code>typedef?struct?_Bucket?{
//?數組元素的值
zval??????????????val;
//?key?通過?Time?33?<strong class="keylink">算法</strong>計算得到的哈希值或數字索引
zend_ulong????????h;
//?字符鍵名，數字索引則為?NULL
zend_string??????*key;
}?Bucket;</code>
登錄后復制
數組訪問
我們知道 PHP 數組是基于哈希表實現的，而與一般哈希表不同的是 PHP 的數組還實現了元素的有序性，就是插入的元素從內存上來看是連續的而不是亂序的，為了實現這個有序性 PHP 采用了「映射表」技術。下面就通過圖例說明我們是如何訪問 PHP 數組的元素 :-D。
注意：因為鍵名到映射表下標經過了兩次散列運算，為了區分本文用哈希特指第一次散列，散列即為第二次散列。
由圖可知，映射表和數組元素在同一片連續的內存中，映射表是一個長度與存儲元素相同的整型數組，它默認值為 -1 ，有效值為 Bucket 數組的下標。而 HashTable->arData 指向的是這片內存中 Bucket 數組的第一個元素。
舉個例子 $a['key'] 訪問數組 $a 中鍵名為 key 的成員，流程介紹：首先通過 Time 33 算法計算出 key 的哈希值，然后通過散列算法計算出該哈希值對應的映射表下標，因為映射表中保存的值就是 Bucket 數組中的下標值，所以就能獲取到 Bucket 數組中對應的元素。
現在我們來聊一下散列算法，就是通過鍵名的哈希值映射到「映射表」的下標的算法。其實很簡單就一行代碼：
<code>nIndex?=?h?|?ht->nTableMask;</code>
登錄后復制
將哈希值和 nTableMask 進行或運算即可得出映射表的下標，其中 nTableMask 數值為 nTableSize 的負數。并且由于 ?nTableSize 的值為 2 的冪次方，所以 h | ht->nTableMask 的取值范圍在 [-nTableSize, -1] 之間，正好在映射表的下標范圍內。至于為何不用簡單的「取余」運算而是費盡周折的采用「按位或」運算？因為「按位或」運算的速度要比「取余」運算要快很多，我覺得對于這種頻繁使用的操作來說，復雜一點的實現帶來的時間上的優化是值得的。
散列沖突
不同鍵名的哈希值通過散列計算得到的「映射表」下標有可能相同，此時便發生了散列沖突。對于這種情況 PHP 使用了「鏈地址法」解決。下圖是訪問發生散列沖突的元素的情況：
這看似與第一張圖差不多，但我們同樣訪問 $a['key'] 的過程多了一些步驟。首先通過散列運算得出映射表下標為 -2 ，然后訪問映射表發現其內容指向 arData 數組下標為 1 的元素。此時我們將該元素的 key 和要訪問的鍵名相比較，發現兩者并不相等，則該元素并非我們所想訪問的元素，而元素的 val.u2.next 保存的值正是下一個具有相同散列值的元素對應 arData 數組的下標，所以我們可以不斷通過 next 的值遍歷直到找到鍵名相同的元素或查找失敗。
插入元素
插入元素的函數 _zend_hash_add_or_update_i ，基于 PHP 7.2.9 的代碼如下：
<code>static?zend_always_inline?zval?*_zend_hash_add_or_update_i(HashTable?*ht,?zend_string?*key,?zval?*pData,?uint32_t?flag?ZEND_FILE_LINE_DC)
{
zend_ulong?h;
uint32_t?nIndex;
uint32_t?idx;
Bucket?*p;
IS_CONSISTENT(ht);
HT_ASSERT_RC1(ht);
if?(UNEXPECTED(!(ht->u.flags?&?HASH_FLAG_INITIALIZED)))?{?//?數組未初始化
//?初始化數組
CHECK_INIT(ht,?0);
//?跳轉至插入元素段
goto?add_to_hash;
}?else?if?(ht->u.flags?&?HASH_FLAG_PACKED)?{?//?數組為連續數字索引數組
//?轉換為關聯數組
zend_hash_packed_to_hash(ht);
}?else?if?((flag?&?HASH_ADD_NEW)?==?0)?{?//?添加新元素
//?查找鍵名對應的元素
p?=?zend_hash_find_bucket(ht,?key);
if?(p)?{?//?若相同鍵名元素存在
zval?*data;
if?(flag?&?HASH_ADD)?{?//?指定?add?操作
if?(!(flag?&?HASH_UPDATE_INDIRECT))?{?//?若不允許更新間接類型變量則直接返回
return?NULL;
}
//?確定當前值和新值不同
ZEND_ASSERT(&p->val?!=?pData);
//?data?指向原數組成員值
data?=?&p->val;
if?(Z_TYPE_P(data)?==?IS_INDIRECT)?{?//?原數組元素變量類型為間接類型
? //?取間接變量對應的變量
data?=?Z_INDIRECT_P(data);
if?(Z_TYPE_P(data)?!=?IS_UNDEF)?{?//?該對應變量存在則直接返回
return?NULL;
}
}?else?{?//?非間接類型直接返回
return?NULL;
}
}?else?{?//?沒有指定?add?操作
//?確定當前值和新值不同
ZEND_ASSERT(&p->val?!=?pData);
//?data?指向原數組元素值
data?=?&p->val;
//?允許更新間接類型變量則?data?指向對應的變量
if?((flag?&?HASH_UPDATE_INDIRECT)?&&?Z_TYPE_P(data)?==?IS_INDIRECT)?{
data?=?Z_INDIRECT_P(data);
}
}
if?(ht->pDestructor)?{?//?析構函數存在
//?執行析構函數
ht->pDestructor(data);
}
//?將?pData?的值復制給?data
ZVAL_COPY_VALUE(data,?pData);
return?data;
}
}
//?如果哈希表已滿，則進行擴容
ZEND_HASH_IF_FULL_DO_RESIZE(ht);
add_to_hash:
//?數組已使用?Bucket?數?+1
idx?=?ht->nNumUsed++;
//?數組有效元素數目?+1
ht->nNumOfElements++;
//?若內部指針無效則指向當前下標
if?(ht->nInternalPointer?==?HT_INVALID_IDX)?{
ht->nInternalPointer?=?idx;
}
????
zend_hash_iterators_update(ht,?HT_INVALID_IDX,?idx);
//?p?為新元素對應的?Bucket
p?=?ht->arData?+?idx;
//?設置鍵名
p->key?=?key;
if?(!ZSTR_IS_INTERNED(key))?{
zend_string_addref(key);
ht->u.flags?&=?~HASH_FLAG_STATIC_KEYS;
zend_string_hash_val(key);
}
//?計算鍵名的哈希值并賦值給?p
p->h?=?h?=?ZSTR_H(key);
//?將?pData?賦值該?Bucket?的?val
ZVAL_COPY_VALUE(&p->val,?pData);
//?計算映射表下標
nIndex?=?h?|?ht->nTableMask;
//?解決沖突，將原映射表中的內容賦值給新元素變量值的?u2.next?成員
Z_NEXT(p->val)?=?HT_HASH(ht,?nIndex);
//?將映射表中的值設為?idx
HT_HASH(ht,?nIndex)?=?HT_IDX_TO_HASH(idx);
return?&p->val;
}</code>
登錄后復制
?擴容
前面將數組結構的時候我們有提到擴容，而在插入元素的代碼里有這樣一個宏 ZEND_HASH_IF_FULL_DO_RESIZE，這個宏其實就是調用了 zend_hash_do_resize 函數，對數組進行擴容并重新索引。注意：并非每次 Bucket 數組滿了都需要擴容，如果 Bucket 數組中 IS_UNDEF 元素的數量占較大比例，就直接將 IS_UNDEF 元素刪除并重新索引，以此節省內存。下面我們看看 zend_hash_do_resize 函數：
重新索引的邏輯在 zend_hash_rehash 函數中，代碼如下：
?總結
嗯哼，本文就到此結束了，因為自身水平原因不能解釋的十分詳盡清楚。這算是我寫過最難寫的內容了，寫完之后似乎覺得這篇文章就我自己能看明白/(ㄒoㄒ)/~~因為文筆太辣雞。想起一句話「如果你不能簡單地解釋一樣東西，說明你沒真正理解它?！筆HP 的源碼里有很多細節和實現我都不算熟悉，這篇文章只是一個我的 PHP 底層學習的開篇，希望以后能夠寫出真正深入淺出的好文章。
