本文轉(zhuǎn)載自微信公眾號(hào)「 寫(xiě)PHP的老王」，轉(zhuǎn)載本文請(qǐng)聯(lián)系 寫(xiě)PHP的老王公眾號(hào)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

順序表

順序表的定義如下:

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

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

序表的特點(diǎn)：

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

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

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

4. 不便于插入和刪除操作，這是因?yàn)樵陧樞虮砩线M(jìn)行的插入和刪除操作會(huì)引起大量數(shù)據(jù)元素的移動(dòng)。

順序表存在的問(wèn)題:

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

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

3. 插入元素不方便，需要移動(dòng)整個(gè)順序表元素

鏈表

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

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

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

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

鏈表的優(yōu)點(diǎn)：

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

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

總結(jié)

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

[1] PHP7 哈希表實(shí)現(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語(yǔ)言版)系列一 線性表: https://www.cnblogs.com/wwf828/p/9503821.html