An in-depth analysis of how PHP arrays flexibly support multiple data types

This article brings you relevant knowledge about PHP. It mainly introduces to you how arrays can flexibly support multiple data types. Friends who are interested can take a look below. I hope it will be useful to you. help.

In PHP, the application processing of array data structures is very frequently used. Compared with strongly typed languages ​​such as Java and C, PHP's arrays can simply It is said to be very easy to use and can store various types of data (such as numbers, strings and even objects, etc.), which brings great convenience to development.

Based on the powerful features of PHP arrays, we can easily implement more complex data structures, such as stacks, queues, lists, sets, dictionaries, etc.

Are you eager to find out: How does PHP implement arrays?

1. The underlying data structure of PHP array

PHP array is internally implemented using the HashTable structure, so let’s briefly talk about HashTable first!

HashTable, also known as hash table, is a structure that efficiently accesses data through key-value. A hash table is a combination of an array and a linked list, integrating the fast addressing of an array and the fast insertion of a linked list.

HashTable is mainly divided into two links:

1. Hash function: The hash function converts the value to be found into a numeric index, and uses the numeric index to You can quickly find where the value exists.

2. Hash collision: Ideally, after different values ​​pass through the hash function, the results will be different; if the values ​​are different, the same number will come out after hashing, we call it for hash collisions.

Therefore, when applying HashTable, you must face the problem of hash collision. There are two main solutions: linked list method and open addressing method.

In the zend_type.h file, you can find the main structure definition of HashTable as follows:

zend_array type

Pick a few Let’s introduce the key members:

• #gc: Reference counting and garbage collection.

• arData: An array that stores elements in a hash table. Its memory is continuous. arData points to the starting position of the array;

• ##nTableSize : The total capacity of the array, that is, the number of elements that can be accommodated. The memory size of arData is determined based on this value. Its size is the power of 2, with a minimum of 8, and then in order: 8, 16, 32... Incrementing;

Bucket type

Bucket has a relatively simple structure and is mainly used to save the key of elements and value, and an integer h (hash value, or hash value).

• If the element is a numeric index, its value is the value of the numeric index;

• If it is a string index, its value is the key A hash value calculated using the Time33 algorithm. The value of

h is used to ultimately map the storage location of the element.

2. Basic implementation of PHP array

We have learned about the data structure of zend_array in the above part, then let’s take a look at the initialization of the array:

The initialization of the array is mainly for the setting of HashTable members. The memory of arData will not be allocated immediately during initialization. The memory of arData will be allocated after the first element is inserted.

In order to better understand the entire hash structure, let’s give an example to illustrate this structure:

$data = array(
    'hello' => 'haha',
    1       => 'me to'
    'world' => 'world', 
    2       => 2
);
unset($data[1]);

What should the hash structure above look like? What should the result stored by arData look like?

Let’s draw an illustration to see it, it’s more intuitive:

arData is a pointer of Bucket type, used to specifically store the key of each element. value stores data in the order in which elements are inserted, so the order of the array is also guaranteed by this.

Each element of the arData array, as you can see from the figure, the negative number on the left is the value after modulo the hash value, and the index of the arData on the right is stored; if -8 conflicts, the linked list is stored The header element.

arData[0]: key='hello', h=xx (a specific value), val = 'haha'

arData[1]: val is type= zval of IS_UNDEF (after being unset, it is not deleted immediately, but set to IS_UNDEF)

arData[2]: key='world', h=xx (a specific value), val = 'world '

arData[3]: key=NULL, h=2 (hash value conflict may occur), val = 2

….

The above example is very specific Explained the meaning of nNumUsed, nNumOfElements, arData.

3. Orderliness of PHP arrays

The order of each element in the array is consistent with the order of insertion. How is this achieved?

In order to achieve the orderliness of PHP arrays, the underlying hash table of PHP adds a mapping table between the hash function and the element array. This mapping table is also an array, with the same size as the array storing the elements. , the type of storage element is an integer, used to save the subscript of the element in the actual stored ordered array - the elements are inserted into the actual storage array in order, and then the array subscript is hashed according to the hash function The location is stored in the newly added mapping table:

In this way, the order of the final stored data can be completed.

This intermediate mapping table is not explicitly identified in the underlying structure of the PHP array, but is placed together with arData. When the array is initialized, not only the memory used to store the Bucket is allocated, but the same amount is also allocated. uint32_t size space, these two spaces are allocated together, and then arData is offset to the location where the element array is stored, and this intermediate mapping table can be accessed forward through arData.

Summary

The characteristic of arrays in PHP is to map values ​​to the type of keys. Unlike other languages, the keys of arrays in PHP can be strings, and the values ​​can be of any type.

In addition to regular additions, deletions, modifications, and searches, arrays also have many other operations, such as copying, merging, destroying, resetting, etc. The codes corresponding to these operations are located in zend_hash.c. Interested students can go Learn about.

Recommended learning: "PHP Video Tutorial"