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


Zend HashTable では、各データ要素 (Bucket) にキーがあります。 HashTable 全体に含まれる名前 (キー) は一意であり、繰り返すことはできません。 HashTable 内のデータ要素は、キー名に基づいて一意に決定できます。キー名の表現方法は 2 つあります。最初の方法では、文字列 arKey をキー名として使用し、文字列の長さは nKeyLength です。上記のデータ構造では、arKey は長さ 1 の単なる文字配列ですが、キーが 1 文字のみであることを意味するわけではないことに注意してください。実際、Bucket は可変長構造体であるため、arKey は Bucket の最後のメンバー変数であるため、nKeyLength の長さのキーは arKey と nKeyLength を組み合わせることで決定できます。これは C 言語プログラミングでは一般的なテクニックです。別のキー名表現方法はインデックス方法です。この場合、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 nTableMask;

ulong nNextFreeElement;ポインタ;

バケット *pListHead; pListTail;
dtor_func_t pDestructor;
unsigned char nApplyCount;
#endif;ハッシュテーブル;



現在のページ 1/3 123次へページ

上記は、ハッシュテーブルの PHP ソース コード解析 Zend HashTable の詳細な説明ページ 1/3 を紹介しており、ハッシュテーブルの内容も含めて、PHP チュートリアルに興味のある友人に役立つことを願っています。