この記事はWeChat公式アカウント「PHPを書く老王」から転載されています。転載をご希望の場合は、WeChat公式アカウント「PHPを書く老王」までご連絡ください。

線形リスト（線形ストレージ構造の略）とは、「すべてのデータを1行で結び付けて物理空間に格納する」という意味です。最も単純な線形リストは配列です。PHPの配列自体は基本的なデータ構造で構成されていませんが、その内部実装では線形リストのデータ構造の大部分が利用されています。今日は、線形リストのデータ構造について学ぶ機会に、PHP配列の内部実装の原則を見直してみましょう。

PHP配列の内部実装

配列はPHPにおいて強力かつ重要なデータ型です。単純な数値インデックス配列とキーと値のペアからなる配列の両方をサポートしており、キーと値のペアからなる配列はJavaのHashMapに似ています。配列はハッシュテーブルを用いて実装されているため、基本的な検索計算量はO(1)であり、データの走査順序も保証されます。

まず、PHP のデータ構造がカーネル C 言語でどのようになっているかを見てみましょう。

PHP コードで配列に要素を挿入すると何が起こるかを見てみましょう。

 $arr = [ '名前' => '管理者' ];

1. カーネルはまず_zend_arrayデータオブジェクトを作成します。配列の初期サイズはHT_MIN_SIZEで、PHPでは8と定義されています。そのため、配列の要素数が8未満の場合、データを挿入しても配列は拡張されません。

2. Times 33 ハッシュ アルゴリズムを使用して、名前を長整数に変換します。

3. `arData[nNumUsed++]` では、Bucket データのキーは配列のキー名です。`h` には、キーのハッシュ値（負の値）が格納されます。`val.u2.next` には、`arData[h]` のアドレスが格納されます。変換テーブルは、`arData` ポインタを起点としてミラーマッピングで格納されます。この方法により、追加のストレージスペースは必要ありません。変換テーブルは、`arData` に割り当てられたスペースと同時に割り当てられます。

配列を検索する際、キー名をハッシュ化することで、キーと値のペアが格納されているバケットを直接特定できます。トラバース処理では、arData は順序付けされたC配列であるため、配列をトラバースすることで、キーと値のペアが格納されているバケットを取得できます。したがって、PHP配列は、O(1)の計算量で配列を取得し、配列要素を順次トラバースすることができます。

対応するソース コード ロジックを実装するメイン コア コードは次のとおりです。

上記のプロセスではハッシュ衝突のケースは省略されています。しかし、この簡略化されたバージョンからでも、PHP配列の実装には膨大なデータ構造の知識が活用されていることは明らかです。

`Bucket *arData;` はC言語の配列であり、データ構造における順序付きリストに相当します。`Buckets` は `val.u2.next` によって連結され、連結リスト構造を形成します。

一方、ハッシュの衝突を処理する際、PHPは衝突するすべてのキー名をリンクリストに縮退させます。これは、ハッシュ処理メソッドのほとんどで採用されているアプローチです。

順次リスト

順次リストの定義は次のとおりです。

シーケンシャルリストとは、順番に格納される線形リストです。シーケンシャルストレージとは、連続したメモリ位置のセットを使用して、線形リストの各要素を順番に格納するストレージ構造です。

上記の PHP コア コードでは、arData は連続リストです。

シーケンスリストの特性:

1. 線形リスト内の論理的に隣接するデータ要素は、ストレージ内でも物理的に隣接しています。

2. ストレージ密度は高いですが、アプリケーションに「十分な」ストレージ領域を事前に割り当てる必要があるため、ストレージ領域が無駄になる可能性があります。

3. ランダムアクセスが容易になります。線形リストの開始位置が決定されれば、線形リスト内の任意のデータ要素にランダムにアクセスできます。したがって、線形リストの順次記憶構造はランダムアクセス記憶構造です。

4. 連続リストでの挿入および削除操作では、多数のデータ要素が移動されるため、挿入および削除操作は不便です。

連続リストの問題:

1. 物理的に連続したストレージはメモリ利用に不便です。例えば、容量10の配列は10バイトのメモリを必要としますが、現状では連続した10バイトの空きメモリ領域がなく、10バイト未満の不連続なメモリ領域が多数存在するため、割り当てが不可能です。

2. シーケンシャルリストの容量を決定するのは困難です。C言語では、配列を定義するにはサイズを指定する必要があります。このサイズは、基盤となるシステムが連続したメモリ空間を割り当てる際の利便性を考慮しています。PHPのソースコードでは、空の配列を初期化する際に、まず長さ16のarData配列が作成され、拡張が必要な​​場合にのみ配列のサイズが変更されます。

3. 要素を挿入するのは不便です。連続リスト全体を移動する必要があります。

リンクリスト

連結リストは、連続リストの問題を解決するために提案されたデータ構造です。連結リストは物理的に連続していない、非連続なストレージ構造です。データ要素の論理的な順序は、リスト内のポインタの連結順序によって実現されます。PHP配列のソースコードでは、各Bucketは連結リスト内のノードです。Bucket.u2.nextは次のノードを指します（ただし、これは主にハッシュ検索を実装するためのものです）。

リンク リストは、リンクされている方法に基づいて、単一リンク リストと二重リンク リストに分けられます。

片方向リンクリストの各ノードには、次のノードへのポインタのみが含まれ、バックトラックは不可能です。ノードの追加と削除に適しています。

双方向リンクリストの各ノードには、次のノードと前のノードへのポインタの両方が含まれており、前のノードへの迅速なアクセスを可能にします。これは、ノード値の双方向参照が必要な状況に適しています。

リンクリストの利点:

挿入と削除は非常に効率的で、ポインタの方向を変えるだけで実行できます。

高いメモリ使用率を誇り、メモリの無駄を省き、メモリ内の小さな非連続領域を有効活用することで、必要な時にのみメモリ領域を確保します。サイズは可変であるため、柔軟な拡張が可能です。

要約

この記事では、PHP 7.4のソースコードに基づいて、キーと値のペアの検索速度をO(1)に抑えつつ、PHPが内部的に順序付き配列を実装する仕組みを説明します。PHPの配列実装から始め、線形リストにおける順序付きリストと連結リストの基本的な概念と特徴を紹介します。これはあくまでも基本的な概要ですが、皆様のお役に立てれば幸いです。

[1] PHP7ハッシュテーブル実装原則: http://www.sohu.com/a/119748257_464029

[2] リンクリスト: https://blog.csdn.net/Shuffle_Ts/article/details/95055467

[3] データ構造（C言語版）シリーズ1：線形リスト：https://www.cnblogs.com/wwf828/p/9503821.html