解析PHP8底層內核源碼-數組（三）

上文已經全文剖析了PHP中陣列的基本結構實作與索引的組成原理

#依賴_Bucket 和_zend_array 兩個結構體

透過雜湊函數實作o(1）的複雜度

可是bucket之前還有一個索引數組 我當時在理解這個索引數組的時候走了不少坑

下圖為 $c =array('x'=>1,'y'=>2,'z'=>3,'a '=>0); 中數組c的bucket結構

#上文已經說如果是packed_array的時候索引數組一直是2 也不會發揮作用

因為如果是packed  key直接是null 也不需要去計算hash值 這個索引數組只是用於快速定位h值所用

typedef struct _Bucket {
zval              val;   //数组的值 ( 复习下 zval只有16个字节)
zend_ulong         h;     // key的 h  值
zend_string      *key;      //当数组为 hash_array时候 会用到 也就是 key的值  
} Bucket;

當為packedarray的時候也不要被val影響了你的學習思路 h值就等於數組的位置的下標(數組都是從0開始，所以下標也從0開始)。例如上文提到的
$b =array(1=>'a',3=>'b',5=>'c');     其中數組b 一樣也是packed_array  結構如下

因為陣列b沒有定義第0個陣列的值所以是無效的  其中$b[1]內容是'a'這裡我圖上是直接標示了val=a(zval) 其實 是16位元組的zval中類型為string的zend_string  這裡面又套了之前學到的gc 等所有PHP核心原始碼裡存在著很多無限套娃方便你溫故知新。

返回再說$c =array('x'=>1,'y'=>2,'z'=>3,'a'=>0);

結構如下

這個h值很大 是用key 透過time33計算得來的雜湊值我也不知道為什麼叫雜湊值我覺得就是透過time33計算得來的h值 然後形成散列表

散列表主要由兩部分組成:儲存元素陣列、雜湊函數。一個簡單的雜湊函數可以採用餘數的方式，例如散列表大小為8 那麼在散列表初始化數組的時候就分配8個元素大小的空間，跟進key的hash code 除以8 得到的值就是該元素在數組中的下標。這樣就可以透過key映射到儲存陣列中的具體位置

#但是直接用上面的方式實作陣列會有一個問題:元素在數組中位置是隨機的它是無序的

PHP中的數組是有序的所以它在散列函數與元素數組之間加了一層索引表這個索引表也是一個數組。大小與儲存元素的陣列相同。但是它儲存的元素類型永遠都是整數型，用於保存元素數組在實際儲存的數組中的下標：元素按照先後順序依次插入實際存儲數組中，然後將其數組下標按照散列函數計算出的位置儲存在新加的索引標中。

第一步計算4 然後取索引表中找到-4  因為這是第0個陣列所以把索引表中第-4個陣列裡面的值設定為0   然後把真正的陣列表中第0個元素設定為真正賦值的zval

散列表中不同元素的key 可能最後計算得到的雜湊值是一樣的也就是指向同一個索引表中的下標這個時候就會發生hash衝突 。因為索引表只能存一個元素  PHP為了實現hash衝突 採用了拉鍊法  就是把值用鍊錶拉起來  。可參考下圖《PHP7 核心剖析-秦朋》

#正常狀況val.u2.next 的值為-1 也就是初始值一旦出現hash衝突那麼這裡的值就會指向衝突之前的陣列的真實位置。

▏本文經原作者PHP崔雪峰同意，發佈在php中文網，原文網址：https://zhuanlan.zhihu.com/p/360952022