PHP配列の基本構造の紹介

この記事では、グループの基本的な構造を紹介します。これは一定の参考価値があります。困っている友達は参考にしてください。お役に立てば幸いです。

以下は、PHP 配列の基本構造、挿入、検索、再ハッシュのプロセスです。

基本構造:

struct _zend_array {
    zend_refcounted_h gc;
    union {
        struct {
            ZEND_ENDIAN_LOHI_4(
                zend_uchar    flags,
                zend_uchar    nApplyCount,
                zend_uchar    nIteratorsCount,
                zend_uchar    consistency)
        } v;
        uint32_t flags;
    } u;
    uint32_t          nTableMask; // 哈希值计算掩码，等于nTableSize的负值(nTableMask = -nTableSize)
    Bucket            *arData;     // 存储元素数组，指向第一个Bucket
    uint32_t          nNumUsed;   // 已用Bucket数
    uint32_t          nNumOfElements; // 哈希表有效元素数 = nNumUsed - num(is_undef)
    uint32_t          nTableSize;   // 哈希表总大小，为2的n次方, 最小为8
    uint32_t          nInternalPointer;  // 怀疑是内部指针
    zend_long         nNextFreeElement; // 下一个可用的数值索引 arr[] = 1;arr["a"] = 2;arr[] = 3;  则nNextFreeElement = 2;
    dtor_func_t       pDestructor;
};

typedef struct _Bucket {
    zval              val;  // 存储的具体value
    zend_ulong        h;    // hash value (or numeric index)  
    zend_string      *key;  // string key or NULL for numerics
} Bucket;

説明:

配列を保存するときは、まず値が順番に保存され、次に値の位置が保存されます。保存されました。

レコードを格納する配列をハッシュテーブルと呼びます。この配列は値を格納するために使用され、値が順番に格納されます。その格納場所は、ハッシュを計算して得られるidxに格納されます。 nTableMask を法とするキー。

配列が初期化されるとき、最小サイズは 8、つまり 16、32、64 です。 。 。

配列の初期化中に作成された idx 領域はすべて -1 に初期化され、再ハッシュ中にも -1 に初期化されます。

要素が配列から削除されると、削除された要素の型は is_undef および nNumOfEmelment - 1 としてマークされます。要素が最後の要素の場合は、nNumused - 1 になります。

挿入:

$arr = ['a'=>1, 'b'=>2] を例として挙げます:

まず配列に 1 を入れます (val.u2.next = -1)。添え字 a に従ってハッシュを計算し、nTableMask を法とするハッシュを取得して idx を取得し、前の 1 のインデックス nindex を次の位置に保存します。 idxの。

2 を再度格納します (val.u2.next = -1)。ハッシュが添え字 b と modulo nTableMask に基づいて計算された場合、取得された idx にはすでに値があり、ハッシュの衝突が発生していることを意味します。このとき、現在の idx の値が取り出して現在の val.u2.next に保存され、インデックス nindex 2 が現在の idx に保存されます。

検索:

添え字 a に基づいてハッシュを計算し、法 nTableMask を取得し、idx を取得し、idx の値 nindex を取得して、arData を検索します。位置が != a のキーが見つかった場合、そのキーは見つかりません。見つかった位置 == a のキーの場合は、その u2.next を確認します。-1 の場合は見つかりました。が -1 でない場合は、挿入中であることを意味します。ハッシュの競合が発生した場合は、見つかるまで u2.next に従って arData の検索を続けます。

#rehash:

rehash するときは、まず nindex 領域内のすべてのレコードを -1 にリセットし、次にポインタ *p を最初の要素から移動します。要素が is_undef としてマークされていない場合は、要素のキー ハッシュを再計算して nindex に入れ、ループします。p。要素が is_undef としてマークされている場合は、ポインタ p を移動し続け、その位置を指すように新しいポインタ j を設定します。ループを続けて、is_undef ではない要素を 1 つずつ前に移動します。p が移動するたびに、 j は is_undef に遭遇し、値が割り当てられるまで動きません。最後の nNunused まで移動し、nNunused に j を割り当て、この位置から要素を挿入すると、前の要素が直接上書きされます。

以上がPHP配列の基本構造の紹介の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。