本文轉(zhuǎn)載自微信公眾號「 寫PHP的老王」，轉(zhuǎn)載本文請聯(lián)系 寫PHP的老王公眾號。

線性表，全名為線性存儲結(jié)構(gòu)。使用線性表存儲數(shù)據(jù)的方式可以這樣理解，即“把所有數(shù)據(jù)用一根線串起來，再存儲到物理空間中”。最簡單的線性表就是數(shù)組了。雖然PHP的數(shù)組本身不是由基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)構(gòu)成，但是其內(nèi)部實現(xiàn)方式應(yīng)用到了大部分的線性表數(shù)據(jù)結(jié)構(gòu)。今天，借著學(xué)習(xí)線性表數(shù)據(jù)結(jié)構(gòu)的機會，重新回顧PHP數(shù)組的內(nèi)部實現(xiàn)原理。

PHP數(shù)組的內(nèi)部實現(xiàn)

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

首先看看PHP在內(nèi)核C語言的數(shù)據(jù)結(jié)構(gòu)長什么樣

看一下在php代碼中，給數(shù)組插入一個元素會發(fā)生什么

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

1.內(nèi)核首先會創(chuàng)建一個_zend_array數(shù)據(jù)對象。初始化數(shù)組的大小為HT_MIN_SIZE，PHP中定義了HT_MIN_SIZE為8;所以當(dāng)數(shù)組元素小于8的時候，插入數(shù)據(jù)并不會進(jìn)行數(shù)組擴容。

2.使用Times 33hash算法，將 name轉(zhuǎn)換成一個長整形的數(shù)。

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

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

對應(yīng)源碼實現(xiàn)邏輯的主要核心代碼如下：

上面的過程省略了hash沖突的情況。但是即使是從上面簡單的版本中也可以發(fā)現(xiàn)PHP數(shù)組的實現(xiàn)運用了很多的數(shù)據(jù)結(jié)構(gòu)知識。

Bucket *arData;是一個C語言數(shù)組，對應(yīng)數(shù)據(jù)結(jié)構(gòu)中的有序表。Bucket之間，通過val的u2.next又構(gòu)成了一個鏈表結(jié)構(gòu)。

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

順序表

順序表的定義如下:

所謂順序表就是順序存儲的線性表。順序存儲是用一組地址連續(xù)的存儲單元依次存放線性表中各個元素的存儲結(jié)構(gòu)。

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

序表的特點：

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

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

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

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

順序表存在的問題:

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

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

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

鏈表

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

根據(jù)鏈表的鏈接方式，分為單鏈表，雙鏈表。

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

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

鏈表的優(yōu)點：

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

內(nèi)存利用率高，不會浪費內(nèi)存，可以使用內(nèi)存中細(xì)小的不連續(xù)的空間，只有在需要的時候才去創(chuàng)建空間。大小不固定，拓展很靈活。

總結(jié)

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

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

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

[3] 數(shù)據(jù)結(jié)構(gòu)(C語言版)系列一 線性表: https://www.cnblogs.com/wwf828/p/9503821.html