宣告: 本文採用 CC BY-NC-ND 4.0 授權。
在 PHP 中表示集合的資料型別就一種：Array。相信每個初學 PHP 的都會對它感到疑惑。這個東西看起來應該和其他語言中的 Array 或 List 一樣，但在 PHP 中，它是一切，也就是 List，也是 Map：
<?php $a = array(1, 2, 3); $b = array('key1' => 1, 'key2' => 2);
這聽起來似乎很好，反正大家都使用同一種資料結構，偶爾情況下才會有些效能問題，況且升級 PHP7 之後 Array 的效能也提高了，實在不濟還可以加記憶體。但如果我們可以透過引入更便利的資料結構來優化效能，同時寫程式碼反而更方便了，那何樂而不為呢?
推薦教學：《PHP教學》
Array 的缺點
有些時候我們需要保存一個集合（Set），但Array 並不能保證元素的唯一性，array_unique 有不可避免的效能損耗。一種折衷方案是，將元素當做 key，同時 value 為 true 來曲線實現 Unique Array 的功能：
<?php $users = User::find($ids);
$res = [];
foreach ($users as $user) {
$res[$user->id] = true;
}
PHP 的 Array 存取不存在的 key 可以得到 null，不會產生 fatal error，但會有一個 E_NOTICE。這個 E_NOTICE 會被 set_error_handler 註冊的函數截獲。顯然，這種程式碼上的不乾淨和效能上的無謂開銷完全是可以避免的。
<?php $req = []; $req['user_id']; // PHP Notice: Undefined offset
可以用 array_key_exists 和 if else 來讓程式碼乾淨一些，但這樣就顯得囉嗦了。
array 的一些函數式方法很難用，例如 array_map, array_walk 等，寫起來也很醜。當然這一點原生 PHP 沒什麼好方法，畢竟 PHP 的物件導向的基因不是很強。
<?php array_map(function($user){
return $user->is_deleted();
}, $users);
// 就是这么难看 users.map { |user| user.is_deleted? }
# ruby 的就好看多了
在某些情況下，使用 Array 效能很差1，例如下面這段程式碼：
<?php $a=[1,2,3,4,5,6,7]; echo $a[5]; // 6 array_unshift($a, 0); // $a: [0,1,2,3,4,5,6,7]; echo $a[5]; // 5
看起來似乎沒什麼，但要注意的是，Array 本質上是一個 Map，unshift 一個元素進來，將會改變每個元素的 key，這是一個 $O(n)$ 操作。另外，PHP 的 Array 將其 value(包擴 key 和 它的 hash) 保存在一個 bucket 中，所以我們需要查看每一個 bucket 並更新 hash。 PHP 內部其實是透過建立新的 array 來做 array_unshift 操作的，其效能問題可想可知2。
其他缺點不一而足。
PHP 資料結構外掛程式
Array 飽受詬病，就會出現替代方案。 PHP5 有spl，但有些場景表現很差，且設計的很不好1。 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 等。
<?php $sequence = new \Ds\Vector([1, 2, 3]); json_encode($sequence);
Sequence 是類別數組資料結構的基礎接口，定義了許多重要且方便的方法，例如 contains, map, filter, reduce, find, first, last 等。從圖中可知，Vector, Deque, Stack, Queue 都直接或間接的實作了這個介面。
<?php $sequence = new \Ds\Vector([1, 2, 3]);
print_r($sequence->map(function($value) { return $value * 2; }));
print_r($sequence);
?>
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（討論）3。
Stack 栈，嗯没什么好说的，它继承自 Collection，但内部使用 Vector 实现。这样做的好处是实现方便，且同时可以屏蔽不需要的和不应该出现的方法。
Queue 队列，内部使用 Deque 实现。
PriorityQueue，最大堆实现。
Map。以前使用 Array 来实现 map 的地方，改用 Map 更好。二者性能几乎一致，但 Map 对内存的管理更好。而且，Map 的语法要更加友好。
<?php
$req = [];
$req['user_id']; // PHP Notice: Undefined offset
$req = new \Ds\Map(["a" => 1, "b" => 2, "c" => 3]);
$req->get('user_id');// OutOfBoundsException
$req->get('user_id', 0); // 0 是默认值
// 即可以方便的指定默认值，也可以选择抛出异常。不用 array，不会产生 E_NOTICE
$req->keys();
$req->map(function($key, $value) { return $value * 2; });
不仅如此，只要 object 继承了 Hashable，Map 还允许使用 object 作为 key。
<?php
class Photo implements \Ds\Hashable {
public function __construct($id) {
$this->id = $id;
}
public function hash() {
return $this->id;
}
public function equals($obj): bool {
return $this->id === $obj->id;
}
}
$p1 = new Photo(1);
$p2 = new Photo(2);
$map = new Ds\Map();
$map->put($p1, 1);
$map->put($p2, 2);
Set 集合是一种元素唯一的数据结构。和 array_unique 相比性能有很大提升，而且用法也更加优雅1。
<?php $set = new Ds\Set(); $set->add($p1); $set->add($p2);
php ds 插件性能测试 ↩ ↩2 ↩3
当然，这一点可能稍嫌牵强，毕竟即使是数据量很大的情况下，array_unshift 的耗时也没有那么大 ↩
github 上还在讨论可以增加一个不可变类型 Tuple，以及取消 Vector 直接使用 Deque，讨论地址和 2.0API 计划 ↩
