建站
咨詢
售后
建站咨詢
新聞中心
本篇文章為大家展示了在PHP7項目中數(shù)組的底層實現(xiàn)，內(nèi)容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細介紹希望你能有所收獲。
成都創(chuàng)新互聯(lián)是一家專業(yè)提供宜秀企業(yè)網(wǎng)站建設(shè),專注與成都網(wǎng)站設(shè)計、成都做網(wǎng)站、成都h5網(wǎng)站建設(shè)、小程序制作等業(yè)務(wù)。10年已為宜秀眾多企業(yè)、政府機構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)絡(luò)公司優(yōu)惠進行中。PHP 數(shù)組具有的特性
PHP 的數(shù)組是一種非常強大靈活的數(shù)據(jù)類型，在講它的底層實現(xiàn)之前，先看一下 PHP 的數(shù)組都具有哪些特性。
可以使用數(shù)字或字符串作為數(shù)組健值
$arr = [1 => 'ok', 'one' => 'hello'];
可按順序讀取數(shù)組
foreach($arr as $key => $value){
echo $arr[$key];
}可隨機讀取數(shù)組中的元素
$arr = [1 => 'ok', 'one' => 'hello', 'a' => 'world']; echo $arr['one']; echo current($arr);
數(shù)組的長度是可變的
$arr = [1, 2, 3]; $arr[] = 4; array_push($arr, 5);
正是基于這些特性，我們可以使用 PHP 中的數(shù)組輕易的實現(xiàn)集合、棧、列表、字典等多種數(shù)據(jù)結(jié)構(gòu)。那么這些特性在底層是如何實現(xiàn)的呢？ 這就得從數(shù)據(jù)結(jié)構(gòu)說起了。
數(shù)據(jù)結(jié)構(gòu)
PHP 中的數(shù)組實際上是一個有序映射。映射是一種把 values 關(guān)聯(lián)到 keys 的類型。
PHP 數(shù)組的底層實現(xiàn)是散列表（也叫 hashTable )，散列表是根據(jù)鍵（Key）直接訪問內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu)，它的key - value 之間存在一個映射函數(shù)，可以根據(jù) key 通過映射函數(shù)得到的散列值直接索引到對應(yīng)的 value 值，無需通過關(guān)鍵字比較，在理想情況下，不考慮散列沖突，散列表的查找效率是非常高的，時間復(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; // 哈希值計算掩碼，等于nTableSize的負值(nTableMask = -nTableSize)
Bucket *arData; // 存儲元素數(shù)組，指向第一個Bucket
uint32_t nNumUsed; // 已用Bucket數(shù)（含失效的 Bucket）
uint32_t nNumOfElements; // 哈希表有效元素數(shù)
uint32_t nTableSize; // 哈希表總大小，為2的n次方（包括無效的元素）
uint32_t nInternalPointer; // 內(nèi)部指針，用于遍歷
zend_long nNextFreeElement; // 下一個可用的數(shù)值索引,如:arr[] = 1;arr["a"] = 2;arr[] = 3; 則nNextFreeElement = 2;
dtor_func_t pDestructor;
};該結(jié)構(gòu)中的 Bucket 即儲存元素的數(shù)組，arData 指向數(shù)組的起始位置，使用映射函數(shù)對 key 值進行映射后可以得到偏移值，通過內(nèi)存起始位置 + 偏移值即可在散列表中進行尋址操作。
Bucket 的數(shù)據(jù)結(jié)構(gòu)如下：
typedef struct _Bucket {
zval val; // 存儲的具體 value，這里是一個 zval，而不是一個指針
zend_ulong h; // 數(shù)字 key 或字符串 key 的哈希值。用于查找時 key 的比較
zend_string *key; // 當(dāng) key 值為字符串時，指向該字符串對應(yīng)的 zend_string（使用數(shù)字索引時該值為 NULL），用于查找時 key 的比較
} Bucket;到這里有個問題出現(xiàn)了：存儲在散列表里的元素是無序的，PHP 數(shù)組如何做到按順序讀取的呢？
答案是中間映射表，為了實現(xiàn)散列表的有序性，PHP 為其增加了一張中間映射表，該表是一個大小與 Bucket 相同的數(shù)組，數(shù)組中儲存整形數(shù)據(jù)，用于保存元素實際儲存的 Value 在 Bucekt 中的下標(biāo)。Bucekt 中的數(shù)據(jù)是有序的，而中間映射表中的數(shù)據(jù)是無序的。
而通過映射函數(shù)映射后的散列值要在中間映射表的區(qū)間內(nèi)，這就對映射函數(shù)提出了要求。
映射函數(shù)
PHP7 數(shù)組采用的映射方式：
nIndex = h | ht->nTableMask;
將 key 經(jīng)過 time33 算法生成的哈希值 h 和 nTableMask 進行或運算即可得出映射表的下標(biāo)，其中 nTableMask 數(shù)值為 nTableSize 的負數(shù)。并且由于 nTableSize 的值為 2 的冪次方，所以 nTableMask 二進制位右側(cè)全部為 0，保證了 h | ht->nTableMask 的取值范圍會在 [-nTableSize, -1] 之間，正好在映射表的下標(biāo)范圍內(nèi)。另外，用按位或運算的方法和其他方法如取余的方法相比運算速度較高，這個映射函數(shù)可以說設(shè)計的非常巧妙了。
散列（哈希）沖突
不同鍵名的通過映射函數(shù)計算得到的散列值有可能相同，此時便發(fā)生了散列沖突。
對于散列沖突有以下 4 種常用方法：
1.將散列值放到相鄰的最近地址里
2.換個散列函數(shù)重新計算散列值
3.將沖突的散列值統(tǒng)一放到另一個地方
4.在沖突位置構(gòu)造一個單向鏈表，將散列值相同的元素放到相同槽位對應(yīng)的鏈表中。這個方法叫鏈地址法，PHP 數(shù)組就是采用這個方法解決散列沖突的問題。
其具體實現(xiàn)是：將沖突的 Bucket 串成鏈表，這樣中間映射表映射出的就不是某一個元素，而是一個 Bucket 鏈表，通過散列函數(shù)定位到對應(yīng)的 Bucket 鏈表時，需要遍歷鏈表，逐個對比 Key 值，繼而找到目標(biāo)元素。而每個 Bucket 之間的鏈接則是將原 value 的下標(biāo)保存到新 value 的 zval.u2.next 里，新 value 放在當(dāng)前位置上，從而形成一個單向鏈表。
舉個例子：
當(dāng)我們訪問 $arr['key'] 的過程中，假設(shè)首先通過散列運算得出映射表下標(biāo)為 -2 ，然后訪問映射表發(fā)現(xiàn)其內(nèi)容指向 arData 數(shù)組下標(biāo)為 1 的元素。此時我們將該元素的 key 和要訪問的鍵名相比較，發(fā)現(xiàn)兩者并不相等，則該元素并非我們所想訪問的元素，而元素的 zval.u2.next 保存的值正是另一個具有相同散列值的元素對應(yīng) arData 數(shù)組的下標(biāo)，所以我們可以不斷通過 zval.u2.next 的值遍歷直到找到鍵名相同的元素。
擴容
PHP 的數(shù)組在底層實現(xiàn)了自動擴容機制，當(dāng)插入一個元素且沒有空閑空間時，就會觸發(fā)自動擴容機制，擴容后再執(zhí)行插入。
擴容的過程為：
如果已刪除元素所占比例達到閾值，則會移除已被邏輯刪除的 Bucket，然后將后面的 Bucket 向前補上空缺的 Bucket，因為 Bucket 的下標(biāo)發(fā)生了變動，所以還需要更改每個元素在中間映射表中儲存的實際下標(biāo)值。
如果未達到閾值，PHP 則會申請一個大小是原數(shù)組兩倍的新數(shù)組，并將舊數(shù)組中的數(shù)據(jù)復(fù)制到新數(shù)組中，因為數(shù)組長度發(fā)生了改變，所以 key-value 的映射關(guān)系需要重新計算，這個步驟為重建索引。
重建散列表
在刪除某一個數(shù)組元素時，會先使用標(biāo)志位對該元素進行邏輯刪除，即在刪除 value 時只是將 value 的 type 設(shè)置為 IS_UNDEF，而不會立即刪除該元素所在的 Bucket，因為如果每次刪除元素立刻刪除 Bucket 的話，每次都需要進行排列操作，會造成不必要的性能開銷。
所以，當(dāng)刪除元素達到一定數(shù)量或擴容后都需要重建散列表，即移除被標(biāo)記為刪除的 value。因為 value 在 Bucket 位置移動了或哈希數(shù)組 nTableSize 變化了導(dǎo)致 key 與 value 的映射關(guān)系改變，重建過程就是遍歷 Bucket 數(shù)組中的 value，然后重新計算映射值更新到散列表。
上述內(nèi)容就是在PHP7項目中數(shù)組的底層實現(xiàn)，你們學(xué)到知識或技能了嗎？如果還想學(xué)到更多技能或者豐富自己的知識儲備，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。
當(dāng)前題目：在PHP7項目中數(shù)組的底層實現(xiàn)-創(chuàng)新互聯(lián)
網(wǎng)站路徑：http://www.dlmjj.cn/article/ccihcj.html
