nTableSize このメンバーは、ハッシュ テーブルの初期化操作中に、nTableSize のサイズが設定され、それに応じてこの値のサイズも調整されます。この値はハッシュ テーブル内の要素の数ではないことに注意してください。
nTableMask は「マスク」で、主に要素のインデックス (nIndex = h & ht->nTableMask) を迅速に計算するために使用されます。一般的なハッシュ関数では、インデックスはモジュロ演算を通じて決定されますが、明らかにビット演算の方が効率的です。モジュラー操作より)、arBuckets が初期化された後、この値はデフォルトで nTableSize – 1 に固定されます。
nNumOfElements このメンバーは、ハッシュテーブルに保存される要素の数を保存します。通常、この結果と一致するように PHP スクリプトで count($arr) を使用します (ext/standard/array.c を参照)。
nNextFreeElement このフィールドは、スクリプトで $array[] = 'key' を使用する場合、nNextFreeElement (zend_hash.c) で指定されたインデックス値を使用します。
pInternalPointer これはポインタです。 PHP スクリプトでは、current、next、key、end、およびその他の配列関連の操作を使用する場合、pInternalPointer ポインターを使用して操作を完了します。
pListHead と pListTail PHP の最下層は、実際には 2 つの重要なデータ構造を維持しています。ハッシュ テーブル (および競合を解決するために使用される二重リンク リスト) に加えて、ハッシュ テーブル要素の線形スキャンに使用される二重リンク リストもあります。 pListHead と pListTail は、この二重リンク リストの先頭と末尾を指します。
arBuckets これは、bucket * 型の配列です。配列内の各要素は、bucket* ポインタです。同じハッシュ値を持つ要素は、バケットの pNext ポインタと pLast ポインタを介して二重リンク リストに接続されます (この二重リンク リストは、前のものと同じ) 線形トラバーサルの二重リンク リストは同じものではありません)。したがって、バケットは実際にデータを保存するコンテナーです。
h ,arKey,nKeyLength PHP 配列には 2 つの異なるタイプのインデックスがあります。1 つは数値インデックスで、C の配列 ($arr = array(1=>'cont') など) によく似ています。もう 1 つは数値インデックスです。クラスは文字列インデックスです。つまり、配列項目のインデックスとしてキーワードを使用します ($arr = array('index'=>'cont'); など)。これら 2 種類のインデックスは、異なるメカニズムによって区別されます。 PHP の下部: 数値インデックスの場合、h はハッシュ値として直接使用されます。同時に、arKey=NULL および nKeyLength=0 は文字列インデックスの場合、arKey は文字列キーを保存し、nKeyLength はキーの長さを保存します。ハッシュ関数によって計算されたハッシュ値によって渡される文字列です。このように、PHP では、h、arKey、nKeyLength は配列内の要素を一意に決定するために実際に使用されます。これは、zend_hash_key 構造体の定義からもわかります。
/* 文字列インデックス */
h = zend_inline_hash_func(arKey, nKeyLength);
nIndex = h & ht->nTableMask;
/* 数値インデックスを追加 $arr[] = 'test' このフォーム */
;
if (フラグ & HASH_NEXT_INSERT) {
h = ht->nNextFreeElement;
}
/* 数値インデックスを指定する場合は h を直接使用します */
nIndex = h & ht->nTableMask;
pData と pDataPtr 通常、Bucket 内のデータは、pData ポインタが指すメモリ空間に格納されます。ただし、ポインターの保存などの例外もあります。このとき、pDataPtrはこのポインタを指し、pDataはpDataPtrを指します。これは、INIT_DATA のマクロ定義からわかります:
#define INIT_DATA(ht, p, pData, nDataSize);
if (nDataSize == sizeof(void*)) {
memcpy(&(p)->pDataPtr, pData, sizeof(void *));
(p)->pData=&(p)->pDataPtr;
}else{
(p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);
pefree_rel(p, (ht)->persistent);
F 返品失敗
memcpy((p)->pData,pData,nDataSize);
(p)->pDataPtr=NULL;
}
pListNext と pListLast、pNext と pLast は以前に導入されました。pListNext と pListLast は、トラバーサル用の二重リンク リスト全体を構成します。 pNext と pLast は、ハッシュの競合が発生した場合に、同じハッシュ値を持つバケットをリンクするために使用されます。これら 2 つの二重リンクリストの構造は以下に示すとおりです:
a. ハッシュ競合が発生した場合の二重リンクリスト:
b. グローバルで使用するための二重リンクリスト:
これら 2 つの二重リンクリスト構造は単独で存在するのではなく、相互に関連していることに注意してください。 HashTable の関連操作では、次の 2 つのリンクされたリストを同時に維持する必要があります:
PHP の hashTable は非常に複雑であることがわかります。この複雑さが PHP の配列操作を非常に柔軟にしています (PHP の配列は配列、スタック、キューとして使用でき、非常に便利です)。
3.ハッシュテーブルの実装
1. HashTable関連のマクロ定義
HashTable の操作を容易にするために、PHP は最下位レベルで多くのマクロを定義します。
(1). CONNECT_TO_BUCKET_DLLIST(要素、リストヘッド)
このマクロは、バケットの二重リンク リストの先頭に要素を挿入するために使用されます。つまり、競合が発生した場合、新しく挿入された要素は常にバケットのリンク リストの先頭に配置されます。このマクロの定義は次のとおりです:
#define CONNECT_TO_BUCKET_DLLIST(要素, list_head)
(要素)->pNext = (list_head);
(要素)->pLast = NULL;
if ((要素)->pNext) {
(要素)->pNext->pLast = (要素);
}
(2).CONNECT_TO_GLOBAL_DLLIST(要素、ht)
上記とは異なり、これはグローバルに走査される二重リンクリストの末尾に要素を挿入します。この二重リンクリストはキューのように機能し、配列を走査するときに正しい順序を保証します。このマクロの定義は次のとおりです:
1 #define CONNECT_TO_GLOBAL_DLLIST(element, ht)
2 (要素)->pListLast = (ht)->pListTail;
3 (ht)->pListTail = (要素);
4 (要素)->pListNext = NULL;
5 if ((要素)->pListLast != NULL) {
6 (要素)->pListLast->pListNext = (要素);
7 }
8
9 if (!(ht)->pListHead) {
10 (ht)->pListHead = (要素);
11 }
12
13 if ((ht)->pInternalPointer == NULL) {
14 (ht)->pInternalPointer = (要素);
15 }
(3).HASH_PROTECT_RECURSION(ht)
このマクロは主に、ハッシュテーブルが再帰的に走査されるときに深すぎるのを防ぐために使用されます
。
#define HASH_PROTECT_RECURSION(ht)
if ((ht)->bApplyProtection) {
if ((ht)->nApplyCount++ >= 3) {
zend_error(E_ERROR, "ネストレベルが深すぎます - 再帰的な依存関係?");
}
}
(4).ZEND_HASH_IF_FULL_DO_RESIZE(ht)
HashTable のサイズは固定されていません。nNumOfElements > nTableSize の場合、より多くの要素を収容できるように HashTable が拡張されます (実際には、zend_hash_do_resize を呼び出すことで実現されます)。マクロは次のように定義されます:
#define ZEND_HASH_IF_FULL_DO_RESIZE(ht)
if ((ht)->nNumOfElements > (ht)->nTableSize) {
zend_hash_do_resize(ht);
}
(5).INIT_DATA(ht、p、pData、nDataSize)
ここには実際には 2 つの状況があります。保存されるデータ自体がポインターである場合、pDataPtr はポインターを保存し、pData を pDataPtr のアドレスにポイントします。
if (nDataSize == sizeof(void*)) {
memcpy(&(p)->pDataPtr, pData, sizeof(void *));
(p)->pData = &(p)->pDataPtr;
}
それ以外の通常のデータを保存する場合は、nDataSize バイトのメモリ割り当てを申請し、pData が指す内容を p->pData のメモリにコピーします。ここで、コピーは memcpy を通じて実行されます。その src ポインターと dest ポインターが両方とも void * であるため、ほぼすべてのタイプのデータをコピーできます。
その他 {
(p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);
if (!(p)->pData) {
pefree_rel(p, (ht)->persistent);
返品失敗;
}
memcpy((p)->pData, pData, nDataSize);
(p)->pDataPtr=NULL;
}
マクロ全体は次のように定義されます:
#define UPDATE_DATA(ht, p, pData, nDataSize)
if (nDataSize == sizeof(void*)) {
pefree_rel((p)->pData, (ht)->persistent);
memcpy(&(p)->pDataPtr, pData, sizeof(void *));
を使用
(p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);
(p)->pDataPtr=NULL;
(p)->pData = (void *) perrealloc_rel((p)->pData, nDataSize, (ht)->persistent);
/* (p)->pDataPtr はすでに NULL なので初期化する必要はありません */
memcpy((p)->pData, pData, nDataSize);
}
(6).UPDATE_DATA(ht, p, pData, nDataSize)
INIT_DATA と同様、違いは、前のメモリ ブロックでさらに処理を行う必要があることです (たとえば、実際のデータは以前に pData によって保存されましたが、ポインタは更新後に保存され、元々適用されていたメモリは解放される必要があり、そうでない場合)逆に、ポインタデータが以前に保存され、通常のデータが更新後に保存される場合は、pDataPtr を NULL に設定し、pData に新しいメモリ領域を割り当てる必要があります。このマクロの定義は次のとおりです。
#define UPDATE_DATA(ht, p, pData, nDataSize)
if (nDataSize == sizeof(void*)) {
pefree_rel((p)->pData, (ht)->persistent);
memcpy(&(p)->pDataPtr, pData, sizeof(void *));
を使用
(p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);
(p)->pDataPtr=NULL;
(p)->pData = (void *) perrealloc_rel((p)->pData, nDataSize, (ht)->persistent);
/* (p)->pDataPtr はすでに NULL なので初期化する必要はありません */
memcpy((p)->pData, pData, nDataSize);
}
(7).CHECK_INIT(ht)
_zend_hash_init() を呼び出してハッシュ テーブルを初期化した後、arBuckets は実際にはメモリ領域を割り当てず、nTableMask の値は設定されません。 CHECK_INIT は、arBuckets が初期化されているかどうかを確認します (nTableMask==0 は初期化されていないことを意味します)。初期化されていない場合は、arBuckets にメモリ領域を割り当て、nTableMask の値を nTableSize - 1 に設定します。マクロは次のように定義されます。
#define CHECK_INIT(ht) do {
if (UNEXPECTED((ht)->nTableMask == 0)) {
(ht)->arBuckets = (Bucket **) pecalloc((ht)->nTableSize, sizeof(Bucket *), (ht)->persistent
& (ht)-& gt; ntableMask = (ht)-& gt;
}
} しながら (0)
2.ハッシュ関数
この記事を書いているときに、Niao 兄弟がすでに「PHP のハッシュ アルゴリズム」という記事を書いていることに気づきました。この記事では、ハッシュ アルゴリズムとアイデアについてより詳細な回答が得られました。ここではあまり説明しません。 ：展開された状態。アンロール自体は展開を意味します。nKeyLength の長さのキーの場合、PHP のハッシュ アルゴリズムは次の形式で 8 単位で展開されます。
for (; nKeyLength >= 8; nKeyLength -= 8) {
ハッシュ = ((ハッシュ
ハッシュ = ((ハッシュ
ハッシュ = ((ハッシュ
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
