PHP7數(shù)組的底層實(shí)現(xiàn)示例

PHP 數(shù)組的底層實(shí)現(xiàn)是散列表（也叫 hashTable )，散列表是根據(jù)鍵（Key）直接訪問(wèn)內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)，它的key - value 之間存在一個(gè)映射函數(shù)，可以根據(jù) key 通過(guò)映射函數(shù)得到的散列值直接索引到對(duì)應(yīng)的 value 值，無(wú)需通過(guò)關(guān)鍵字比較，在理想情況下，不考慮散列沖突，散列表的查找效率是非常高的，時(shí)間復(fù)雜度是 O(1)。

從源碼中我們可以看到 zend_array 的結(jié)構(gòu)如下：

typedef struct _zend_array zend_array;
typedef struct _zend_array hashTable;

struct _zend_array {
 zend_refcounted_h gc;
 union {
 struct {
 ZEND_ENDIAN_LOHI_4(
  zend_uchar flags,
  zend_uchar nApplyCount,
  zend_uchar nIteratorsCount,
  zend_uchar reserve)
 } v;
 uint32_t flags;
 } u;
 uint32_t nTableMask; // 哈希值計(jì)算掩碼，等于nTableSize的負(fù)值(nTableMask = -nTableSize)
 Bucket *arData; // 存儲(chǔ)元素?cái)?shù)組，指向第一個(gè)Bucket
 uint32_t nNumUsed; // 已用Bucket數(shù)（含失效的 Bucket）
 uint32_t nNumOfElements; // 哈希表有效元素?cái)?shù)
 uint32_t nTableSize; // 哈希表總大小，為2的n次方（包括無(wú)效的元素）
 uint32_t nInternalPointer; // 內(nèi)部指針，用于遍歷
 zend_long nNextFreeElement; // 下一個(gè)可用的數(shù)值索引,如:arr[] = 1;arr["a"] = 2;arr[] = 3; 則nNextFreeElement = 2;
 dtor_func_t pDestructor;
};

該結(jié)構(gòu)中的 Bucket 即儲(chǔ)存元素的數(shù)組，arData 指向數(shù)組的起始位置，使用映射函數(shù)對(duì) key 值進(jìn)行映射后可以得到偏移值，通過(guò)內(nèi)存起始位置 + 偏移值即可在散列表中進(jìn)行尋址操作。

Bucket 的數(shù)據(jù)結(jié)構(gòu)如下：

typedef struct _Bucket {
 zval val; // 存儲(chǔ)的具體 value，這里是一個(gè) zval，而不是一個(gè)指針
 zend_ulong h; // 數(shù)字 key 或字符串 key 的哈希值。用于查找時(shí) key 的比較 
 zend_string *key; // 當(dāng) key 值為字符串時(shí)，指向該字符串對(duì)應(yīng)的 zend_string（使用數(shù)字索引時(shí)該值為 NULL），用于查找時(shí) key 的比較
} Bucket;

到這里有個(gè)問(wèn)題出現(xiàn)了：存儲(chǔ)在散列表里的元素是無(wú)序的，PHP 數(shù)組如何做到按順序讀取的呢？

答案是中間映射表，為了實(shí)現(xiàn)散列表的有序性，PHP 為其增加了一張中間映射表，該表是一個(gè)大小與 Bucket 相同的數(shù)組，數(shù)組中儲(chǔ)存整形數(shù)據(jù)，用于保存元素實(shí)際儲(chǔ)存的 Value 在 Bucekt 中的下標(biāo)。Bucekt 中的數(shù)據(jù)是有序的，而中間映射表中的數(shù)據(jù)是無(wú)序的。

而通過(guò)映射函數(shù)映射后的散列值要在中間映射表的區(qū)間內(nèi)，這就對(duì)映射函數(shù)提出了要求。

映射函數(shù)

PHP7 數(shù)組采用的映射方式：

nIndex = h | ht->nTableMask;

將 key 經(jīng)過(guò) time33 算法生成的哈希值 h 和 nTableMask 進(jìn)行或運(yùn)算即可得出映射表的下標(biāo)，其中 nTableMask 數(shù)值為 nTableSize 的負(fù)數(shù)。并且由于 nTableSize 的值為 2 的冪次方，所以 nTableMask 二進(jìn)制位右側(cè)全部為 0，保證了 h | ht->nTableMask 的取值范圍會(huì)在 [-nTableSize, -1] 之間，正好在映射表的下標(biāo)范圍內(nèi)。另外，用按位或運(yùn)算的方法和其他方法如取余的方法相比運(yùn)算速度較高，這個(gè)映射函數(shù)可以說(shuō)設(shè)計(jì)的非常巧妙了。

散列（哈希）沖突

不同鍵名的通過(guò)映射函數(shù)計(jì)算得到的散列值有可能相同，此時(shí)便發(fā)生了散列沖突。

對(duì)于散列沖突有以下 4 種常用方法：

1.將散列值放到相鄰的最近地址里

2.換個(gè)散列函數(shù)重新計(jì)算散列值

3.將沖突的散列值統(tǒng)一放到另一個(gè)地方

4.在沖突位置構(gòu)造一個(gè)單向鏈表，將散列值相同的元素放到相同槽位對(duì)應(yīng)的鏈表中。這個(gè)方法叫鏈地址法，PHP 數(shù)組就是采用這個(gè)方法解決散列沖突的問(wèn)題。

其具體實(shí)現(xiàn)是：將沖突的 Bucket 串成鏈表，這樣中間映射表映射出的就不是某一個(gè)元素，而是一個(gè) Bucket 鏈表，通過(guò)散列函數(shù)定位到對(duì)應(yīng)的 Bucket 鏈表時(shí)，需要遍歷鏈表，逐個(gè)對(duì)比 Key 值，繼而找到目標(biāo)元素。而每個(gè) Bucket 之間的鏈接則是將原 value 的下標(biāo)保存到新 value 的 zval.u2.next 里，新 value 放在當(dāng)前位置上，從而形成一個(gè)單向鏈表。

舉個(gè)例子：

當(dāng)我們?cè)L問(wèn) $arr['key'] 的過(guò)程中，假設(shè)首先通過(guò)散列運(yùn)算得出映射表下標(biāo)為 -2 ，然后訪問(wèn)映射表發(fā)現(xiàn)其內(nèi)容指向 arData 數(shù)組下標(biāo)為 1 的元素。此時(shí)我們將該元素的 key 和要訪問(wèn)的鍵名相比較，發(fā)現(xiàn)兩者并不相等，則該元素并非我們所想訪問(wèn)的元素，而元素的 zval.u2.next 保存的值正是另一個(gè)具有相同散列值的元素對(duì)應(yīng) arData 數(shù)組的下標(biāo)，所以我們可以不斷通過(guò) zval.u2.next 的值遍歷直到找到鍵名相同的元素。

擴(kuò)容

PHP 的數(shù)組在底層實(shí)現(xiàn)了自動(dòng)擴(kuò)容機(jī)制，當(dāng)插入一個(gè)元素且沒(méi)有空閑空間時(shí)，就會(huì)觸發(fā)自動(dòng)擴(kuò)容機(jī)制，擴(kuò)容后再執(zhí)行插入。

擴(kuò)容的過(guò)程為：

如果已刪除元素所占比例達(dá)到閾值，則會(huì)移除已被邏輯刪除的 Bucket，然后將后面的 Bucket 向前補(bǔ)上空缺的 Bucket，因?yàn)?Bucket 的下標(biāo)發(fā)生了變動(dòng)，所以還需要更改每個(gè)元素在中間映射表中儲(chǔ)存的實(shí)際下標(biāo)值。

如果未達(dá)到閾值，PHP 則會(huì)申請(qǐng)一個(gè)大小是原數(shù)組兩倍的新數(shù)組，并將舊數(shù)組中的數(shù)據(jù)復(fù)制到新數(shù)組中，因?yàn)閿?shù)組長(zhǎng)度發(fā)生了改變，所以 key-value 的映射關(guān)系需要重新計(jì)算，這個(gè)步驟為重建索引。

重建散列表

在刪除某一個(gè)數(shù)組元素時(shí)，會(huì)先使用標(biāo)志位對(duì)該元素進(jìn)行邏輯刪除，即在刪除 value 時(shí)只是將 value 的 type 設(shè)置為 IS_UNDEF，而不會(huì)立即刪除該元素所在的 Bucket，因?yàn)槿绻看蝿h除元素立刻刪除 Bucket 的話，每次都需要進(jìn)行排列操作，會(huì)造成不必要的性能開(kāi)銷(xiāo)。

所以，當(dāng)刪除元素達(dá)到一定數(shù)量或擴(kuò)容后都需要重建散列表，即移除被標(biāo)記為刪除的 value。因?yàn)?value 在 Bucket 位置移動(dòng)了或哈希數(shù)組 nTableSize 變化了導(dǎo)致 key 與 value 的映射關(guān)系改變，重建過(guò)程就是遍歷 Bucket 數(shù)組中的 value，然后重新計(jì)算映射值更新到散列表。

關(guān)于 PHP7 的數(shù)組底層實(shí)現(xiàn)就總結(jié)這么些了，因?yàn)樗接邢抟矡o(wú)法研究的十分詳盡清楚，如果有疑問(wèn)或者不足之處歡迎提出~~

參考資料

《PHP7 的底層設(shè)計(jì)與源碼實(shí)現(xiàn)》

php7-internal

總結(jié)

聲明：本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com