摘要：使用安裝目前不支持使用安裝。這個(gè)會(huì)被注冊(cè)的函數(shù)截獲。使用最大堆實(shí)現(xiàn)。同的使用是一致的，可是是任意的類型，但是必須唯一。優(yōu)點(diǎn)效率和內(nèi)存使用幾乎和一致當(dāng)?shù)拇笮∠陆档阶銐蛐r(shí)，會(huì)自動(dòng)釋放已分配的內(nèi)存。

pecl install ds

brew install homebrew/php/php71-ds

目前PHP7.2不支持使用 brew 安裝。

PHP5.x 的時(shí)代，Array是唯一的表示集合的數(shù)據(jù)類型，在 PHP 中，他既是 List 也是 Map， 他就是一切。

1,"b"=>2,"c"=>3);

這種數(shù)據(jù)類型的確是給開發(fā)者帶來了便捷性，但讓PHPer 會(huì)主鍵的忽略掉數(shù)據(jù)結(jié)構(gòu)帶來的好處，特別是在學(xué)習(xí)其他的語言時(shí)，給PHPer 帶來困擾。

在 PHP 升級(jí)到7后，Array也同時(shí)得到了優(yōu)化，但是他的結(jié)構(gòu)并沒有發(fā)生變化， “optimised for everything; optimised for nothing” with room for improvement。那如果我們可以通過引入更便利的數(shù)據(jù)結(jié)構(gòu)優(yōu)化性能，同時(shí)寫代碼反而更方便了，那何樂而不為呢?

“SPL數(shù)據(jù)結(jié)構(gòu)怎么樣？”
 Unfortunately they are terrible. They did offer some benefits prior to PHP 7, but have since been neglected to the point of having no practical value.
“我們?yōu)槭裁床荒苄拚透倪M(jìn)它們？”
We could, but I believe their design and implementation is so poor that it would be better to replace them with something brand new.
“SPL數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)非?？膳隆！?- 安東尼 費(fèi)拉拉

PHP 的 Array 訪問不存在的 key 可以得到 null，不會(huì)產(chǎn)生 fatal error，但會(huì)有一個(gè) E_NOTICE。這個(gè) E_NOTICE 會(huì)被 set_error_handler 注冊(cè)的函數(shù)截獲。顯然，這種代碼上的不干凈和性能上的無謂開銷完全是可以避免的。

一般的 PHPer 都不會(huì)用array_key_exists 和 if else 來處理，這樣做會(huì)顯得有些麻煩。
有時(shí)候Array 的使用，性能會(huì)變得很差。Array 本質(zhì)上是一個(gè) Map，unshift 一個(gè)元素進(jìn)來，將會(huì)改變每個(gè)元素的 key，這是一個(gè) O(n)操作。另外，PHP 的 Array 將其 value(包括 key 和 它的 hash) 保存在一個(gè) bucket 中，所以我們需要查看每一個(gè) bucket 并更新 hash。
PHP 內(nèi)部其實(shí)是通過創(chuàng)建新的 array 來完成 array_unshift 操作的，其性能問題可想可知。
DataStructures，PHP7的一個(gè)擴(kuò)展，數(shù)組(Array)的一個(gè)替代品。
Github: https://github.com/php-ds
Namespace: Ds
接口類: Collection, Sequence, Hashable
實(shí)現(xiàn)類(final class): Vector, Deque, Map, Set, Stack, Queue, PriorityQueue, Pair

接口類

Collection 是一個(gè)基礎(chǔ)接口，定義了一個(gè)數(shù)據(jù)集合（這里的集合指的是 Collection，不是 Set） 的基本操作，比如 foreach, echo, count, print_r,  var_dump, serialize, json_encode, and clone.等。

Sequence 是類數(shù)組數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)接口，定義了很多重要且方便的方法，比如 contains, map, filter, reduce, find, first, last 等。從圖中可知，Vector, Deque, Stack, Queue 都直接或者間接的實(shí)現(xiàn)了這個(gè)接口。它的特點(diǎn)如下：

值始終會(huì)被索引 [0, 1, 2, …, size - 1]
刪除或插入更新所有連續(xù)值的位置。
只允許訪問索引在 [0, size-1]的值。


Hashable 在圖中看起來比較孤立，但對(duì)于 Map 和 Set 很重要。一個(gè) Object 如果實(shí)現(xiàn)了 Hashable，就可以作為 Map 的 key，可以作為 Set 的元素。這樣 Map 和 Set 就能像 Java 一樣方便的使用了。

實(shí)現(xiàn)類
Vector 應(yīng)該是最為常用的數(shù)據(jù)結(jié)構(gòu)之一了，可以把它當(dāng)成 Ruby 的 Array 或者 Python 的 List。其元素的值的 index 就是它在 buffer 中的 index，所以效率很高。只要有使用數(shù)組的需求且不需要 insert, remove, shift 和 unshift 的都可以用它。
視頻說明



優(yōu)點(diǎn)：

低內(nèi)存使用量
get, set, push and pop的復(fù)雜度為 O(1)



缺點(diǎn)：
insert, remove, shift,  and unshift 的復(fù)雜度為 O(n)


PhotoShop中使用主要的數(shù)據(jù)結(jié)構(gòu)就是 Vector  ---- Sean Parent

Deque（發(fā)音[dek] ） 是一種雙端隊(duì)列“double-ended queue”。在 queue 的基礎(chǔ)上增加了一個(gè)頭指針，因此 shift 和 unshift 也是 O(1) 復(fù)雜度了。但帶來的性能損耗并不多。
兩個(gè)指針用于跟蹤頭部和尾部， 指針可以“wrap around”緩沖區(qū)的末尾，這避免了需要移動(dòng)其他值來騰出空間。 這使得移位和移位非?？?- Vector無法與之競爭。視頻說明


優(yōu)點(diǎn)：

低內(nèi)存使用量。
get,set, push, pop, shift, and unshift 的復(fù)雜度為 O(1)。



缺點(diǎn)：

inser,remove 的復(fù)雜度為 O(n)。
緩沖區(qū)容量必須是2的n次方。




Stack 是一種“LIFO” 結(jié)構(gòu)，按照“后進(jìn)先出”的原則允許訪問、遍歷、銷毀結(jié)構(gòu)頂部的值。DsStack 的內(nèi)部使用的是 DsVector 的實(shí)現(xiàn)。
Queue 是一種“FIFO”結(jié)構(gòu)，按照“先進(jìn)先出”的原則允許訪問、遍歷、銷毀結(jié)構(gòu)頂部的值。DsQueue 內(nèi)部使用的是 DsDeque 的實(shí)現(xiàn)。
PriorityQueue（優(yōu)先級(jí)隊(duì)列） 與 Queue 非常的相似，按照分配的優(yōu)先級(jí)將值推入隊(duì)列，優(yōu)先級(jí)最高的值始終位于隊(duì)列的前端。遍歷 PriorityQueue 具有破壞性，相當(dāng)于連續(xù)的彈出操作，直到隊(duì)列為空。使用最大堆實(shí)現(xiàn)。
Hashable , 一個(gè)允許用對(duì)象作鍵的接口。注意：并不是hashTable。Hashable只引入了兩種方法：hash和equals。支持Hashable接口的數(shù)據(jù)結(jié)構(gòu)是Map和Set。

Map , 一種連續(xù)的鍵值對(duì)集合。同 array 的使用是一致的，key 可是是任意的類型，但是必須唯一。如果相同的 key 添加到 Map 中，那么會(huì)替換掉原有的。同array 一樣，插入的順序會(huì)被保留。


優(yōu)點(diǎn)：

效率和內(nèi)存使用幾乎和 Array 一致
當(dāng)Map 的大小下降到足夠小時(shí)，會(huì)自動(dòng)釋放已分配的內(nèi)存。
key 和 value 可以是任意類型，甚至是對(duì)象。
put, get, remove, 和 hasKey 的復(fù)雜度為 O(1)



缺點(diǎn)：
當(dāng)key 為對(duì)象時(shí)，不能轉(zhuǎn)成 Array 。




Set，是一個(gè)無序唯一值的集合。Map 內(nèi)部使用了 set 的實(shí)現(xiàn)，他們都是基于Array 相同的內(nèi)部結(jié)構(gòu)，這意味這Set 的排序具有 O(n*log n) 的復(fù)雜度。


優(yōu)點(diǎn)：

添加、刪除、引用都是 O(1)的復(fù)雜度
使用 Hashable 的接口
支持任何類型的值。



缺點(diǎn)：

不支持 push, pop, insert, shift, unshift
如果在索引之前刪除了值，那么復(fù)雜度會(huì)從 O(1) 降到 O(n)





這里在說明一點(diǎn)，Array中的值本身是沒有索引的，因此在使用 in_array()的時(shí)候呈線性搜索，復(fù)雜度為 O(n)。
如果想要?jiǎng)?chuàng)建一個(gè)唯一值數(shù)組，可以使用 array_unique()，由于array_unique()針對(duì)的是 value 而不是 key，所以每個(gè)數(shù)組成員都會(huì)被限行搜索，復(fù)雜度會(huì)變?yōu)?O(n2)。