php數組實作原理

陣列是PHPer最常用的資料型，同時php容易上手也得益於其強大的數組，但是數組在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的變數容器。 #########雜湊表內部結構關係圖###################　　從上圖我們可以看出，Bucket在存放資料的時候，如果存在雜湊衝突，則將多個關鍵字對應到鍊錶中，由此組成了雙向鍊錶#############總結############　　今天，我們以數組作為切入點，簡單了解了下基本的資料結構：哈希表和鍊錶；並且了解了數組的底層實現，即哈希表雙向鍊錶。其實哈希表作為php中最重要的資料結構，用處很廣。變數的符號表，函數列表等都是用哈希表來儲存的###

以上是php數組實作原理的詳細內容。更多資訊請關注PHP中文網其他相關文章！