PHP關(guān)聯(lián)陣列將作為有序的哈希表實(shí)現(xiàn)，從而實(shí)現(xiàn)有效的鍵值操作； 1。插入：平均O（1），由於碰撞或調(diào)整大小而導(dǎo)致的最差O（N）； 2.查找：平均O（1），碰撞的最差O（N）； 3。刪除：平均o（1），如果有很多碰撞，則最差的o（n）； 4。密鑰檢查（ISSET/ARRAY_KEY_EXISTS）：平均O（1），最差O（n）; 5。迭代：O（n）在所有情況下； 6。 array_merge：o（mn）; 7。 array_keys/array_values：o（n）;實(shí)際用途偏愛isset（）進(jìn)行非無效檢查，避免了不信任的密鑰，最大程度地減少大量合併，並將陣列視為在對(duì)抗條件下具有罕見但可能的性能降解的快速哈希地圖。

PHP關(guān)聯(lián)陣列（也稱為關(guān)聯(lián)陣列或簡(jiǎn)單的陣列）實(shí)際上是在引擎蓋下訂購(gòu)的哈希表。這使它們具有難以置信的通用性，從而允許使用混合鍵類型（字符串和整數(shù)）和動(dòng)態(tài)調(diào)整的鍵值存儲(chǔ)。分析時(shí)間複雜性時(shí)，必須了解PHP陣列被用作哈希表的實(shí)現(xiàn)，這直接影響了共同操作的性能。

以下是基於基礎(chǔ)哈希表實(shí)現(xiàn)的PHP關(guān)聯(lián)陣列中關(guān)鍵操作的時(shí)間複雜性的分析。

1。插入（添加一個(gè)元素）

操作： $array[$key] = $value;

• 平均情況： o（1）
  插入涉及計(jì)算鍵的哈希，並將鍵值對(duì)放在適當(dāng)?shù)耐爸?。具有良好的哈希功能和足夠的容量，這是恆定的時(shí)間。

• 最壞的情況： o（n）
  在極少數(shù)情況下，例如哈希碰撞攻擊或陣列大小時(shí)（重新調(diào)整所有元素），插入可能會(huì)降解為o（n）。但是，調(diào)整大小在許多插入中攤銷，因此平均性能仍然O（1）。

  

注意：PHP在擴(kuò)展過程中使用稱為“增量重新升級(jí)”的機(jī)制，這有助於降低性能峰值。

2。查找（通過鍵訪問）

操作： $value = $array[$key];

• 平均情況： o（1）
  哈希計(jì)算和直接存儲(chǔ)桶訪問使查找非?？?。

• 最壞的情況： o（n）
  當(dāng)所有鑰匙在同一桶中發(fā)生碰撞時(shí)（例如，由於惡意輸入或哈希分佈不良）時(shí)發(fā)生。實(shí)際上，PHP對(duì)碰撞攻擊的內(nèi)部保護(hù)措施可以緩解這種情況（例如，PHP 7中使用的Siphash）。

3。刪除（不設(shè)密鑰）

操作： unset($array[$key]);

• 平均情況： o（1）
  通過哈希找到元素並刪除它通常是恆定的時(shí)間。

• 最壞的情況： o（n）
  只有目標(biāo)桶中有許多哈希碰撞。否則，刪除是有效的。

注意： unset()不會(huì)立即壓縮內(nèi)存。內(nèi)部哈希表將條目標(biāo)記為已刪除，這可能會(huì)影響迭代，但不會(huì)顯著影響查找性能。

4。鑰匙存在檢查

操作： array_key_exists($key, $array)或isset($array[$key])

• isset($array[$key]) ： o（1）平均
  快速基於哈希的查找。返回null值的false（如果您需要區(qū)分零與缺席，則不合適）。

• array_key_exists($key, $array) ： o（1）平均
  也基於哈希，但即使值為null，也可以返回true。

• 最壞的情況： o（n）由於碰撞（與查找相同）。

5。迭代（使用foreach ）

操作： foreach ($array as $key => $value)

• 時(shí)間複雜性： o（n）
  在所有元素上進(jìn)行迭代需要線性時(shí)間，因?yàn)闊o論鑰匙分佈如何，每個(gè)元素都會(huì)精確訪問一次。

注意：PHP數(shù)組保持內(nèi)部排序（插入順序），因此迭代順序是可以預(yù)測(cè)的。

6。陣列合併

操作： array_merge($a, $b)

• 時(shí)間複雜性： O（MN）
  其中m和n是兩個(gè)數(shù)組中的元素?cái)?shù)量。複製每個(gè)元素，並重新重新串聯(lián)鍵。重新索引數(shù)字鍵，添加了開銷。

注意：由於重新分配和內(nèi)存分配，合併大型陣列可能很昂貴。

7.獲取所有鍵或值

操作： array_keys($array) ， array_values($array)

• 時(shí)間複雜性： o（n）
  這兩個(gè)功能都必須遍歷整個(gè)數(shù)組，並返回帶有鍵或值的新數(shù)組。

時(shí)間複雜性的摘要

實(shí)際含義

• 當(dāng)您不需要區(qū)分null與缺席時(shí)，請(qǐng)使用isset()進(jìn)行快速鍵檢查。
• 避免在對(duì)安全敏感的上下文中使用與不受信任密鑰的關(guān)聯(lián)陣列（儘管PHP減輕了哈希洪水）。
• 對(duì)於大型數(shù)據(jù)集，如果性能成為瓶頸，請(qǐng)考慮對(duì)象存儲(chǔ)或?qū)I(yè)數(shù)據(jù)結(jié)構(gòu)。
• 重複合併或複制大型陣列可能是昂貴的 - 考慮參考文獻(xiàn)或懶惰評(píng)估。

在大多數(shù)實(shí)際應(yīng)用程序中，PHP關(guān)聯(lián)陣列由於優(yōu)化的哈希表實(shí)現(xiàn)而有效地執(zhí)行。儘管存在最糟糕的情況，但在實(shí)踐中很少見。了解這些複雜性有助於編寫可擴(kuò)展的PHP代碼，尤其是在至關(guān)重要的應(yīng)用程序中。

基本上，將PHP陣列視為快速哈希地圖 - 對(duì)於平均案例O（1）操作而言，但要注意邊緣案例。

以上是分析PHP關(guān)聯(lián)陣列中關(guān)鍵操作的時(shí)間複雜性的詳細(xì)內(nèi)容。更多資訊請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！