PHP_PHPチュートリアルのHashTable構造の詳細な説明-PHPチュートリアル-php.cn

HashTable は、Zend エンジンで最も重要で広く使用されているデータ構造で、ほぼすべてのものを保存するために使用されます。
1.2.1 データ構造
HashTable データ構造は次のように定義されます:

コードをコピーコードは次のとおりです:

typedef structbucket {
ulong h; // Store hash
uint; nKeyLength;
void * pData; // ユーザーデータのコピーである value を指します
void *pDataPtr;
struct Bucket *pListNext; // pListNext と pListLast は
struct Bucket で構成されます *pListLast;二重リンクリスト
structbucket *pNext; // pNext と pLast は二重リンクリストを形成するために使用されます
char arKey[1] // key
} Bucket;
対応する特定のハッシュ用 struct Bucket *pLast;

typedef struct _hashtable {
uint nTableSize;
uint nTableMask;
uint nNumOfElements;
ulong nNextFreeElement;
Bucket *pInternalPointer; /* 要素の走査に使用 */
Bucket *pListHead;
Bucket *pListTail;など。 // ハッシュ配列
dtor_func_t pDestructor; // HashTable の初期化時に指定し、Bucket を破棄する際に zend_bool を呼び出します。 // C のメモリ割り当てルーチンを使用するかどうか
unsigned char nApplyCount
#if ZEND_DEBUG
int inconsistent;
#endif
} HashTable;

一般に、Zend の HashTable は、以下に示すように、線形トラバーサル用にも最適化されたリンクリストハッシュです。

HashTable には、リンクリストハッシュと二重リンクリストの 2 つのデータ構造が含まれており、前者は高速なキーと値のクエリに使用され、後者は両方のデータ構造に存在します。同時。

このデータ構造に関するいくつかの説明:

なぜリンクリストハッシュで二重リンクリストが使用されるのですか? 一般的なリンクリストのハッシュ化はキーで操作するだけで済み、リンクリストは 1 つだけで十分です。ただし、Zend はリンクリストのハッシュから特定のバケットを削除する必要がある場合があります。これは、二重リンクリストを使用すると非常に効率的に実行できます。
nTableMask は何をしますか?
この値は、ハッシュ値を arBuckets 配列のインデックスに変換するために使用されます。 HashTable を初期化するとき、Zend はまず arBuckets 配列に nTableSize サイズのメモリを割り当てます。nTableSize はユーザー指定のサイズの最小値 2^n (バイナリで 10*) 以上です。 nTableMask = nTableSize – 1、これはバイナリ 01* です。このとき、h & nTableMask はたまたま [0, nTableSize – 1] に該当し、Zend はそれを arBuckets 配列にアクセスするためのインデックスとして使用します。
pDataPtr は何をしますか?
通常、ユーザーがキーと値のペアを挿入すると、Zend は値のコピーを作成し、pData がその値のコピーを指すようにします。コピー操作では、Zend の内部ルーチン emalloc を呼び出してメモリを割り当てる必要があります。これは非常に時間がかかり、値よりも大きなメモリを消費します (値が小さい場合は、余分なメモリが使用されます)。大きな無駄。 HashTable は主にポインタ値を格納するために使用されることを考慮して、値がポインタと同じくらい小さい場合、Zend はそれを pDataPtr に直接コピーし、pData を pDataPtr にポイントします。これにより emalloc 操作が回避され、キャッシュヒット率の向上にも役立ちます。
arKey サイズが 1 だけなのはなぜですか?ポインタを使用してキーを管理してみてはいかがでしょうか?
arKey はキーを格納する配列ですが、そのサイズは 1 のみで、キーを保持するには十分ではありません。次のコードは HashTable の初期化関数にあります:

コードをコピー

コードは次のとおりです: p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht-> ;しつこい);

可见，Zend为一个Bucket分配了一块足够放下自己和key的内存，上半部分是Bucket，下半部分是key，而arKey“恰好”是Bucket的最后一个元素，于是就可以使用arKey来访问key了。这种手法在内存管理例程中最为常见，当分配内存时，实际上是分配了比指定大小要大的内存，多出的上半部分通常被称为cookie，它存储了这块内存的信息，比如块大小、上一块指针、下一块指针等，baidu的Transmit程序就使用了这种方法。
不用指针管理key，是为了减少一次emalloc操作，同时也可以提高Cache命中率。另一个必需的理由是，key绝大部分情况下是固定不变的，不会因为key变长了而导致重新分配整个Bucket。这同时也解释了为什么不把value也一起作为数组分配了——因为value是可变的。

1.2.2 PHP数组
关于HashTable还有一个疑问没有回答，就是nNextFreeElement是干什么的？
不同于一般的散列，Zend的HashTable允许用户直接指定hash值，而忽略key，甚至可以不指定key（此时，nKeyLength为0）。同时，HashTable也支持append操作，用户连hash值也不用指定，只需要提供value，此时，Zend就用nNextFreeElement作为hash，之后将nNextFreeElement递增。
HashTable的这种行为看起来很奇怪，因为这将无法按key访问value，已经完全不是个散列了。理解问题的关键在于，PHP数组就是使用HashTable实现的——关联数组使用正常的k-v映射将元素加入HashTable，其key为用户指定的字符串；非关联数组则直接使用数组下标作为hash值，不存在key；而当在一个数组中混合使用关联和非关联时，或者使用array_push操作时，就需要用nNextFreeElement了。
再来看value，PHP数组的value直接使用了zval这个通用结构，pData指向的是zval*，按照上一节的介绍，这个zval*将直接存储在pDataPtr里。由于直接使用了zval，数组的元素可以是任意PHP类型。
数组的遍历操作，即foreach、each等，是通过HashTable的双向链表来进行的，pInternalPointer作为游标记录了当前位置。

1.2.3 变量符号表
除了数组，HashTable还被用来存储许多其他数据，比如，PHP函数、变量符号、加载的模块、类成员等。
一个变量符号表就相当于一个关联数组，其key是变量名（可见，使用很长的变量名并不是个好主意），value是zval*。
在任一时刻PHP代码都可以看见两个变量符号表——symbol_table和active_symbol_table——前者用于存储全局变量，称为全局符号表；后者是个指针，指向当前活动的变量符号表，通常情况下就是全局符号表。但是，当每次进入一个PHP函数时（此处指的是用户使用PHP代码创建的函数），Zend都会创建函数局部的变量符号表，并将active_symbol_table指向局部符号表。Zend总是使用active_symbol_table来访问变量，这样就实现了局部变量的作用域控制。
但如果在函数局部访问标记为global的变量，Zend会进行特殊处理——在active_symbol_table中创建symbol_table中同名变量的引用，如果symbol_table中没有同名变量则会先创建。

1.3 メモリとファイル
プログラムが所有するリソースには通常、メモリとファイルが含まれます。通常のプログラムの場合、これらのリソースはプロセスが終了すると、オペレーティングシステムまたは C ライブラリによって自動的にリサイクルされます。リソースを明示的に解放していません。
ただし、PHP プログラムはページに基づいており、ページの実行が終了すると、メモリやファイルにも適用されます。リソースをリサイクルする必要があることを知りません。たとえば、php をモジュールとして Apache にコンパイルし、Apache をプリフォークモードまたはワーカーモードで実行します。この場合、Apache プロセスまたはスレッドが再利用され、php ページによって割り当てられたメモリは、コアが解放されるまでメモリ内に残ります。
この問題を解決するために、Zend は一連のメモリ割り当て API を提供しています。それらの関数は C の対応する関数と同じです。違いは、これらの関数が Zend 独自のメモリプールからメモリを割り当て、自動リサイクルベースを実装できることです。ページ上で。私たちのモジュールでは、ページに割り当てられたメモリは C ルーチンの代わりにこれらの API を使用する必要があります。そうしないと、Zend がページの最後でメモリを解放しようとし、その結果、通常はクラッシュが発生します。
emalloc()
efree()
estrdup()
estrndup()
ecalloc()
erealloc()
さらに、Zend は、C ライブラリと対応するファイル API を置き換える VCWD_xxx 形式のマクロのセットも提供しますオペレーティングシステムの場合、これらのマクロは PHP の仮想作業ディレクトリをサポートしており、常にモジュールコードで使用する必要があります。マクロの具体的な定義については、PHPソースコード「TSRM/tsrm_virtual_cwd.h」を参照してください。これらすべてのマクロで close 操作が提供されていないことに気づくかもしれません。これは、close のオブジェクトがオープンされたリソースであり、ファイルパスを含まないためです。そのため、同様に C またはオペレーティングシステムのルーチン、read/Operations を直接使用できます。 write などでは、C またはオペレーティングシステムのルーチンを直接使用することもできます。