Einführung in die Grundstruktur von PHP-Arrays

Dieser Artikel gibt Ihnen eine Einführung in die Grundstruktur von Gruppen. Er hat einen gewissen Referenzwert. Ich hoffe, er wird Ihnen hilfreich sein.

Das Folgende ist die Grundstruktur, das Einfügen, die Suche und den Rehash-Prozess des PHP-Arrays.

Grundstruktur:

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;

Erklärung:

Speichern Sie beim Speichern des Arrays zuerst den Wert in der richtigen Reihenfolge und dann die Position des Werts .

Das Array, in dem Datensätze gespeichert werden, wird als Hash-Tabelle bezeichnet. Dieses Array wird zum Speichern von Werten verwendet, und die Werte werden in der Reihenfolge gespeichert, in der sie in der IDX gespeichert werden, die durch Berechnen des Hashs erhalten wird Schlüsselmodulo nTableMask.

Wenn das Array initialisiert wird, beträgt die Mindestgröße 8, also 16, 32, 64. . .

Der während der Array-Initialisierung erstellte IDX-Bereich wird alle auf -1 initialisiert und wird auch während des Rehashs auf -1 initialisiert.

Wenn ein Element aus dem Array gelöscht wird, wird der Typ des gelöschten Elements als is_undef markiert und nNumOfEmelment – ​​1. Wenn das Element das letzte Element ist, dann ist nNumUsed – 1.

Einfügen:

Nehmen Sie $arr = ['a'=>1, 'b'=>2] als Beispiel:

Fügen Sie zuerst 1 in das Array ein, sein val.u2.next = -1, berechnen Sie den Hash gemäß seinem Index a, nehmen Sie dann den Hash-Modulo nTableMask, um eine ID zu erhalten, und speichern Sie den Index nindex der vorherigen 1 an der Position des idx.

Speichern Sie 2 erneut, sein val.u2.next = -1. Wenn der auf der Grundlage seines Index b modulo nTableMask berechnete Hash bereits einen Wert in der ID hat, bedeutet dies, dass eine Hash-Kollision aufgetreten ist Dieses Mal wird der Wert im aktuellen IDX herausgenommen und im aktuellen val.u2.next gespeichert, und der Index nindex von 2 wird im aktuellen IDX gespeichert und so weiter.

Suche:

Berechnen Sie den Hash basierend auf dem Index a, nehmen Sie die Modulo-nTableMask und erhalten Sie einen IDX, erhalten Sie den Wert nindex im IDX und suchen Sie ihn in arData . Wenn der Schlüssel in != a gefunden wird, wird er nicht gefunden Ist nicht -1, bedeutet dies, dass ein Hash-Konflikt auftritt. Setzen Sie die Suche in arData gemäß u2.next fort, bis er gefunden wird.

Rehash: Beim

Rehash werden zunächst alle Datensätze im nindex-Bereich auf -1 zurückgesetzt und dann der Zeiger *p ab dem ersten Element bewegt Das Element ist nicht als is_undef markiert. Berechnen Sie dann den Schlüssel-Hash des Elements neu, fügen Sie ihn in nindex ein und führen Sie dann eine Schleife aus, p++. Wenn das Element als is_undef markiert ist, bewegen Sie den Zeiger p++ weiter und setzen Sie einen neuen Zeiger j, der auf die Position zeigt. Setzen Sie die Schleife fort und verschieben Sie die Elemente, die nicht is_undef sind, nacheinander nach vorne , j trifft auf is_undef. Es wird sich nicht bewegen, bis ihm ein Wert zugewiesen wird. Gehen Sie bis zum letzten nNunUsed, weisen Sie dann nNunUsed j zu und fügen Sie dann Elemente von dieser Position aus ein. Die vorherigen Elemente werden direkt überschrieben.

Das obige ist der detaillierte Inhalt vonEinführung in die Grundstruktur von PHP-Arrays. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!