php底層原理之數組實現

HackerShell 發布于2019-07-01 12:38 / 3496人閱讀

摘要：數組是最常用的數據類型，同時容易上手也得益于其強大的數組，但是數組在中是如何實現的呢首先，我們還是先了解下相關的數據結構，為下面的內容打好基礎哈希表哈希表，顧名思義，即將不同的關鍵字映射到不同單元的一種數據結構。

數組是PHPer最常用的數據類型，同時php容易上手也得益于其強大的數組，但是數組在php中是如何實現的呢？

首先，我們還是先了解下相關的數據結構，為下面的內容打好基礎

哈希表

哈希表，顧名思義，即將不同的關鍵字映射到不同單元的一種數據結構。而將不同關鍵字映射到不同單元的方法就叫做哈希函數

理想情況下，經過哈希函數處理，關鍵字和單元是會進行一一對應的；但是如果關鍵字值足夠多的情況下，就容易出現多個關鍵字映射到同一單元的情況，即出現哈希沖突

哈希沖突的解決方案，要么使用鏈接法，要么使用開放尋址法

鏈接法
即當不同的關鍵字映射到同一單元時，在同一單元內使用鏈表來保存這些關鍵字

開放尋址法
即當插入數據時，如果發現關鍵字被映射到的單元存在數據了，說明發生了沖突，就繼續尋找下一個單元，直到找到可用單元為止

而因為開放尋址法方案屬于占用其他關鍵字映射單元的位置，所以后續的關鍵字更容易出現哈希沖突，因此容易出現性能下降

鏈表

既然上面提到了鏈表，這里我們簡單聊一下鏈表的基礎知識。鏈表分為很多種類型，常用的數據結構包括：隊列，棧，雙向鏈表等

鏈表，就是由不同的鏈表節點組成的一種數據結構。鏈表節點一般由元素+指向下一節點的指針組成。而雙向鏈表，顧名思義，則是由指向上一節點的指針+元素+指向下一節點的指針組成

對于數據結構的內容，我們不過多展開，我們之后會有專門的內容去詳細介紹數據結構

php數組

php解決哈希沖突的方式是使用了鏈接法，所以php數組是由哈希表+鏈表實現，準確來說，是由哈希表+雙向鏈表實現

內部結構-哈希表

HashTable結構體主要用來存放哈希表的基本信息

typedef struct _hashtable { 
    uint nTableSize;        // hash Bucket的大小，即哈希表的容量，最小為8，以2x增長。
    uint nTableMask;        // nTableSize-1 ， 索引取值的優化
    uint nNumOfElements;    // hash Bucket中當前存在的元素個數，count()函數會直接返回此值 
    ulong nNextFreeElement; // 下一個可使用的數字鍵值
    Bucket *pInternalPointer;   // 當前遍歷的指針（foreach比for快的原因之一）
    Bucket *pListHead;          // 存儲整個哈希表的頭元素指針
    Bucket *pListTail;          // 存儲整個哈希表的尾元素指針
    Bucket **arBuckets;         // 存儲hash數組
    dtor_func_t pDestructor;    // 在刪除元素時執行的回調函數，用于資源的釋放
    zend_bool persistent;       //指出了Bucket內存分配的方式。如果persisient為TRUE，則使用操作系統本身的內存分配函數為Bucket分配內存，否則使用PHP的內存分配函數。
    unsigned char nApplyCount; // 標記當前hash Bucket被遞歸訪問的次數（防止多次遞歸）
    zend_bool bApplyProtection;// 標記當前hash桶允許不允許多次訪問，不允許時，最多只能遞歸3次
#if ZEND_DEBUG
    int inconsistent;
#endif
} HashTable;

Bucket結構體則用于保存數據的具體內容

typedef struct bucket {
    ulong h;            // 對char *key進行hash后的值，或者是用戶指定的數字索引值
    uint nKeyLength;    // hash關鍵字的長度，如果數組索引為數字，此值為0
    void *pData;        // 指向value，一般是用戶數據的副本，如果是指針數據，則指向pDataPtr
    void *pDataPtr;     // 如果是指針數據，此值會指向真正的value，同時上面pData會指向此值
    struct bucket *pListNext;   // 指向整個哈希表的該單元的下一個元素
    struct bucket *pListLast;   // 指向整個哈希表的該單元的上一個元素
    struct bucket *pNext;       // 指向由于哈希沖突導致存放在同一個單元的鏈表中的下一個元素
    struct bucket *pLast;       // 指向由于哈希沖突導致存放在同一個單元的鏈表中的上一個元素
    // 保存當前值所對于的key字符串，這個字段只能定義在最后，實現變長結構體
    char arKey[1];              
} Bucket;

其中Bucket結構體內有指向用戶數據的pData元素，其實是指向了之前我們介紹的變量zval結構體，這也是為什么當創建數組時，會出現數組元素+1的變量容器。不了解變量底層相關知識的，請查看我之前的文章：

php底層原理之變量（一）
php底層原理之變量（二）

哈希表內部結構關系圖

注：圖片來源于網絡

從上圖我們可以看出，Bucket在存放數據的時候，如果存在哈希沖突，則將多個關鍵字映射到鏈表中，由此組成了雙向鏈表

總結

今天，我們以數組作為切入點，簡單了解了下基本的數據結構：哈希表和鏈表；并且了解了數組的底層實現，即哈希表+雙向鏈表。其實哈希表作為php中最重要的數據結構，用處很廣。變量的符號表，函數列表等都是用哈希表來存儲的，感興趣的同學可以看我之前的文章來了解相關知識

GPU云服務器云服務器 php的數組底層實現 php數組的原理 ECS底層原理 php 數組實現if

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/31143.html

php底層原理之變量（一）

摘要：對于來說，變量有全局變量和局部變量之分那么，他們都是存儲到一個哈希表內了么其實不是的，變量存儲也有作用域的概念。上次跟大家講了垃圾回收機制后，有些小伙伴對底層原理比較感興趣，私信問我了一些關于變量的相關知識，既然大家對變量比較感興趣，那么這次我們來系統的講一下變量的底層原理變量結構首先，我們還是先擺上我們的zval結構體，即php所有變量都會以zval結構體的形式實現 struc...

curlyCheng 2019-07-01 12:35 評論0 收藏0
php底層原理之垃圾回收機制

摘要：總結垃圾回收機制以的引用計數機制為基礎以前只有該機制同時使用根緩沖區機制，當發現有存在循環引用的時，就會把其投入到根緩沖區，當根緩沖區達到配置文件中的指定數量后，就會進行垃圾回收，以此解決循環引用導致的內存泄漏問題開始引入該機制 php垃圾回收機制，對于PHPer來說是一個不陌生但是又不是很熟悉的內容。那么php是怎么實現對不需要的內存進行回收的呢？ php變量的內部存儲結構首先還是...

light 2019-07-01 12:32 評論0 收藏0
PHP小知識點

摘要：那些瑣碎的知識點作者記錄的的很奇特很難記的知識點。易錯知識點整理注意和的區別中和都是輸出的作用，但是兩者之間還是有細微的差別。今天手頭不忙，總結一下，分享過程中掌握的知識點。深入理解 PHP 之：Nginx 與 FPM 的工作機制這篇文章從 Nginx 與 FPM 的工作機制出發，探討配置背后的原理，讓我們真正理解 Nginx 與 PHP 是如何協同工作的。 PHP 那些瑣碎的知識...

hover_lew 2019-06-28 14:35 評論0 收藏0
php底層原理之變量（二）

摘要：但是對于結構體中的和字段我們一直都沒有詳細介紹過，而這兩個字段其實是和變量之間賦值的原理有著密切的關系的。上周我們從底層的角度介紹了php變量從生成->常量賦值->銷毀的完整生命周期（不了解的同學可以翻看一下前面的文章php底層原理之變量（一）），但是我們留了一個思考，不知道大家有答案了沒，變量之間的賦值在底層又是如何實現的呢？變量之間賦值 php變量的zval結構，我們已經介紹了...

bladefury 2019-07-01 12:36 評論0 收藏0
foreach遍歷過程中的奇怪現象（PHP5）

摘要：中基礎中的三大坑，遍歷，引用機制，數組。今天我們在講講中的一些奇怪現象。本文適合有一定基礎的。運行流程共用一個結構體開始遍歷數組，進行判斷，拷貝數組是一個新的結構體，操作的是新的結構體。那么遍歷數組時，全程與原數組無關。 PHP中基礎中的三大坑，foreach遍歷，引用機制&，數組。今天我們在講講foreach中的一些奇怪現象。在講解之前，可以先看看我其他相關的文章，屬于同一個大的...

kgbook 2019-07-01 12:15 評論0 收藏0