PHP 的數據結構擴展

知識 08-20

在PHP中表示集合的數據類型就一種：Array。相信每個初學PHP的都會對它感到疑惑。這個東西看起來應該和其他語言中的Array或者List一樣，但在PHP中，它是一切，既是List，也是Map。

這聽起來似乎很好，反正大家都使用同一種數據結構，偶爾情況下才會有些性能問題，況且升級 PHP7 之後， Array 的性能也提高了，實在不濟還可以加內存。

但如果我們可以通過引入更便利的數據結構優化性能，同時寫代碼反而更方便了，那何樂而不為呢?

Array 的缺點

有些時候我們需要保存一個集合（Set），但是 Array 並不能保證元素的唯一性，array_unique 有不可避免的性能損耗。一種折衷方案是，將元素當做 key，同時 value 為 true 來曲線實現 Unique Array 的功能：

PHP 的 Array 訪問不存在的 key 可以得到 null，不會產生 fatal error，但會有一個 E_NOTICE。這個 E_NOTICE 會被 set_error_handler 註冊的函數截獲。顯然，這種代碼上的不幹凈和性能上的無謂開銷完全是可以避免的。

可以用 array_key_exists 和 if else 來讓代碼乾淨一些，但這樣就顯得啰嗦了。

array 的一些函數式方法很難用，比如 array_map, array_walk 等，寫起來也很醜陋。當然這一點原生 PHP 沒什麼好方法，畢竟 PHP 的面向對象的基因不是很強。

在某些情況下，使用 Array 性能很差，比如下面這段代碼：

看起來似乎沒什麼，但需要注意的是，Array 本質上是一個 Map，unshift 一個元素進來，將會改變每個元素的 key，這是一個 O(n) 操作。另外，PHP 的 Array 將其 value(包括 key 和它的 hash) 保存在一個 bucket 中，所以我們需要查看每一個 bucket 並更新 hash。PHP 內部其實是通過創建新的 array 來做 array_unshift 操作的，其性能問題可想可知。

其他缺點不一而足。

PHP 數據結構插件

Array 飽受詬病，就會出現替代方案。PHP5 有spl，但是有些場景性能很差，且設計的很不好。laravel 的 Collection 提供了更好用的 Map，但畢竟只是一種單一的數據結構，而且對 orm 操作設計了不少特有的介面，其用途受到限制。

PHP7 新增的 Data Structures 插件（簡稱 ds）是 PHP 下一個優秀的補充，它充分考慮了便利、安全和整潔的需求。其結構如下圖所示：

它提供了 3 個介面類：Collection, Sequence, Hashable 和 7 個實現類（final class）：Vector, Deque, Map, Set, Stack, Queue, PriorityQueue。

介面

Collection 是基礎介面，定義了一個數據集合（這裡的集合指的是 Collection，不是 Set）的基本操作，比如 foreach, json_encode, var_dump 等。

Sequence 是類數組數據結構的基礎介面，定義了很多重要且方便的方法，比如 contains, map, filter, reduce, find, first, last 等。從圖中可知，Vector, Deque, Stack, Queue 都直接或者間接的實現了這個介面。

Hashable 在圖中看起來比較孤立，但對於 Map 和 Set 很重要。一個 Object 如果實現了 Hashable，就可以作為 Map 的 key，可以作為 Set 的元素。這樣 Map 和 Set 就能像 Java 一樣方便的使用了。

實現類

Vector 應該是最為常用的數據結構之一了，可以把它當成 Ruby 的 Array 或者 Python 的 List。其元素的值的 index 就是它在 buffer 中的 index，所以效率很高。只要有使用數組的需求且不需要 insert, remove, shift 和 unshift 的都可以用它。

Deque([dek]) 是雙端隊列，在 Vector 的基礎上增加了一個頭指針，因此 shift 和 unshift 也是 O(1)複雜度了。但帶來的性能損耗並不多，因此也有討論是不是只需要一個 Deque 就夠了，不需要 Vector。

Stack 棧，嗯，沒什麼好說的，它繼承自 Collection，但內部使用 Vector 實現。這樣做的好處是實現方便，且同時可以屏蔽不需要的和不應該出現的方法。

Queue 隊列，內部使用 Deque 實現。

PriorityQueue，最大堆實現。

Map。以前使用 Array 來實現 map 的地方，改用 Map 更好。二者性能幾乎一致，但 Map 對內存的管理更好。而且，Map 的語法要更加友好。