PHPの『HashTable』における衝突回避戦略：DJBX33Aハッシュ関数の特性と衝突攻撃への耐性
PHPの配列（Array）は、言語の仕様として「連想配列であり、かつ順序付きマップであり、かつベクタ（リスト）である」という極めて欲張りなデータ構造として実装されている。この多面的な振る舞いを、Zend Engineの内部において単一のデータ構造で支えているのが `HashTable` だ。
Webアプリケーションにおいて、リクエストごとに数千、数万の連想配列操作が行われる。この `HashTable` の根幹を揺るがす脅威が 「ハッシュ衝突（Hash Collision）攻撃」 である。最悪の場合、計算量のオーダーが $O(1)$（または平均 $O(N)$）から $O(N^2)$ へと跳ね上がり、CPUコアを100%占有したままリクエストが雪崩を打ってタイムアウトする――いわゆる DoS攻撃（Hash DoS） の温床となる。
本稿では、Zend VMがこの悪意ある攻撃に対してどのように対抗しているのか、DJBX33Aハッシュ関数の特性、ハッシュシードのランダム化、そしてメモリ上の物理構造に至るまで、低レイヤの視点から徹底的に解剖する。
—
1. Zend Engineにおける `HashTable` の物理構造とメモリ空間
PHPの配列やシンボルテーブル（関数、クラス、定数の定義を保持するグローバルなハッシュ）は、すべて内部的には `Bucket` 構造体の配列と、インデックスを高速に引き当てるための `nTableMask`（実質的なハッシュバケットのインデックス計算用ビットマスク）によって構成されている。
C言語レベルでの `Bucket` と `HashTable` の概念を疑似的な構造体で表現すると、以下のようになる。
/ Zend Engine内部の概念に近い構造体イメージ /
typedef struct _bucket {
zend_ulong h; // ハッシュ値（または数値インデックス）
zend_string key; // 文字列キー（数値インデックスの場合はNULL）
zval val; // 格納される値（zvalコンテナ）
} Bucket;
typedef struct _hashtable {
uint32_t nTableSize; // バケット全体のサイズ（2のべき乗にパディングされる）
uint32_t nTableMask; // nTableSize – 1 （ビットマスク用）
uint32_t nNumUsed; // 使用済みバケット数
uint32_t nNumOfElements; // 有効な要素数
zend_ulong nInternalPointer;
zend_long nNextFreeElement;
uint32_t arHash; // ハッシュ衝突チェーンをたどるためのインデックス配列
Bucket arData; // 実際のデータが連続して配置されるメモリ領域
// … (dtor, その他フラグやプリンタブル用のメタデータが続く)
} HashTable;
Zend VMがキーから値を取り出すとき、まずキー文字列を特定のハッシュ関数にかけ、得られたハッシュ値に `nTableMask` をビット単位の論理積（AND）で適用してバケットのインデックスを算出する。もし複数の異なるキーが同一のインデックスに帰結した場合、これが ハッシュ衝突 である。
—
2. DJBX33Aハッシュ関数とその特性
PHP（Zend Engine）は、文字列キーのハッシュ値を計算するために、Daniel J. Bernstein氏が考案した `DJBX33A`（Bernsteinハッシュ） の変種を採用している。
このアルゴリズムのC言語レベルでの実装は非常にシンプルで、以下のループ構造を持つ。
/ Zend Engine内部におけるDJBX33Aの実装原理 /
static zend_always_inline zend_ulong zend_inline_hash_func(const char str, size_t len)
{
zend_ulong hash = 5381;
for (size_t i = 0; i < len; i++) { / hash 33 + c / hash = ((hash << 5) + hash) + (unsigned char)str++; } return hash; }
なぜ `33` なのか？
- `hash 33` は、ビット演算に置き換えると `(hash << 5) + hash` となり、CPUのシフト演算と加算命令だけで高速に処理できる。
- 数学的な特性として、乗数 33 は衝突率が低く、かつ短時間で文字列全体のエントロピーを適切に混合（mixing）させることができる。
しかし、このアルゴリズムには致命的な弱点がある。「入力文字列のパターンを計算機で解析すれば、意図的に同一のハッシュ値を生成する異なる文字列（コリジョンペア）を無限に量産できる」という点だ。これが、かつて多くの言語を震撼させた Hash DoS の根本原因である。
—
3. ハッシュシードのランダム化による衝突攻撃への耐性
この脆弱性に対し、Zend Engineは 「ハッシュシードのランダム化（Hash Seed Randomization）」 という堅牢な防御機構を備えている。
PHPが起動し、SAPIライフサイクルが開始される際（`MINIT` フェーズ）、Zend EngineはOSのエントロピープール（`/dev/urandom` や CryptGenRandom など）から十分なランダムネスを取得し、プロセスごとに一意の ハッシュシード（`CG(hash_secret)`） を生成する。
[文字列キー] + [プロセス固有のランダムシード]
↓
DJBX33A関数の実行
↓
[予測不可能なハッシュ値] → DoS攻撃の無力化
攻撃者が直面する壁
攻撃者が「数万個のコリジョンを起こすキー群」をローカル環境で事前にどれだけ精密に計算したとしても、それらのキーが実際に本番環境のPHPプロセス（PHP-FPMのワーカーなど）に到達した瞬間、エンジン側でシードが加算・混合されるため、攻撃者が意図した通りのハッシュ衝突を再現することは完全に不可能になる。
もし無理やり衝突を引き起こそうとすれば、攻撃者はプロセスごとのランダムシードの値を総当たりで推測しなければならないが、これは物理的に不可能な時間計算量を要求する。これが、近代PHPにおけるハッシュ衝突耐性の核心である。
—
4. OPcacheプリローディングと HashTable の物理構造の永続化
この堅牢な `HashTable` の仕組みは、JITやOPcacheの世界においても極めて重要な役割を果たしている。特に `opcache.preload` を用いたプリローディング機構では、スクリプトのパース結果（AST）だけでなく、クラス定義のシンボルテーブル（これも `HashTable` である）が共有メモリ（SHM: Shared Memory）上にそのまま構築される。
/
declare(strict_types=1);
namespace Core\Architecture;
class EngineOptimizer {
public function inspectHashTableIntegrity(array $symbolTable): void
{
// 共有メモリ上のHashTableは、プロセス起動時にシードが固定されるため、
// 読み取り専用（ReadOnly）セグメントとして各FPMワーカーからマッピングされる。
// これにより、リクエストごとのハッシュ計算コストがゼロになる。
}
}
OPcacheが有効な環境下では、不変のクラスプロパティやメソッドのルックアップは、既にハッシュ化され最適化された `HashTable` のスロットを直接参照するため、Zend VMの実行レイテンシは劇的に低下する。
—
5. 実践：PHP配列の挙動を低レイヤから監視するコード
百聞は一見にしかず。PHPの配列内部で何が起きているのか、メモリ消費とキーの順序保証の観点から検証するコードを以下に示す。
/
// 1. 大量のキーを動的に生成し、内部的なバケット再割当て（Rehashing）を誘発する
$startMemory = memory_get_usage(true);
$array = [];
// 連続した整数インデックスではなく、文字列キーを大量に投入
for ($i = 0; $i < 100000; $i++) {
// プレフィックスを付与することで、DJBX33Aハッシュ関数を通した際の分散を促す
$array['key_prefix_' . $i] = $i;
}
$peakMemory = memory_get_peak_usage(true);
echo "--- Zend HashTable Memory Profiling ---\n";
echo "初期メモリ消費: " . number_format($startMemory) . " bytes\n";
echo "ピークメモリ消費: " . number_format($peakMemory) . " bytes\n";
echo "配列の要素数: " . count($array) . "\n";
// 2. 順序付きマップとしての振る舞いの確認
// 最初の要素と最後の要素を取り出し、内部ポインタの整合性を確認
reset($array);
$firstKey = key($array);
end($array);
$lastKey = key($array);
echo "先頭キー: {$firstKey}\n";
echo "末尾キー: {$lastKey}\n";
コードの低レイヤ解説
このスクリプトを実行すると、10万個のエントリを持つ `HashTable` が動的に構築される。
1. `nTableSize` は要素数の増加に伴い、自動的に2のべき乗（この場合は `131072` など）に拡張（Rehash）される。
2. キー文字列はすべて内部的に `zend_string` として管理され、参照カウント（`gc_refcount`）によって効率的に共有・管理される。
3. もしここで悪意あるスクリプトがハッシュ衝突を狙ったキーを投入しようとしても、前述のランダムシードにより、最悪計算量 $O(N^2)$ への陥落は防がれる。しかし、衝突回数が許容値を超えて連鎖（Collision Chaining）が発生した場合、バケットの走査コスト（線形探索の深度）がわずかに増加する。高負荷なシステムにおいては、外部からの入力値がそのまま配列のキーになるような実装（例：`$_GET` をそのままキーとして巨大な配列を構築するなど）を避けることが、アーキテクトとしての最低限の防衛ラインとなる。
—
6. チーフアーキテクトからの総括
PHPの `HashTable` と DJBX33A ハッシュ関数の関係、そしてハッシュシードのランダム化は、単なる「便利なデータ構造の実装」にとどまらない。それは、Webという不特定多数からの入力を受け付ける最前線において、言語ランタイムが自律的にセキュリティとパフォーマンスの均衡を保つための 要塞（Citadel） である。
我々エンジニアは、フレームワークが提供する抽象化されたAPIの背後で、Zend VMが毎秒数百万回のハッシュ計算とメモリ管理をいかに高速に、かつ安全に完遂しているかを知らなければならない。低レイヤの物理構造を脳内でトレースできる者だけが、真にスケーラブルで堅牢なWebシステムアーキテクチャを構築できるのだ。