PHPソースコード解析 Zend HashTable 詳細解説 1/3ページ

HashTable は、一般的なデータ構造の教科書ではハッシュ テーブルまたはハッシュ テーブルとも呼ばれます。基本原理は比較的単純ですが (詳しくない場合は、データ構造の教科書を参照するか、オンラインで検索してください)、PHP の実装には独自の特徴があります。 HashTable のデータ ストレージ構造を理解することは、PHP のソース コード、特に Zend Engine での仮想マシンの実装を分析するときに非常に役立ちます。これは、脳内で完全な仮想マシンのイメージをシミュレートするのに役立ちます。これは、配列などの PHP の他のデータ構造の実装の基礎でもあります。
Zend HashTable の実装は、二重リンク リストとベクトル (配列) という 2 つのデータ構造の利点を組み合わせ、PHP に非常に効率的なデータ ストレージとクエリ メカニズムを提供します。
始めましょう!
1. HashTable のデータ構造
Zend Engine の HashTable の実装コードには、主に zend_hash.h と zend_hash.c の 2 つのファイルが含まれています。 Zend HashTable には 2 つの主要なデータ構造が含まれており、1 つは Bucket 構造、もう 1 つは HashTable 構造です。 Bucket 構造はデータを保存するために使用されるコンテナであり、HashTable 構造はこれらすべての Bucket (またはバケット列) を管理するメカニズムを提供します。

コードをコピーします コードは次のとおりです。

typedef structbucket {
ulong h; /* 数値に使用されます。インデックス作成 */
uint nKeyLength; /* キーの長さ */
void *pData; /* バケットに保存されたデータへのポインタ */
void *pDataPtr; structbucket * pListNext; /* HashTable バケット列の次の要素を指します*/
structbucket *pListLast; /* HashTable バケット列の前の要素を指します*/
structbucket *pNext; * 同じハッシュ値を指すバケット列の次の要素*/
structbucket *pLast; /* 同じハッシュ値を持つバケット列の前の要素を指す*/
char arKey[1] ; /* 最後のメンバーである必要があります、キー名*/
} Bucket

Zend HashTable では、各データ要素 (Bucket) に一意のキー名 (key) があります。 HashTable 全体を繰り返すことはできません。 HashTable 内のデータ要素は、キー名に基づいて一意に決定できます。キー名を表す方法は 2 つあります。最初の方法では、文字列 arKey をキー名として使用し、文字列の長さは nKeyLength です。上記のデータ構造では、arKey は長さ 1 の単なる文字配列ですが、キーが 1 文字のみであることを意味するわけではないことに注意してください。実際、Bucket は可変長構造体であるため、arKey は Bucket の最後のメンバー変数であるため、nKeyLength の長さのキーは arKey と nKeyLength を組み合わせることで決定できます。これは C 言語プログラミングでは一般的なテクニックです。キー名を表すもう 1 つの方法はインデックス メソッドです。この場合、nKeyLength は常に 0 であり、長整数フィールド h がデータ要素のキー名を表します。簡単に言うと、nKeyLength=0 の場合、キー名は h であり、それ以外の場合、キー名は arKey であり、キー名の長さは nKeyLength です。
nKeyLength > 0 の場合、このときの h の値が無意味になるわけではありません。実はこのとき保存されるのはarKeyに対応するハッシュ値です。ハッシュ関数がどのように設計されていても、競合は避けられません。つまり、異なる arKey が同じハッシュ値を持つ可能性があります。同じハッシュ値を持つバケットは、HashTable の arBuckets 配列の同じインデックスに対応するバケット列に格納されます (以下の説明を参照)。このバケット列は二重リンクリストであり、その前方要素と後方要素はそれぞれ pLast と pNext で表されます。新しく挿入されたバケットは、バケット列の前面に配置されます。
Bucket では、実際のデータは pData ポインタが指すメモリ ブロックに格納されます。通常、このメモリ ブロックはシステムによって個別に割り当てられます。ただし、例外があります。つまり、バケットによって保存されたデータがポインターの場合、HashTable はシステムにポインターを保存するためのスペースの割り当てを要求せず、ポインターを pDataPtr に直接保存し、pData をメンバーにポイントします。この構造の。これにより効率が向上し、メモリの断片化が軽減されます。このことから、PHP HashTable の設計の微妙な点がわかります。 Bucket 内のデータがポインターでない場合、pDataPtr は NULL になります。
HashTable 内のすべてのバケットは、pListNext と pListLast を通じて二重リンク リストを形成します。最後に挿入されたバケットは、この二重リンク リストの最後に配置されます。
一般に、Bucket は保存するデータのサイズに関する情報を提供できないことに注意してください。したがって、PHP の実装では、Bucket に保存されるデータには、独自のサイズを管理する機能が必要です。

コードをコピーします コードは次のとおりです。

typedef struct _hashtable {
uint nTableSize
uint nTableMask; ;
uint nNumOfElements;
Bucket *pListHead;
zend_bool; 🎜 >#if ZEND_DEBUG
int inconsistent;
#endif
} ハッシュテーブル