先說結論：

PHP 的 array 其實是有序的 HashMap

以一般學習資料結構而言：

  • 陣列（Array）：使用一連串連續的記憶體空間來存資料。同一陣列只會存放同一種資料型態的值，並用索引來記錄順序。優點是查找時間複雜度為 O(1)，缺點是只要移動資料順序或陣列空間不夠用時（需創建另一串更大的連續記憶體來做搬移），時間複雜度會變成 O(N)。

  • 哈希表（HashMap）：先定義好鍵值的型態，並且是無序的。當你放值時會用 hash function 算出雜湊值，以對應放值的記憶體位址。遇到碰撞時不同語言會用不同的方式解決，例如常見的拉鍊法。優點是查找和存放的時間複雜度都是 O(1)，缺點是效能會隨使用的 hash function 不同而有差異，且當哈希表容量不足時，會定義一個新的哈希表，並把舊的鍵值移過去，等於每個舊鍵都要重跑一次 hash function，成本大幅提高。

PHP Array：

在 PHP 裡基於 C 語言將兩者實作成關聯陣列，名稱還是叫 Array。可接受存放不同型態的鍵值對，且為有序的 HashMap

補充：

以 JAVA 而言，HashMap 會有預設大小(16)，如果存放內容超過最大容量的 75% 時，程式會自動建立一個更大的 HashMap(2倍)，並將舊的 HashMap 中所有鍵值搬移到新的 HashMap 裡（會重新對應hash值），導致時間複雜度變成O(N)。
參考 stackoverflow 討論

HashMap 在碰撞時會用鏈表存有撞到的值，查詢時會遍歷鍊表（鏈式解決碰撞法），當鍊表大於預設值(8)時會轉存成紅黑樹，以避免若無限碰撞時 HashMap 會變成鍊表。不用二元樹是因為二元樹在最糟情況下等同於鍊表，而小於 8 的情況下用紅黑樹則過於浪費資源。

PHP Array 使用要點：

參考：