Introduction aux tables et tableaux de hachage php (avec code)

Cet article vous présente une introduction aux tables de hachage et aux tableaux PHP (avec code). Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

Les tableaux sont le type de données le plus couramment utilisé en PHP. En même temps, PHP est facile à utiliser grâce à ses tableaux puissants, mais comment les tableaux sont-ils implémentés en PHP ?

Tout d'abord, comprenons d'abord la structure de données pertinente pour jeter une base solide pour le contenu suivant

Table de hachage

哈希表, comme son nom l'indique, est une structure de données qui mappe différents mots-clés à différentes unités. La méthode de mappage de différents mots-clés à différentes unités est appelée 哈希函数

Idéalement, après traitement par la fonction de hachage, il y aura une correspondance biunivoque entre les mots-clés et les unités ; Cependant, s'il y a suffisamment de valeurs de mots-clés, il est facile de mapper plusieurs mots-clés sur la même unité, c'est-à-dire 哈希冲突

solution de conflit de hachage, utilisez 链接法 ou utilisez 开放寻址法

méthode de chaînage
c'est-à-dire que lorsque différents mots-clés sont mappés à la même unité, utilisez une liste chaînée dans la même unité pour enregistrer ces mots-clés

Méthode d'adressage ouverte
C'est-à-dire que lors de l'insertion de données, s'il s'avère qu'il y a des données dans l'unité à laquelle le mot-clé est mappé, cela signifie qu'un conflit s'est produit, puis continuez à rechercher le unité suivante jusqu'à ce qu'une unité disponible soit trouvée

Et comme la méthode d'adressage ouverte occupe l'emplacement d'autres unités de mappage de mots-clés, les mots-clés suivants sont plus susceptibles d'avoir des conflits de hachage, donc une dégradation des performances est susceptible de se produire

Liste chaînée

Étant donné que les listes chaînées ont été mentionnées ci-dessus, nous parlons brièvement ici des bases des listes chaînées. Les listes chaînées sont divisées en plusieurs types. Les structures de données couramment utilisées incluent : la file d'attente, la pile, la liste chaînée bidirectionnelle, etc.

La liste chaînée est une structure de données composée de différents nœuds de liste chaînée. Les nœuds de liste chaînée sont généralement constitués de 元素+指向下一节点的指针. La liste doublement chaînée, comme son nom l'indique, est composée de 指向上一节点的指针+元素+指向下一节点的指针

Quant au contenu de la structure des données, nous n'allons pas trop l'étendre. Nous aurons du spécial. contenu pour présenter la structure des données en détail plus tard.

tableau php

La façon dont PHP résout les conflits de hachage est d'utiliser la méthode de chaînage, donc le tableau PHP est implémenté par 哈希表+链表, pour être précis, est implémenté par 哈希表+双向链表

Structure interne - Table de hachage

La structure HashTable est principalement utilisé pour stocker les informations de base de la table de hachage

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;

La structure Bucket est utilisée pour enregistrer le contenu spécifique des données

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;

Il y a un élément pData dans la structure Bucket qui pointe vers les données utilisateur, qui pointe en fait vers la structure variable zval que nous avons introduite précédemment, c'est pourquoi lors de la création d'un tableau, un conteneur variable d'élément de tableau + 1 apparaît.

Schéma de la structure interne de la table de hachage

Remarque : l'image provient d'Internet

De l'image ci-dessus nous On peut voir que lorsque Bucket stocke des données, en cas de conflit de hachage, plusieurs mots-clés seront mappés à la liste chaînée, formant ainsi une liste doublement chaînée

Résumé

Aujourd'hui, nous En utilisant les tableaux comme point d'entrée, nous avons brièvement compris les structures de données de base : tables de hachage et listes chaînées et avons également découvert l'implémentation sous-jacente des tableaux, à savoir 哈希表+双向链表. En fait, la table de hachage est la structure de données la plus importante en PHP et a de nombreuses utilisations.

[Recommandations associées : Tutoriel vidéo PHP]

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!