Introduction to php hash tables and arrays (with code)

This article brings you an introduction to PHP hash tables and arrays (with code). It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

Arrays are the most commonly used data type in PHP. At the same time, PHP is easy to use thanks to its powerful arrays, but how are arrays implemented in PHP?

First of all, we should first understand the relevant data structure and lay a solid foundation for the following content

Hash table

Hash table, as the name suggests, is a data structure that maps different keywords to different units. The method of mapping different keywords to different units is called Hash function

Ideally, after processing by the hash function, the keywords and units will be One-to-one correspondence; however, if there are enough keyword values, it is easy for multiple keywords to be mapped to the same unit, that is, hash conflict

hash The solution to the conflict is to either use linking method or open addressing method

##linking method i.e. when different keys When words are mapped to the same unit, use a linked list to save these keywords in the same unit

Open addressing methodThat is, when inserting data, if the keyword is found to be mapped to There is data in the unit, indicating that a conflict has occurred, and then continue to search for the next unit until an available unit is found

And because the open addressing method scheme occupies the location of other keyword mapping units, the subsequent key Words are more likely to have hash conflicts, so they are prone to performance degradation

Linked list

Since linked lists are mentioned above, here we briefly talk about the basics of linked lists. Linked lists are divided into many types. Commonly used data structures include: queues, stacks, two-way linked lists, etc.

A linked list is a data structure composed of different linked list nodes. Linked list nodes are generally composed of

elements pointers pointing to the next node. The doubly linked list, as the name suggests, is composed of pointers pointing to the previous node elements pointers pointing to the next node

for data structures We will not expand on the content. We will have special content to introduce the data structure in detail later

php array

The way PHP resolves hash conflicts is to use Linking method, so the php array is implemented by

hash table linked list . To be precise, it is implemented by hash table doubly linked list

Internal structure - Hash table

The HashTable structure is mainly used to store the basic information of the hash table

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;

The Bucket structure is used for The specific content of the saved data

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;

There is a pData element in the Bucket structure that points to the user data, which actually points to the variable zval structure we introduced before. This is why when creating an array, array element 1 appears. variable container.

Hash table internal structure diagram

Note: The picture comes from the Internet

From the above picture we It can be seen that when Bucket stores data, if there is a hash conflict, multiple keywords will be mapped to the linked list, thus forming a doubly linked list

Summary

Today, we Using arrays as the entry point, we briefly understood the basic data structures: hash tables and linked lists; and also learned about the underlying implementation of arrays, that is,

hash tables double linked lists. In fact, the hash table is the most important data structure in PHP and has many uses.

【Related recommendations:

PHP video tutorial】

The above is the detailed content of Introduction to php hash tables and arrays (with code). For more information, please follow other related articles on the PHP Chinese website!