• <legend id="m0ego"></legend>
  • <td id="m0ego"></td>
  • PHP7數組的底層實現示例

    文章TAG:數組 PHP7
    時間:2019-08-25來源/作者:JeffreyC 編輯:源碼庫 文章熱度:

    PHP 數組具有的特性

    PHP 的數組是一種非常強大靈活的數據類型,在講它的底層實現之前,先看一下 PHP 的數組都具有哪些特性。

    可以使用數字或字符串作為數組健值

    $arr = [1 => 'ok', 'one' => 'hello'];

    可按順序讀取數組

    foreach($arr as $key => $value){
     echo $arr[$key];
    }

    可隨機讀取數組中的元素

    $arr = [1 => 'ok', 'one' => 'hello', 'a' => 'world'];
    
    echo $arr['one'];
    
    echo current($arr);

    數組的長度是可變的

    $arr = [1, 2, 3];
    
    $arr[] = 4;
    
    array_push($arr, 5);

    正是基于這些特性,我們可以使用 PHP 中的數組輕易的實現集合、棧、列表、字典等多種數據結構。那么這些特性在底層是如何實現的呢? 這就得從數據結構說起了。

    數據結構

    PHP 中的數組實際上是一個有序映射。映射是一種把 values 關聯到 keys 的類型。

    PHP 數組的底層實現是散列表(也叫 hashTable ),散列表是根據鍵(Key)直接訪問內存存儲位置的數據結構,它的key - value 之間存在一個映射函數,可以根據 key 通過映射函數得到的散列值直接索引到對應的 value 值,無需通過關鍵字比較,在理想情況下,不考慮散列沖突,散列表的查找效率是非常高的,時間復雜度是 O(1)。

    從源碼中我們可以看到 zend_array 的結構如下:

    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;   // 存儲元素數組,指向第一個Bucket
      uint32_t     nNumUsed;  // 已用Bucket數(含失效的 Bucket)
      uint32_t     nNumOfElements; // 哈希表有效元素數
      uint32_t     nTableSize;   // 哈希表總大小,為2的n次方(包括無效的元素)
      uint32_t     nInternalPointer; // 內部指針,用于遍歷
      zend_long     nNextFreeElement; // 下一個可用的數值索引,如:arr[] = 1;arr["a"] = 2;arr[] = 3; 則nNextFreeElement = 2;
      dtor_func_t    pDestructor;
    };

    該結構中的 Bucket 即儲存元素的數組,arData 指向數組的起始位置,使用映射函數對 key 值進行映射后可以得到偏移值,通過內存起始位置 + 偏移值即可在散列表中進行尋址操作。

    Bucket 的數據結構如下:

    typedef struct _Bucket {
      zval       val; // 存儲的具體 value,這里是一個 zval,而不是一個指針
      zend_ulong    h;  // 數字 key 或字符串 key 的哈希值。用于查找時 key 的比較  
      zend_string   *key; // 當 key 值為字符串時,指向該字符串對應的 zend_string(使用數字索引時該值為 NULL),用于查找時 key 的比較
    } Bucket;

    到這里有個問題出現了:存儲在散列表里的元素是無序的,PHP 數組如何做到按順序讀取的呢?

    答案是中間映射表,為了實現散列表的有序性,PHP 為其增加了一張中間映射表,該表是一個大小與 Bucket 相同的數組,數組中儲存整形數據,用于保存元素實際儲存的 Value 在 Bucekt 中的下標。Bucekt 中的數據是有序的,而中間映射表中的數據是無序的。

    PHP7,數組

    而通過映射函數映射后的散列值要在中間映射表的區間內,這就對映射函數提出了要求。

    映射函數

    PHP7 數組采用的映射方式:

    nIndex = h | ht->nTableMask;

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

    散列(哈希)沖突

    不同鍵名的通過映射函數計算得到的散列值有可能相同,此時便發生了散列沖突。

    對于散列沖突有以下 4 種常用方法:

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

    2.換個散列函數重新計算散列值

    3.將沖突的散列值統一放到另一個地方

    4.在沖突位置構造一個單向鏈表,將散列值相同的元素放到相同槽位對應的鏈表中。這個方法叫鏈地址法,PHP 數組就是采用這個方法解決散列沖突的問題。

    其具體實現是:將沖突的 Bucket 串成鏈表,這樣中間映射表映射出的就不是某一個元素,而是一個 Bucket 鏈表,通過散列函數定位到對應的 Bucket 鏈表時,需要遍歷鏈表,逐個對比 Key 值,繼而找到目標元素。而每個 Bucket 之間的鏈接則是將原 value 的下標保存到新 value 的 zval.u2.next 里,新 value 放在當前位置上,從而形成一個單向鏈表。

    舉個例子:

    當我們訪問 $arr['key'] 的過程中,假設首先通過散列運算得出映射表下標為 -2 ,然后訪問映射表發現其內容指向 arData 數組下標為 1 的元素。此時我們將該元素的 key 和要訪問的鍵名相比較,發現兩者并不相等,則該元素并非我們所想訪問的元素,而元素的 zval.u2.next 保存的值正是另一個具有相同散列值的元素對應 arData 數組的下標,所以我們可以不斷通過 zval.u2.next 的值遍歷直到找到鍵名相同的元素。

    擴容

    PHP 的數組在底層實現了自動擴容機制,當插入一個元素且沒有空閑空間時,就會觸發自動擴容機制,擴容后再執行插入。

    擴容的過程為:

    如果已刪除元素所占比例達到閾值,則會移除已被邏輯刪除的 Bucket,然后將后面的 Bucket 向前補上空缺的 Bucket,因為 Bucket 的下標發生了變動,所以還需要更改每個元素在中間映射表中儲存的實際下標值。

    如果未達到閾值,PHP 則會申請一個大小是原數組兩倍的新數組,并將舊數組中的數據復制到新數組中,因為數組長度發生了改變,所以 key-value 的映射關系需要重新計算,這個步驟為重建索引。

    重建散列表

    在刪除某一個數組元素時,會先使用標志位對該元素進行邏輯刪除,即在刪除 value 時只是將 value 的 type 設置為 IS_UNDEF,而不會立即刪除該元素所在的 Bucket,因為如果每次刪除元素立刻刪除 Bucket 的話,每次都需要進行排列操作,會造成不必要的性能開銷。

    所以,當刪除元素達到一定數量或擴容后都需要重建散列表,即移除被標記為刪除的 value。因為 value 在 Bucket 位置移動了或哈希數組 nTableSize 變化了導致 key 與 value 的映射關系改變,重建過程就是遍歷 Bucket 數組中的 value,然后重新計算映射值更新到散列表。

    關于 PHP7 的數組底層實現就總結這么些了,因為水平有限也無法研究的十分詳盡清楚,如果有疑問或者不足之處歡迎提出~~

    參考資料

    《PHP7 的底層設計與源碼實現》

    php7-internal

    總結

    以上就是這篇文章的全部內容了,希望本文的內容對大家的學習或者工作具有一定的參考學習價值,謝謝大家對ASPKU源碼庫的支持。


    注:相關教程知識閱讀請移步到PHP教程頻道。
    相關PHP教程
    熱門標簽

    PHP教程Rss訂閱PHP教程搜索