Einführung in PHP-Hash-Tabellen und -Arrays (mit Code)

Dieser Artikel bietet Ihnen eine Einführung in PHP-Hash-Tabellen und -Arrays (mit Code). Ich hoffe, dass er für Freunde hilfreich ist.

Arrays sind der am häufigsten verwendete Datentyp in PHP. Gleichzeitig ist PHP dank seiner leistungsstarken Arrays einfach zu verwenden, aber wie werden Arrays in PHP implementiert?

Lassen Sie uns zunächst die relevante Datenstruktur verstehen, um eine solide Grundlage für den folgenden Inhalt zu legen

Hash-Tabelle

哈希表 ist, wie der Name schon sagt, eine Datenstruktur, die verschiedene Schlüsselwörter verschiedenen Einheiten zuordnet. Die Methode zum Zuordnen verschiedener Schlüsselwörter zu verschiedenen Einheiten heißt 哈希函数

Idealerweise besteht nach der Verarbeitung durch die Hash-Funktion eine Eins-zu-eins-Entsprechung zwischen Schlüsselwörtern und Einheiten. Wenn jedoch genügend Schlüsselwortwerte vorhanden sind, können mehrere Schlüsselwörter leicht derselben Einheit zugeordnet werden, d. h. 哈希冲突

Hash-Konfliktlösung, entweder 链接法 verwenden oder 开放寻址法 verwenden

Verkettungsmethode
Das heißt, wenn unterschiedliche Schlüsselwörter derselben Einheit zugeordnet sind, verwenden Sie eine verknüpfte Liste in derselben Einheit, um diese Schlüsselwörter zu speichern

Offene Adressierungsmethode
Das heißt, wenn beim Einfügen von Daten festgestellt wird, dass in der Einheit, der das Schlüsselwort zugeordnet ist, Daten vorhanden sind, bedeutet dies, dass ein Konflikt aufgetreten ist, und suchen Sie dann weiter nach nächste Einheit, bis eine verfügbare Einheit gefunden wird

Und da die offene Adressierungsmethode den Standort anderer Schlüsselwortzuordnungseinheiten einnimmt, ist es wahrscheinlicher, dass nachfolgende Schlüsselwörter Hash-Konflikte aufweisen, sodass es leicht zu Leistungseinbußen kommt

Verknüpfte Liste

Da oben bereits die verknüpften Listen erwähnt wurden, sprechen wir hier kurz über die Grundlagen verknüpfter Listen. Verknüpfte Listen werden in viele Typen unterteilt: Warteschlangen, Stapel, bidirektional verknüpfte Listen usw.

Eine verknüpfte Liste ist eine Datenstruktur, die aus verschiedenen verknüpften Listenknoten besteht. Verknüpfte Listenknoten bestehen im Allgemeinen aus 元素+指向下一节点的指针. Die doppelt verknüpfte Liste besteht, wie der Name schon sagt, aus 指向上一节点的指针+元素+指向下一节点的指针

Was den Inhalt der Datenstruktur betrifft, werden wir nicht zu viel erweitern Inhalt, um die Datenstruktur später im Detail vorzustellen.

PHP-Array

Die Art und Weise, wie PHP Hash-Konflikte löst, besteht darin, die Verkettungsmethode zu verwenden, sodass das PHP-Array von implementiert wird 哈希表+链表, um genau zu sein, wird durch 哈希表+双向链表

Interne Struktur - Hash-Tabelle

Die HashTable-Struktur wird hauptsächlich implementiert Wird verwendet, um die grundlegenden Informationen der Hash-Tabelle zu speichern

typedef struct _hashtable { 
    uint nTableSize;        // hash Bucket的大小，即哈希表的容量，最小为8，以2x增长。
    uint nTableMask;        // nTableSize-1 ， 索引取值的优化
    uint nNumOfElements;    // hash Bucket中当前存在的元素个数，count()函数会直接返回此值 
    ulong nNextFreeElement; // 下一个可使用的数字键值
    Bucket *pInternalPointer;   // 当前遍历的指针（foreach比for快的原因之一）
    Bucket *pListHead;          // 存储整个哈希表的头元素指针
    Bucket *pListTail;          // 存储整个哈希表的尾元素指针
    Bucket **arBuckets;         // 存储hash数组
    dtor_func_t pDestructor;    // 在删除元素时执行的回调函数，用于资源的释放
    zend_bool persistent;       //指出了Bucket内存分配的方式。如果persisient为TRUE，则使用操作系统本身的内存分配函数为Bucket分配内存，否则使用PHP的内存分配函数。
    unsigned char nApplyCount; // 标记当前hash Bucket被递归访问的次数（防止多次递归）
    zend_bool bApplyProtection;// 标记当前hash桶允许不允许多次访问，不允许时，最多只能递归3次
#if ZEND_DEBUG
    int inconsistent;
#endif
} HashTable;

Die Bucket-Struktur wird verwendet, um den spezifischen Inhalt der Daten zu speichern

typedef struct bucket {
    ulong h;            // 对char *key进行hash后的值，或者是用户指定的数字索引值
    uint nKeyLength;    // hash关键字的长度，如果数组索引为数字，此值为0
    void *pData;        // 指向value，一般是用户数据的副本，如果是指针数据，则指向pDataPtr
    void *pDataPtr;     // 如果是指针数据，此值会指向真正的value，同时上面pData会指向此值
    struct bucket *pListNext;   // 指向整个哈希表的该单元的下一个元素
    struct bucket *pListLast;   // 指向整个哈希表的该单元的上一个元素
    struct bucket *pNext;       // 指向由于哈希冲突导致存放在同一个单元的链表中的下一个元素
    struct bucket *pLast;       // 指向由于哈希冲突导致存放在同一个单元的链表中的上一个元素
    // 保存当前值所对于的key字符串，这个字段只能定义在最后，实现变长结构体
    char arKey[1];              
} Bucket;

Es gibt ein pData-Element in der Bucket-Struktur, das auf die zeigt Benutzerdaten, die tatsächlich auf die zuvor eingeführte variable zval-Struktur verweisen. Dies ist auch der Grund, warum beim Erstellen eines Arrays ein Variablencontainer mit Array-Element +1 angezeigt wird.

Internes Strukturdiagramm der Hash-Tabelle

Hinweis: Das Bild stammt aus dem Internet

Aus dem Bild oben wir Es ist ersichtlich, dass beim Speichern von Bucket-Daten bei einem Hash-Konflikt mehrere Schlüsselwörter der verknüpften Liste zugeordnet werden, wodurch eine doppelt verknüpfte Liste entsteht

Zusammenfassung

Heute haben wir Mithilfe von Arrays als Einstiegspunkt haben wir kurz die grundlegenden Datenstrukturen verstanden: Hash-Tabellen und verknüpfte Listen und haben auch etwas über die zugrunde liegende Implementierung von Arrays gelernt, nämlich 哈希表+双向链表; Tatsächlich ist die Hash-Tabelle die wichtigste Datenstruktur in PHP und hat viele Verwendungsmöglichkeiten.

[Verwandte Empfehlungen: PHP-Video-Tutorial]

Das obige ist der detaillierte Inhalt vonEinführung in PHP-Hash-Tabellen und -Arrays (mit Code). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!