HashTableの衝突解決アルゴリズムとメモリ効率：PHP 8.xのPacked Array最適化の深層
Zend Engineの内部構造において、すべての根幹を成すデータ構造が `HashTable` である。PHPにおける「連想配列」「インデックス配列」「オブジェクトのプロパティ管理」「シンボルテーブル（スコープ内の変数管理）」、さらにはクラスのメソッドや定数のルックアップに至るまで、そのすべてがこの `HashTable` という巨大な迷宮の上で動いている。
Webアプリケーションのパフォーマンスチューニングの限界を突破したいのであれば、私たちが日常的に叩いている `$arr[‘key’] = ‘val’;` というコードが、Zend VMのメモリ空間上でどのような構造体に分解され、CPUキャッシュとどのように戯れているのかを完全に把握していなければならない。
今回は、PHP 8.x系における `HashTable` の衝突解決アルゴリズムの変遷と、メモリ効率を劇的に引き上げた「Packed Array（密配列）」の内部構造、そしてそれがガベージコレクションやOPcacheの挙動、ひいては低レイヤのセキュリティ（オブジェクトインジェクションやメモリ安全性）にどう影響するかを、Zend Engineのソースコードの深層から解き明かしていく。
—
1. Zend Engineにおける HashTable の基本構造とメモリレイアウト
PHP 7以降、HashTableのアーキテクチャは劇的な刷新を遂げた。従来のPHP 5時代におけるHashTableは、要素（Bucket）ごとに個別のヒープメモリを `malloc` し、ポインタでつなぐという極めてキャッシュ効率の悪い構造をしていた。
PHP 8の `HashTable` (`_zend_array` 構造体) は、以下のような物理的メモリ配置をとる。
1. 護衛・メタデータ領域 (Bucket数、サイズ、ハッシュマスクなどのヘッダ)
2. 高速ハッシュルックアップテーブル (ArData / Indices)
3. 連続した Bucket 配列 (Zend `Bucket` 構造体の連続領域)
`_zend_array` と `Bucket` の物理配置
// Zend/zend_types.h の概念的表現
typedef struct _zend_array {
zend_refcounted_h gc;
union {
struct {
ZEND_ENDIAN_LOHI_4(
zend_uchar flags,
zend_uchar nApplyCount,
zend_uchar nIteratorsCount,
zend_uchar reserve
)
} v;
uint32_t flags;
} u;
uint32_t nTableSize; // ハッシュテーブルのサイズ（2のべき乗）
uint32_t nTableMask; // ハッシュマスク（nTableSize – 1）
uint32_t nNumUsed; // 使用済み（削除済み含む）バケツの数
uint32_t nInternalPointer;
zend_long nNextFreeElement;
uint32_t arHash; // 衝突解決用のインデックス配列
Bucket arData; // 実際のデータ（Bucket構造体）が連続配置される領域
zend_free_destructor pDestructor;
} HashTable;
特筆すべきは、`arData` が指すメモリ領域である。ここには、キーのハッシュ値、キーの文字列ポインタ、そして実際の値である `zval`（Zend Value）が、CPUのキャッシュライン（通常64バイト）を意識した連続したメモリブロックとして確保される。
これにより、配列の走査（`foreach` 等）を行う際、CPUのプリフェッチ機構が最大限に働き、キャッシュミスの頻度が劇的に低下する。これがPHP 7以降の圧倒的な高速化の正体である。
—
2. 衝突解決アルゴリズムとタイムコンプレックス
ハッシュテーブルの宿命として、異なるキーが同じハッシュ値を持つ「ハッシュ衝突（Collision）」が存在する。PHPでは、この衝突を解決するために 「間接インデックス方式（Indirect Lookup with Map）」 を採用している。
従来のチェーニングとPHPのスマートな解決策
一般的なハッシュテーブルでは、衝突が発生した場合、同じハッシュ値を持つバケツ同士をリンクリスト（連結リスト）で繋ぐ。しかし、ポインタを辿るアプローチはCPUのキャッシュメモリを汚染する。
PHP 8のHashTableでは、`arHash` というインデックス配列を用いて衝突を解決する。
1. キーの文字列から `zend_string_hash_val()`（DJBX33A変法などの高速なハッシュアルゴリズム）を計算する。
2. ハッシュ値と `nTableMask` のビット単位の論理積（`hash & nTableMask`）をとり、`arHash` のインデックスを算出する。
3. `arHash[index]` には、実際のデータが格納されている `arData` 内のオフセット（または直接のバケツ番号）が格納されている。
4. 衝突時: もし `arHash` の指す先にすでに別の要素が存在する場合、各 `Bucket` 構造体内部に持つ `u2.hash_next` というリンクリスト用のオフセットを辿ることで、高速に衝突を解決する。
[ arHash (インデックスマップ) ] ──> [ arData (連続した Bucket 配列) ]
arHash[hash & mask] ───────────> Bucket 0: [ Key / Value / h_next = -1 ]
arHash[hash & mask] ───────────> Bucket 1: [ Key / Value / h_next = 0 ] (衝突発生時はチェイン)
この設計により、メモリの断片化を防ぎつつ、O(1)に近い検索性能（最悪計算量でもO(N)、実際には衝突が最小限に抑えられるように動的に再ハッシュ・リサイズが行われる）を維持している。
—
3. PHP 8.xの真骨頂：Packed Array（密配列）の内部構造
ここからが本題の核心である。私たちが普段何気なく書く、キーを指定しない連続した配列：
$list = [‘alpha’, ‘beta’, ‘gamma’];
このコードを実行したとき、Zend Engineは内部で「キーの文字列ハッシュを計算する必要すらない」ことに気づく。なぜなら、キーが明示されておらず、単なる `0, 1, 2…` の整数インデックスだからだ。
PHP 8.xでは、この状態の配列を Packed Array（密配列） として特別に最適化してメモリに配置する。
秘められたフラグ：`HASH_FLAG_PACKED`
Zend Engineは、配列が以下の条件を満たしているとき、内部フラグに `HASH_FLAG_PACKED` を立てる。
- キーがすべて整数である。
- キーの順序が `0` から始まり、連続している。
- ハッシュルックアップ用の `arHash` 領域が完全に省略される。
これにより、何が起きるか？
- ハッシュ計算のCPUサイクルがゼロになる。
- `arHash` のためのメモリ割り当てが不要になる。
- `arData` のバケツ配列が、文字通り「ただのC言語の配列（`zval` の連続領域）」として振る舞う。
[ 通常の HashTable ]
Memory: [Header] ──> [arHash[]] ──> [arData[] (Bucket)]
[ Packed Array (PHP 8.x) ]
Memory: [Header] ──> [arData[] (Bucket without hash overhead)]
※ arHashが存在しないため、オーバーヘッドが極小化
注意すべき「Packed Arrayの崩壊（Unpacking）」
次のようなコードを書いた瞬間、Zend EngineはこのPacked Arrayの最適化を放棄し、通常のHashTableへと内部構造を「昇格（Upgrade）」させる。
$list = [‘alpha’, ‘beta’, ‘gamma’]; // ここまでは Packed Array
$list[‘custom_key’] = ‘delta’; // 文字列キーの混入により、通常HashTableへ構造変換！
この内部的な構造変換（`zend_hash_packed_to_hash` の呼び出し）は、既存の `arData` の再割り当てやハッシュテーブルの構築を伴うため、パフォーマンス上のコストがかかる。極限までパフォーマンスを絞り出すホットパス（Hot Path）では、配列のキーの型を途中で混在させないことが、Zend VMのCPUパイプラインを乱さないための鉄則となる。
—
4. OPcacheプリローディングとメモリ空間の共融
これほどの複雑な `HashTable` や `zval` の構造体は、リクエストが来るたびにPHPスクリプトをパースし、AST（抽象構文木）を生成し、Opcodeにコンパイルしていたのでは、現代のWebアプリケーションの要求速度（マイクロ秒単位の応答）を満たすことはできない。
ここで登場するのが OPcacheのプリローディング（Preloading） である。
共有メモリ（SHM）上のHashTable配置
PHP 7.4以降で導入されたプリローディングでは、サーバースタートアップ時に指定されたスクリプト群がメモリ上で完全にコンパイルされ、Opcodeの配列（`zend_op_array`）や定数、関数、クラス定義のシンボルテーブル（これらもすべて `HashTable` で管理されている）が、共有メモリ（Shared Memory / SHM）に書き込まれる。
[ Master Process (PHP-FPM) ]
│ 起動時にスクリプトをロード・コンパイル
▼
[ Shared Memory (SHM) ] ── Opcode Arrays, Class Tables (HashTable)
│
├─> [ Worker Process 1 ] (SHMを読み込み専用でアタッチ)
├─> [ Worker Process 2 ] (SHMを読み込み専用でアタッチ)
└─> [ Worker Process 3 ] (SHMを読み込み専用でアタッチ)
このとき、共有メモリ上の `HashTable` 内のポインタは、そのままではプロセスごとに異なるメモリ空間を指してしまうため、Zend Engineはポインタの相対化（Relocation）や、特定のメモリ領域内でのオフセット解決を行っている。
プリローディングされたクラスのプロパティ定義やメソッドマップは、一切の動的な動的アロケーションなしに、プロセス間で完全に共有される。これが、フレームワークのブートストラップコストをほぼゼロにする物理的なメカニズムである。
—
5. セキュリティハックの深層：HashTable衝突攻撃とオブジェクトインジェクション
低レイヤのメモリ構造を知ることは、すなわち「脆弱性の仕組み」を完全に掌握することと同義である。
1. Hash Collision Denial of Service (DoS)
かつて、PHPのハッシュ関数にはアルゴリズム上の弱点（スロット数が固定、あるいは簡易なハッシュ）が存在し、攻撃者が意図的に同じハッシュ値を持つ膨大なクエリパラメータ（例: `?a[0]=1&a[32]=1&a[64]=1…`）を送りつけることで、すべての要素が同一のハッシュチェインに属する最悪のケース（O(N^2)の計算量）を引き起こすことができた。これによりCPU使用率が100%に張り付き、サービスが完全に停止する。
PHP 8での対策:
現在のZend Engineでは、ハッシュ関数に強力なシード（起動時にランダム生成される `DJBX33A` の改良版や、環境に応じたハッシュ）が組み込まれており、外部から衝突を予測して意図的に偏らせることが極めて困難になっている。
2. オブジェクトインジェクションと Gadget Chain のメモリ空間
悪名高い「PHPオブジェクトインジェクション（PHP Object Injection）」は、`unserialize()` 関数にユーザー制御の未サニタイズな文字列が渡されることで発生する。
内部では、`unserialize()` はシリアライズされた文字列を解析し、動的にクラスを復元しながら、そのプロパティを格納するために再び `HashTable` を構築する。
もしアプリケーション内に、危険なマジックメソッド（`__destruct()`, `__wakeup()`, `__toString()` など）を持つクラスが存在する場合、攻撃者はシリアライズされたストリームを巧妙に細工し、逆シリアライズの過程で任意のプロパティに不正な値を注入する。
class ExploitGadget {
private $command;
public function __destruct() {
// 逆シリアライズ完了後のメモリ解放（ガベージコレクション含む）時に実行される
system($this->command);
}
}
Zend VMのメモリ空間において、`unserialize()` は以下のように動作する。
1. ストリームからクラス名を読み込み、内部のクラスエントリ（`zend_class_entry` の `HashTable` から検索）を取得する。
2. オブジェクト用のメモリ領域を `emalloc` で確保し、プロパティ用の `HashTable` を初期化する。
3. ストリーム内のキーと値を、その `HashTable` に順次挿入していく。
4. スコープを抜ける、あるいはスクリプト終了時にオブジェクトの参照カウント（`refcount`）が `0` になると、デストラクタが発動し、内部のプロパティ値がそのまま危険なシステム関数へと流し込まれる。
防衛の基本は「`unserialize()` にユーザー入力を絶対に渡さないこと」であるが、アーキテクトとしての根本的なアプローチは、型安全なDемеシリアライザ（JSONやカスタムパーサー）の採用、あるいはOPcacheの厳格な設定によるシンボルテーブルの保護、そして何よりもセキュアなコーディング規準の徹底にある。
—
6. チーフアーキテクトからの提言
PHPは、もはや「動的型付けの遅いスクリプト言語」ではない。Zend VMのJITコンパイラ、精緻に最適化された `HashTable` とその Packed Array、そしてOPcacheによる共有メモリ管理により、C/C++に近いレベルのメモリ効率とパフォーマンスを手に入れている。
私たちが書く1行のPHPコード、定義する1つの配列が、低レイヤのメモリ空間でどう振る舞っているか。そのイメージを常に脳内でトレースできるエンジニアだけが、真にスケーラブルで堅牢なWebシステムを設計・実装することができる。
メモリの境界を支配し、Zend Engineの限界を突破せよ。これこそが、ハイパフォーマンスPHPアーキテクチャの真髄である。