ハッシュテーブルは、あらゆる深刻なCプログラムで、あらゆる場所で使用されます。 基本的に、プログラマは文字列でインデックスを作成して値を「配列」に格納できますが、Cでは整数配列キーのみが許可されます。 ハッシュテーブルでは、小文字のキーが最初にハッシュされ、次にテーブルのサイズに縮小されます。 ここでは衝突が発生する可能性があるため、衝突を解決するアルゴリズムが必要です。 同様のアルゴリズムがいくつかあり、PHPはリンクリスト戦略を使用します。

Web上には、ハッシュテーブルの構造とその実装について詳しく説明している素晴らしい記事がたくさんあります。 http://preshing.com/から始めることができます。 ただし、無数のハッシュテーブル構造のオプションがあり、それらのいずれも完全ではなく、プロセッササイクル、メモリ使用量、またはスレッド環境の適切なスケーリングの最適化にもかかわらず、それぞれにトレードオフがあります。 データを追加する場合はより良いオプション、検索する場合は他のオプションなどがあります。より重要なものに応じて実装を選択します。

PHP 5のハッシュテーブルについては、PHP 7のハッシュテーブルに関する優れた記事の著者であるNikicと一緒に書いたphpinternalsbookで詳しく説明されています。 おそらくあなたもそれを面白いと思うでしょう。 確かに、それはリリースの前に書かれたので、その中のいくつかのものはわずかに異なります。

ここでは、PHP 7でハッシュテーブルがどのように配置されるか、C言語の観点からハッシュテーブルを操作する方法、およびPHPツールを使用して（配列と呼ばれる構造を使用して）ハッシュテーブルを管理する方法を詳しく見ていきます。 ソースコードのほとんどはzend_hash.cで入手できます。 ハッシュテーブルはどこでも（通常は辞書として）使用することを忘れないでください。したがって、プロセッサですばやく処理され、メモリをほとんど消費しないように設計する必要があります。 ハッシュテーブルが使用される場所はローカル配列だけではないため、これらの構造はPHPの全体的なパフォーマンスに決定的な影響を及ぼします。

ハッシュテーブルの設計

以下で詳細に検討する多くの規定があります。

• キーは文字列または整数です。 zend_string場合はzend_string構造がzend_string 、 zend_string場合はzend_stringがzend_stringます。
• ハッシュテーブルは、要素が追加される順序を常に記憶している必要があります。
• ハッシュテーブルのサイズは自動的に変更されます。 状況に応じて、独立して減少または増加します。
• 内部実装の観点から見ると、テーブルのサイズは常に2度に等しくなります。 これは、パフォーマンスを改善し、メモリ内のデータ配置を調整するために行われます。
• ハッシュテーブル内のすべての値は、他の場所ではなく、 zval構造に格納されます。 Zvalは、任意のタイプのデータを含めることができます。

HashTable構造について考えてみましょう。

 struct _zend_array { zend_refcounted_h gc; union { struct { ZEND_ENDIAN_LOHI_4( zend_uchar flags, zend_uchar nApplyCount, zend_uchar nIteratorsCount, zend_uchar reserve) } v; uint32_t flags; /*  32  */ } u; uint32_t nTableMask; /*  — nTableSize */ Bucket *arData; /*    */ uint32_t nNumUsed; /*     arData */ uint32_t nNumOfElements; /*      arData */ uint32_t nTableSize; /*  ,      */ uint32_t nInternalPointer; /*    */ zend_long nNextFreeElement; /*     */ dtor_func_t pDestructor; /*   */ }; 

一部のフィールドはめったに使用されないため、それらについては説明しません。

この構造のサイズは56バイトです （LP64モデルによる）。

最も興味深いデータフィールドは、 Bucketチェーンのメモリ領域へのポインタの一種であるarDataです。 Bucket自体は配列内の単一のセルです。

 typedef struct _Bucket { zval val; /*  */ zend_ulong h; /*  (  ) */ zend_string *key; /*    NULL    */ } Bucket; 

お気づきかもしれませんが、 zvalはBucket構造に保存されます。 これはzvalへのポインタではなく、構造自体であることに注意してください。 これは、PHP 7ではzvalがヒープに配置されなくなったためです（PHP 5とは異なります）が、PHP 7では、 zvalポインターとして保存されたターゲット値（PHP文字列など）を配置できます。

メモリ内の配置がどのように発生するかを見てみましょう。



ご覧のとおり、ハッシュテーブルに配置されたデータは、隣接するメモリセクションarData保存されます。

順序を維持しながらアイテムを追加する

PHPは、要素が配列に追加されるときに要素の順序を維持する必要があります。 foreachを配列に適用すると、キーに関係なく、配列に配置された正確な順序でデータを受け取ります。

 $a = [9=>"foo", 2 => 42, []]; var_dump($a); array(3) { [9]=> string(3) "foo" [2]=> int(42) [10]=> array(0) { } } 

これは、ハッシュテーブルの実装に多くの制限を課した重要なポイントです。 すべてのデータは、互いに隣り合うメモリに配置されます。 zvalでは、 arData C-arrayのフィールドにあるBucketパックされて格納されます。 このようなもの：

 $a = [3=> 'foo', 8 => 'bar', 'baz' => []]; 

このアプローチのおかげで、ハッシュテーブルを簡単に反復できますarData配列をarDataだけです。 本質的に、これはメモリの迅速な順次スキャンであり、プロセッサキャッシュリソースをほとんど消費しません。 arDataからのすべてのデータは1行に配置でき、各セルへのアクセスには約1ナノ秒かかります。 注：プロセッサキャッシュの使用効率を高めるために、 arData 64ビットモデルに従ってアライメントされます（64ビットフル命令のアライメントの最適化も使用されます）。 ハッシュテーブルの反復コードは次のようになります。

 size_t i; Bucket p; zval val; for (i=0; i < ht->nTableSize; i++) { p = ht->arData[i]; val = p.val; /*  -   val */ } 

データはソートされ、次のarDataセルに渡されます。 この手順を完了するには、 nNumUsedフィールドに格納されている、この配列で次に使用可能なセルを覚えておいてnNumUsed 。 新しい値が追加されるたびに、 ht->nNumUsed++を追加しht->nNumUsed++ 。 nNumUsedの要素数がハッシュテーブルの要素数（ nNumOfElements ）に達すると、コンパクトアルゴリズムまたはサイズ変更アルゴリズムを実行します。これについては以下で説明します。

文字列キーを使用してハッシュテーブルにアイテムを追加する簡略化されたビュー：

 idx = ht->nNumUsed++; /*      */ ht->nNumOfElements++; /*    */ /* ... */ p = ht->arData + idx; /*     bucket  arData */ p->key = key; /*  ,     */ /* ... */ p->h = h = ZSTR_H(key); /*   bucket    */ ZVAL_COPY_VALUE(&p->val, pData); /*     bucket':   */ 

値を消去

値を削除しても、 arData配列arData減少したり再配列arDataたりarDataん。 そうしないと、メモリ内のデータを移動する必要があるため、パフォーマンスが劇的に低下します。 そのため、ハッシュテーブルからデータを削除する場合、 arDataの対応するセルは、 zval UNDEFという特別な方法で単純にマークされます。



したがって、このような「空の」セルを処理できるように、反復コードを少し再構築する必要があります。

 size_t i; Bucket p; zval val; for (i=0; i < ht->nTableSize; i++) { p = ht->arData[i]; val = p.val; if (Z_TYPE(val) == IS_UNDEF) { continue; } /*  -   val */ } 

以下では、ハッシュテーブルのサイズが変更されたときに何が起こるか、および「空の」セルが消えるようにarData配列を再編成する必要があります（圧縮）。

キーハッシュ

キーはハッシュおよび圧縮され、圧縮されたハッシュ値から変換されてarDataインデックス付けされるarDataます。 キーは整数であっても圧縮されます。 これは、配列の境界に収まるようにするために必要です。

arData直接あるように、圧縮された値にインデックスをarDataことはできないことにarDataしてarData 。 結局、これは配列のインデックスに使用されるキーがハッシュから取得したキーに直接対応することを意味します。これは、PHPのハッシュテーブルのプロパティの1つ、要素の順序の保持に違反します。

たとえば、最初にfooキーを追加し、次にbarキーを追加すると、最初のキーはハッシュされてキー5に圧縮され、2番目のキーはキー3に圧縮されますarData[5]データがarData[5] arData[3] 、データバーがデータfooに移動することがわかります。 また、 arData反復処理する場合arData要素は追加された順序ではなく転送されます。



したがって、割り当てられたarData境界に収まるように、キーをハッシュしてから圧縮します。 ただし、PHP 5とは異なり、そのまま使用しません。最初に変換テーブルを使用してキーを変換する必要があります。 ハッシュ/圧縮によって取得された1つの整数値と、 arData配列内のアドレス指定に使用される別の整数値を単純に比較します。

注意点が1つあります。変換テーブルのメモリは、 arDataベクトルの背後に慎重に配置されます。 これarDataテーブルはすでにarData隣にarDataれており、同じアドレス空間に残っているため、テーブルが別のメモリ領域を使用するarDataます。 これにより、データの局所性が向上します。 これは、8要素のハッシュテーブル（可能な最小サイズ）の場合に説明されたスキームがどのように見えるかです：



これで、fooキーはDJB33Xでハッシュされ、必要なサイズ（ nTableMask ）にモジュロ圧縮されます。 結果の値は、（直接セルではなく） arData 変換 arDataにアクセスするために使用できるインデックスです。

これらのセルは、 arData開始位置からの負のシフトによってアクセスされます。 2つのメモリ領域が結合されたため、メモリにデータを順番に保存できます。 nTableMaskはテーブルのサイズの負の値に対応するため、モジュールとして取得すると0〜–7の値を取得します。 これでメモリにアクセスできます。 arDataバッファー全体を配置する場合、次の式を使用してサイズを計算します。

* bucket' + * (uint32) .

以下に、バッファが2つの部分にどのように分割されているかを明確に示します。

 #define HT_HASH_SIZE(nTableMask) (((size_t)(uint32_t)-(int32_t)(nTableMask)) * sizeof(uint32_t)) #define HT_DATA_SIZE(nTableSize) ((size_t)(nTableSize) * sizeof(Bucket)) #define HT_SIZE_EX(nTableSize, nTableMask) (HT_DATA_SIZE((nTableSize)) + HT_HASH_SIZE((nTableMask))) #define HT_SIZE(ht) HT_SIZE_EX((ht)->nTableSize, (ht)->nTableMask) Bucket *arData; arData = emalloc(HT_SIZE(ht)); /*      */ 

マクロが実行されると、次の結果が得られます。

 (((size_t)(((ht)->nTableSize)) * sizeof(Bucket)) + (((size_t)(uint32_t)-(int32_t)(((ht)->nTableMask))) * sizeof(uint32_t))) 

いいね

衝突解決

それでは、衝突がどのように解決されるかを見てみましょう。 覚えているように、ハッシュテーブルでは、ハッシュおよび圧縮されたときのいくつかのキーが同じ変換インデックスに対応することがあります。 そのため、変換インデックスを受け取ったら、それを使用してarDataからデータを抽出し、ハッシュとキーを比較して、これが必要かどうかを確認します。 データが正しくない場合、 zval.u2.nextフィールドを使用してリンクリストをzval.u2.nextます。このフィールドには、データを入力するための次のセルが反映されます。

リンクリストは、従来のリンクリストのようにメモリスキャッタリングされないことに注意してください。 ヒープから受け取ったいくつかのメモリに配置されたポインタをarDataではarDataおそらくアドレス空間に散らばっている）、メモリから完全なベクトルarDataを読み取ります。 そして、これは、PHP 7および言語全体のハッシュテーブルのパフォーマンスを向上させる主な理由の1つです。

PHP 7では、ハッシュテーブルのデータの局所性は非常に高くなっています。 データは通常、第1レベルのプロセッサキャッシュにあるため、ほとんどの場合、アクセスは1ナノ秒で行われます。

ハッシュに要素を追加し、衝突を解決する方法を見てみましょう。

 idx = ht->nNumUsed++; /*      */ ht->nNumOfElements++; /*    */ /* ... */ p = ht->arData + idx; /*   arData bucket    */ p->key = key; /*     */ /* ... */ p->h = h = ZSTR_H(key); /*   bucket    */ ZVAL_COPY_VALUE(&p->val, pData); /*     bucket':   */ nIndex = h | ht->nTableMask; /*     */ Z_NEXT(p->val) = HT_HASH(ht, nIndex); /*        */ HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx); /*       */ 

削除と同じこと：

 h = zend_string_hash_val(key); /*      */ nIndex = h | ht->nTableMask; /*     */ idx = HT_HASH(ht, nIndex); /*  ,    */ while (idx != HT_INVALID_IDX) { /*     */ p = HT_HASH_TO_BUCKET(ht, idx); /*  bucket    */ if ((p->key == key) || /*  ?    ? */ (p->h == h && /* ...    */ p->key && /*   (   ) */ ZSTR_LEN(p->key) == ZSTR_LEN(key) && /*      */ memcmp(ZSTR_VAL(p->key), ZSTR_VAL(key), ZSTR_LEN(key)) == 0)) { /*     ? */ _zend_hash_del_el_ex(ht, idx, p, prev); /*   !   */ return SUCCESS; } prev = p; idx = Z_NEXT(p->val); /*     */ } return FAILURE; 

変換セルとハッシュの初期化

HT_INVALID_IDXは、変換テーブルに入れる特別なフラグです。 これは、「この変換はどこにも通じないため、続行する必要がない」ことを意味します。

2段階の初期化には特定の利点があり、作成されたばかりの空のハッシュテーブル（PHPの一般的なケース）の影響を最小限に抑えることができます。 テーブルを作成するときに、 arDataバケットセルと、 HT_INVALID_IDXフラグを配置する2つの変換セルを同時に作成します。 次に、最初の変換セル（ HT_INVALID_IDX 、ここにはデータはありません）を指すマスクを適用します。

 #define HT_MIN_MASK ((uint32_t) -2) #define HT_HASH_SIZE(nTableMask) (((size_t)(uint32_t)-(int32_t)(nTableMask)) * sizeof(uint32_t)) #define HT_SET_DATA_ADDR(ht, ptr) do { (ht)->arData = (Bucket*)(((char*)(ptr)) + HT_HASH_SIZE((ht)->nTableMask)); } while (0) static const uint32_t uninitialized_bucket[-HT_MIN_MASK] = {HT_INVALID_IDX, HT_INVALID_IDX}; /* hash lazy init */ ZEND_API void ZEND_FASTCALL _zend_hash_init(HashTable *ht, uint32_t nSize, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC) { /* ... */ ht->nTableSize = zend_hash_check_size(nSize); ht->nTableMask = HT_MIN_MASK; HT_SET_DATA_ADDR(ht, &uninitialized_bucket); ht->nNumUsed = 0; ht->nNumOfElements = 0; } 

ここでは、束を使用できないことに注意してください。 静的constメモリゾーンで十分であり、はるかに簡単です（ uninitialized_bucket ）。

最初の要素を追加した後、ハッシュテーブルを完全に初期化します。 つまり、要求されたサイズに応じて、最後に必要な変換セルを作成します（デフォルトでは8セルから始まります）。 メモリ内の配置はヒープから来ます。

 (ht)->nTableMask = -(ht)->nTableSize; HT_SET_DATA_ADDR(ht, pemalloc(HT_SIZE(ht), (ht)->u.flags & HASH_FLAG_PERSISTENT)); memset(&HT_HASH(ht, (ht)->nTableMask), HT_INVALID_IDX, HT_HASH_SIZE((ht)->nTableMask)) 

HT_HASHマクロを使用HT_HASHと、負のオフセットが使用されるメモリ内にあるバッファーのその部分の変換セルにアクセスできHT_HASH 。 変換テーブルのセルにはarDataバッファーの先頭からマイナスのインデックスが付けられるため、テーブルマスクは常に負になります。 ここでは、Cでのプログラミングがすべての栄光で明らかになりました。数十億個のセルが利用可能で、無限に泳ぎ、justれないでください。

レイジー初期化（レイジー初期化）ハッシュテーブルの例：作成されましたが、これまでハッシュは配置されていません。

ハッシュの断片化、拡大、および圧縮

ハッシュテーブルがいっぱいで、新しい要素を追加する必要がある場合は、サイズを大きくする必要があります。 これは、Cの従来のハード制限配列と比較したハッシュテーブルの大きな利点です。増加するたびに、ハッシュテーブルのサイズは2倍になります。 テーブルのサイズが大きくなると、メモリにC配列arBucketを事前に割り当て、空のセルに特別なUNDEF値を配置することを思い出してください。 その結果、私たちは激しく記憶を失います。 損失は​​次の式で計算されます。

( – ) * Bucket

このメモリはすべてUNDEFセルで構成され、そこにデータが配置されるのを待ちます。

たとえば、ハッシュテーブルに1024個のセルがあり、新しい要素を追加します。 テーブルは2048個のセルに拡大し、そのうちの1023個は空です。 1023 * 32バイト=約32 Kb。 これは、PHPでハッシュテーブルを実装することの欠点の1つです。

ハッシュテーブルが完全に1つのUNDEFセルで構成されている可能性があることを覚えておく必要があります。 多くの要素を追加および削除すると、テーブルが断片化されます。 ただし、要素の順序を保持するために、 arDataの最後にのみ新しいものをすべて追加し、結果のスペースには挿入しません。 そのため、 arDataの最後にarDataすると状況が発生する可能性がありarData 、UNDEFセルはまだ存在しています。

非常に断片化された8セルハッシュテーブルの例：



覚えているように、新しい値はUNDEFセルに保存できません。 上記のスキームでは、ハッシュテーブルを反復するときに、 arData[0]からarData[7]ます。

サイズを大きくすると、 arDataベクトルを減らし、データを再配布するだけで最終的に空のセルを埋めることができます。 テーブルにサイズ変更のコマンドが与えられると、最初にテーブル自体を圧縮しようとします。 次に、圧縮後に再度増加する必要があるかどうかを計算します。 そして、イエスと判明した場合、テーブルは2倍になります。 その後、 arDataベクトルは2倍のメモリ(realloc()) arData始めます。 増やす必要がない場合、データは既にメモリにあるセルに再配布されます。 ここでは、要素を削除するたびに使用できないアルゴリズムを使用します。これは、あまりにも頻繁にプロセッサリソースを消費し、排気量がそれほど大きくないためです。 有名なプログラマーがプロセッサーとメモリーの間で妥協したことを覚えていますか？

この図は、圧縮後の以前の断片化されたハッシュテーブルを示しています。



アルゴリズムはarDataをarData 、各UNDEFセルに次の非UNDEFセルからのデータを取り込みます。 簡略化すると、次のようになります。

 Bucket *p; uint32_t nIndex, i; HT_HASH_RESET(ht); i = 0; p = ht->arData; do { if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) { uint32_t j = i; Bucket *q = p; while (++i < ht->nNumUsed) { p++; if (EXPECTED(Z_TYPE_INFO(p->val) != IS_UNDEF)) { ZVAL_COPY_VALUE(&q->val, &p->val); q->h = p->h; nIndex = q->h | ht->nTableMask; q->key = p->key; Z_NEXT(q->val) = HT_HASH(ht, nIndex); HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(j); if (UNEXPECTED(ht->nInternalPointer == i)) { ht->nInternalPointer = j; } q++; j++; } } ht->nNumUsed = j; break; } nIndex = p->h | ht->nTableMask; Z_NEXT(p->val) = HT_HASH(ht, nIndex); HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(i); p++; } while (++i < ht->nNumUsed); 

ハッシュテーブルAPI

さて、これでPHP 7でハッシュテーブルを実装する主なポイントがわかりました。次に、パブリックAPIを見てみましょう。

特別なことは何もありません（PHP 5では、APIの方がはるかに優れています）。 API関数を使用するときは、次の3つのことを忘れないでください。

• 操作について（追加、削除、クリーニング、破棄など）。
• キーのタイプについて（整数または小文字）。
• 保存するデータの種類について。

キー、小文字、整数にかかわらず、主なこと：小文字のキーにはzend_stringからのハッシュがzend_string 、整数はすぐにハッシュとして使用されることをAPIが認識する必要があります。 したがって、 zend_hash_add(ht, zend_string, data)またはzend_hash_index_add(ht, long, data)を満たすことができます。

キーは単純なペア（char * / int）になる場合があります。 この場合、 zend_hash_str_add(ht, char *, int, data)などの別のAPIを使用する必要があります。 ハッシュテーブルはzend_stringにアクセスし、文字列キーに変換してハッシュを計算し、ある程度のプロセッサリソースを消費することにzend_stringしてください。 zend_stringを使用できる場合は、使用します。 ハッシュはすでに計算されているので、APIはそれらを取得します。 たとえば、PHPコンパイラは、 zend_stringように、使用される文字列の各部分のハッシュを計算します。 OPCacheは同様のハッシュを共有メモリに保存します。 拡張機能の作成者として、すべてのzend_stringリテラルをzend_string初期化することをお勧めします。

次に、ハッシュテーブルに保存するデータについて説明します。 繰り返しになりますが、ハッシュテーブルは各Bucket zvalにデータを配置します。 PHP 7では、zvalはあらゆる種類のデータを保存できます。 一般に、ハッシュテーブルAPIは、データをzvalにパックすることを期待していますzvalは、APIが値として認識します。

ストレージまたはメモリ領域へのポインター（ポインターによって参照されるデータ）がある場合、状況は多少単純化できます。 次に、APIはこのポインターまたはメモリ領域をzvalに配置し、zval自体がポインターをデータとして使用します。

例は、アイデアを理解するのに役立ちます。

 zend_hash_str_add_mem(hashtable *, char *, size_t, void *) zend_hash_index_del(hashtable *, zend_ulong) zend_hash_update_ptr(hashtable *, zend_string *, void *) zend_hash_index_add_empty_element(hashtable *, zend_ulong) 

データを取得すると、zval *またはNULLが取得されます。 ポインターが値として使用される場合、APIはそのまま返されます。

 zend_hash_index_find(hashtable *, zend_string *) : zval * zend_hash_find_ptr(hashtable *, zend_string *) : void * zend_hash_index_find(hashtable *, zend_ulong) : zval * 

zend_hash_add_new()ような_new APIについては、使用しない方が良いでしょう。 内部のニーズにエンジンを使用します。 このAPIは、ハッシュ（同じキー）で既に使用可能な場合でも、ハッシュテーブルにデータを保存させます。 その結果、重複が生じ、作業に最適な効果が得られない場合があります。 したがって、追加しようとしているハッシュにデータがないことを完全に確信している場合にのみ、このAPIを使用できます。 したがって、それらを探す必要はありません。

: 5, API zend_symtable_api() :

 static zend_always_inline zval *zend_symtable_update(HashTable *ht, zend_string *key, zval *pData) { zend_ulong idx; if (ZEND_HANDLE_NUMERIC(key, idx)) { /* handle numeric key */ return zend_hash_index_update(ht, idx, pData); } else { return zend_hash_update(ht, key, pData); } } 

, : , zval… ZEND_HASH_FOREACH :

 #define ZEND_HASH_FOREACH(_ht, indirect) do { \ Bucket *_p = (_ht)->arData; \ Bucket *_end = _p + (_ht)->nNumUsed; \ for (; _p != _end; _p++) { \ zval *_z = &_p->val; \ if (indirect && Z_TYPE_P(_z) == IS_INDIRECT) { \ _z = Z_INDIRECT_P(_z); \ } \ if (UNEXPECTED(Z_TYPE_P(_z) == IS_UNDEF)) continue; #define ZEND_HASH_FOREACH_END() \ } \ } while (0) 

« -»

, : arData , , arData . -: - arData . - , .

: . arData , . , .

« -» (packed hashtable):



, . arData[0] . , 2 * uint32 = 8 . . , , .

: , , ( /), - . bucket'.

 ZEND_API void ZEND_FASTCALL zend_hash_packed_to_hash(HashTable *ht) { void *new_data, *old_data = HT_GET_DATA_ADDR(ht); Bucket *old_buckets = ht->arData; ht->u.flags &= ~HASH_FLAG_PACKED; new_data = pemalloc(HT_SIZE_EX(ht->nTableSize, -ht->nTableSize), (ht)->u.flags & HASH_FLAG_PERSISTENT); ht->nTableMask = -ht->nTableSize; HT_SET_DATA_ADDR(ht, new_data); memcpy(ht->arData, old_buckets, sizeof(Bucket) * ht->nNumUsed); pefree(old_data, (ht)->u.flags & HASH_FLAG_PERSISTENT); zend_hash_rehash(ht); } 

- u.flags , , -. , -, . , . 例：

 static zend_always_inline zval *_zend_hash_index_add_or_update_i(HashTable *ht, zend_ulong h, zval *pData, uint32_t flag ZEND_FILE_LINE_DC) { uint32_t nIndex; uint32_t idx; Bucket *p; /* ... */ if (UNEXPECTED(!(ht->u.flags & HASH_FLAG_INITIALIZED))) { CHECK_INIT(ht, h < ht->nTableSize); if (h < ht->nTableSize) { p = ht->arData + h; goto add_to_packed; } goto add_to_hash; } else if (ht->u.flags & HASH_FLAG_PACKED) { /* ... */ } else if (EXPECTED(h < ht->nTableSize)) { p = ht->arData + h; } else if ((h >> 1) < ht->nTableSize && (ht->nTableSize >> 1) < ht->nNumOfElements) { zend_hash_packed_grow(ht); p = ht->arData + h; } else { goto convert_to_hash; } /* ... */ 

: - , .

• : : (_ - 2) * (uint32) . , .
• : . , .

(, 42 60), - «». ( — ) . - API:

 void ZEND_FASTCALL zend_hash_real_init(HashTable *ht, zend_bool packed) 

, zend_hash_real_init() — , «» ( zend_hash_init() ). , «», - . , .

, - .

-

(packed array):

 function m() { printf("%d\n", memory_get_usage()); } $a = range(1,20000); /* range()    */ m(); for($i=0; $i<5000; $i++) { /*      , *       : *    «»  */ $a[] = $i; } m(); /*         * -   «»,   *     */ $a['foo'] = 'bar'; m(); 

, :

 1406744 1406776 1533752 

130 ( 25 000 ).

:

 function m() { printf("%d\n", memory_get_usage()); } /*  -    .   *   32 768  (2^15).    */ for ($i=0; $i<32768; $i++) { $a[$i] = $i; } m(); /*    */ for ($i=0; $i<32768; $i++) { unset($a[$i]); } m(); /*   .  -  , *        */ $a[] = 42; m(); 

結果：

 1406864 1406896 1533872 

, ( , modulo noise). unset() arData 32 768 , UNDEF-zval'.

- . nNumUsed , arData ? , , .

?

— , UNDEF-. : , , , . , , , .

 /*   ,   , : */ /*          (idx). *   ,      */ $a[3] = 42; m(); 

:

 1406864 1406896 1406896 

? 32 768 65 538 , . 32 767 . Bucket , zval , long ( 42), . zval long. :) , 32 768 , , , . , , . ., , UNDEF-zval' «» .

-, . , , , . «» , ( idx 0 ), — UNDEF-zval.

 function m() { printf("%d\n", memory_get_usage()); } /*  -    .   *   32 768  (2^15).       */ for ($i=0; $i<32768; $i++) { /*   ,       */ $a[' ' . $i] = $i; } m(); /*    */ for ($i=0; $i<32768; $i++) { unset($a[' ' . $i]); } m(); /*         . *   ,      */ $a[] = 42; m(); 

:

 2582480 1533936 1533936 

. 2,5 . unset() , . 32 768 zend_string , 1,5 .

, , . , , . 42 idx 0, . 物語の終わり。

, - , . ? , (, ?) / , . . , . «» 20 32 , .

(Immutable arrays)

— OPCache. OPCache, , . . . OPCache , . , AST-. , — AST-. 例：

 $a = ['foo', 1, 'bar']; 

$a — AST-. , , . OPCache AST-, ( ) , . OPCache .

, OPCache , IS_ARRAY_IMMUTABLE IS_TYPE_IMMUTABLE . IS_IMMUTABLE , . , . .

:

 $ar = []; for ($i = 0; $i < 1000000; ++$i) { $ar[] = [1, 2, 3, 4, 5, 6, 7, 8]; } 

400 OPCache, — 35 . OPCache , 8- $ar . 8- . OPCache, 8- IS_IMMUTABLE $ar , .

, , , $ar[42][3] = 'foo'; , 8- $ar[42] .

- , . , PHP- — - Zend. PHP, . - . , / . -. OPArray ( ) ( ). PHP , OPArray: . OPCache IMMUTABLE , . , .

OPCache , . , ( , ). , - OPCache , PHP- . PHP.

. , :

 $a = [1]; $b = [1]; 

. , ( interned strings ), , . — , ( , , ), runtime' PHP. ( ). , OPCache.