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

• 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

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

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"