PHP連想配列は、順序付けられたハッシュテーブルとして実裝され、効率的なキー値操作を可能にします。 1。挿入：平均O（1）、衝突またはサイズ変更による最悪のO（n）。 2。ルックアップ：平均O（1）、衝突による最悪のO（n）。 3。削除：平均O（1）、最悪のO（n）多くの衝突の場合。 4。キーチェック（ISSET/array_key_exists）：平均O（1）、最悪のo（n）; 5。反復(fù)：O（n）すべての場合において。 6。ARRAY_MERGE：O（MN）; 7。ARRAY_KEYS/ARRAY_VALUES：o（n）;実用的な使用は、非ヌルチェックのISSET（）を好み、信頼されていないキーを回避し、大きなマージを最小限に抑え、アレイを敵対的條件下でのまれではあるが可能なパフォーマンス分解を伴う高速なハッシュマップとして扱います。

PHP連想配列（連想アレイまたは単にアレイとしても知られている）は、実際にフードの下でハッシュテーブルを注文します。これにより、それらは非常に用途が広く、キータイプ（文字列と整數(shù)）と動的なサイズ変更を備えたキー価値ストレージが可能になります。時間の複雑さを分析するとき、PHPアレイがハッシュテーブルとして実裝されていることを理解することが不可欠です。これは、共通操作のパフォーマンスに直接影響します。

以下は、基礎(chǔ)となるハッシュテーブルの実裝に基づいて、PHP連想配列の主要な操作の時間の複雑さの分析です。

1。挿入（要素の追加）

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

• 平均ケース： o（1）
  挿入には、キーのハッシュを計算し、適切なバケツにキー価値ペアを配置することが含まれます。優(yōu)れたハッシュ関數(shù)と十分な容量があるため、これは一定の時間です。

• 最悪の場合： o（n）
  まれに、ハッシュ衝突攻撃やアレイがサイズが変更された場合（すべての要素の再ハッシュ）、挿入はO（n）に分解する可能性があります。ただし、サイズ変更は多くの挿入で償卻されるため、平均パフォーマンスはO（1）のままです。

  

注：PHPは、拡張中に「増分再ハッシュ」と呼ばれるメカニズムを使用します。これにより、パフォーマンスのスパイクが削減されます。

2。ルックアップ（キーによるアクセス）

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

• 平均ケース： o（1）
  ハッシュ計算とダイレクトバケットアクセスは、検索を非常に高速にします。

• 最悪の場合： o（n）
  すべてのキーが同じバケツに衝突したときに発生します（たとえば、悪意のある入力やハッシュ分布が不十分なため）。実際には、これはPHPの衝突攻撃に対する內(nèi)部保護によって軽減されます（たとえば、PHP 7で使用されているサイファッシュ）。

3。削除（キーによる設(shè)定）

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

• 平均ケース： o（1）
  ハッシュを介して要素を見つけることとそれを削除することは、通常一定の時間です。

• 最悪の場合： o（n）
  ターゲットバケットに多くのハッシュ衝突がある場合のみ。それ以外の場合、削除は効率的です。

注： unset()すぐにメモリをコンパクトしません。內(nèi)部ハッシュテーブルは、削除されたエントリをマークします。これは、反復(fù)に影響を與える可能性がありますが、ルックアップパフォーマンスは大きくなりません。

4.キー存在チェック

操作： array_key_exists($key, $array)またはisset($array[$key])

• isset($array[$key]) ： o（1）平均
  高速ハッシュベースのルックアップ。 null値に対してfalseを返します（したがって、nullを不在と區(qū)別する必要がある場合は適切ではありません）。

• array_key_exists($key, $array) ： o（1）平均
  また、ハッシュベースですが、値がnullであってもtrueを返します。

• 最悪の場合：衝突によるO（n）（ルックアップと同じ）。

5。イテレーション（ foreachを使用）

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

• 時間の複雑さ： o（n）
  すべての要素を繰り返すには、キー分布に関係なく、各要素が正確に1回訪問されるため、線形時間がかかります。

注：PHPアレイは、內(nèi)部順序（挿入順序）を維持するため、反復(fù)順序が予測可能です。

6。アレイマージ

操作： array_merge($a, $b)

• 時間の複雑さ： o（mn）
  ここで、mとnは2つの配列の要素の數(shù)です。各要素がコピーされ、文字列キーが再ハッシュされます。數(shù)字キーが再インネックスされており、オーバーヘッドが追加されます。

注：再ハッシュとメモリの割り當(dāng)てにより、大きな配列のマージは高価です。

7.すべてのキーまたは値を取得します

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

• 時間の複雑さ： o（n）
  両方の関數(shù)は、配列全體を通過し、キーまたは値を使用して新しい配列を返す必要があります。

時間の複雑さの概要

実用的な意味

• null不在と區(qū)別する必要がない場合は、高速キーチェックにisset()を使用します。
• セキュリティに敏感なコンテキストで信頼できないキーを使用して連想配列を使用しないでください（ただし、PHPはハッシュフラッディングを軽減します）。
• 大規(guī)模なデータセットの場合、パフォーマンスがボトルネックになった場合は、オブジェクトストレージまたは専門データ構(gòu)造を検討してください。
• 大きなアレイの繰り返しのマージまたはコピーは、コストがかかる場合があります。

ほとんどの実際のアプリケーションでは、PHP連想配列が最適化されたハッシュテーブル実裝により効率的に機能します。最悪のシナリオは存在しますが、実際にはまれです。これらの複雑さを理解することは、特にパフォーマンスが批判的なアプリケーションで、スケーラブルなPHPコードを書くのに役立ちます。

基本的に、PHPアレイを高速ハッシュマップとして扱います。これは、平均ケースO（1）操作のためですが、エッジケースに注意してください。

以上がの詳細內(nèi)容です。詳細については、PHP 中國語 Web サイトの他の関連記事を參照してください。