本文轉載自微信公眾號「 寫PHP的老王」，轉載本文請聯系 寫PHP的老王公眾號。

線性表，全名為線性存儲結構。使用線性表存儲數據的方式可以這樣理解，即“把所有數據用一根線串起來，再存儲到物理空間中”。最簡單的線性表就是數組了。雖然PHP的數組本身不是由基礎的數據結構構成，但是其內部實現方式應用到了大部分的線性表數據結構。今天，借著學習線性表數據結構的機會，重新回顧PHP數組的內部實現原理。

PHP數組的內部實現

數組是PHP中很強大且非常重要的數據類型。它既支持單純的數字索引數組又支持鍵值對數組，其中鍵值對數組類似于 java的 HashMap。由于采用了哈希表實現能夠保證基本查找時間復雜度為 O(1)，而且還能夠保證數據遍歷的順序。

首先看看PHP在內核C語言的數據結構長什么樣

看一下在php代碼中，給數組插入一個元素會發生什么

$arr = ['name'=>'admin']; 

1.內核首先會創建一個_zend_array數據對象。初始化數組的大小為HT_MIN_SIZE，PHP中定義了HT_MIN_SIZE為8;所以當數組元素小于8的時候，插入數據并不會進行數組擴容。

2.使用Times 33hash算法，將 name轉換成一個長整形的數。

3.在arData[nNumUsed++]中保存 Bucket 數據中 key是數組的鍵名，h中保存key的hash之后的整數(負數)，val的u2.next 保存 arData[h]的地址。將轉換表存儲以 arData 起始指針為起點做鏡面映射存儲。這樣，我們不需要額外的空間存儲，在分配 arData 空間的同時也分配了轉換表。

查找數組的時候，根據鍵名直接hash之后，可以直接定位到實際保存鍵值的Bucket，遍歷的時候，因為arData本身是有序的C數組，遍歷數組之后可以獲取到保存鍵值的Bucket。因此PHP的數組既能夠以O(1)的復雜度查詢到數組，又能夠順序的遍歷數組元素。

對應源碼實現邏輯的主要核心代碼如下：

上面的過程省略了hash沖突的情況。但是即使是從上面簡單的版本中也可以發現PHP數組的實現運用了很多的數據結構知識。

Bucket *arData;是一個C語言數組，對應數據結構中的有序表。Bucket之間，通過val的u2.next又構成了一個鏈表結構。

同時，PHP在處理hash沖突情況的時候，是將所有的沖突的鍵名數據退化成一個鏈表。而這種處理方式，是絕大部分hash處理的方式。

順序表

順序表的定義如下:

所謂順序表就是順序存儲的線性表。順序存儲是用一組地址連續的存儲單元依次存放線性表中各個元素的存儲結構。

上面PHP核心代碼中 arData就是一個順序表。

序表的特點：

1. 在線性表中邏輯上相鄰的數據元素，在物理存儲上也是相鄰的。

2. 存儲密度高，但要預先分配“足夠應用”的存儲空間，這可能會造成存儲空間的浪費。

3. 便于隨機存儲。只要確定了存儲線性表的起始位置，線性表中任一數據元素都可隨機存取，所以線性表的順序存儲結構是一種隨機存取的存儲結構。

4. 不便于插入和刪除操作，這是因為在順序表上進行的插入和刪除操作會引起大量數據元素的移動。

順序表存在的問題:

1. 物理上相鄰存儲，不便于內存利用。例如一個容量為10的數組，需要內存為10字節，但是目前沒有連續10個字節空余的內存空間，但是有很多不連續的小于10字節的內存空間，這樣也沒辦法分配;

2. 順序表的容量很難確定。對于C語言而言，定義一個數組是需要指定數組大小的。這個大小就是為了方便底層用于申請連續內存空間。PHP源碼中在初始化一個空數組的時候，也會先創建一個長度為16的arData數組，在需要擴容的時候在進行數組擴容。

3. 插入元素不方便，需要移動整個順序表元素

鏈表

鏈表的數據結構，是針對順序表的問題而提出的。鏈表是一種物理存儲結構上非連續，非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。在PHP的數組的源碼中，每個Bucket就是鏈表中的一個節點。通過Bucket.u2.next指向下一個節點(雖然本身是為了實現hash查找)。

根據鏈表的鏈接方式，分為單鏈表，雙鏈表。

單鏈表的每一個節點中只有指向下一個結點的指針，不能進行回溯，適用于節點的增加和刪除。

雙鏈表的每一個節點中既有指向下一個結點的指針，也有指向上一個結點的指針，可以快速的找到當前節點的前一個節點，適用于需要雙向查找節點值的情況

鏈表的優點：

插入和刪除的效率高，只需要改變指針的指向就可以進行插入和刪除。

內存利用率高，不會浪費內存，可以使用內存中細小的不連續的空間，只有在需要的時候才去創建空間。大小不固定，拓展很靈活。

總結

本文以PHP7.4的源碼為基礎，介紹了PHP內部是如何實現數組的有序同時保證鍵值查找的O(1)的查詢速度。從PHP數組的實現出發，介紹了線性表中有序表，鏈表的基本內容以及各自的特點。皮毛內容，希望對大家有所幫助。

[1] PHP7 哈希表實現原理 : http://www.sohu.com/a/119748257_464029

[2] 鏈表: https://blog.csdn.net/Shuffle_Ts/article/details/95055467

[3] 數據結構(C語言版)系列一 線性表: https://www.cnblogs.com/wwf828/p/9503821.html