Shulou(Shulou.com)06/02 Report--

What this article shares to you is about how to look at the linear table data structure from the principle of PHP array implementation, the editor thinks it is very practical, so I share it with you to learn. I hope you can get something after reading this article.

Linear table, the full name is linear storage structure. Using linear tables to store data can be understood as "stringing all the data together with a thread and then storing it in physical space." The simplest linear table is an array. Although the array of PHP itself is not made up of basic data structures, its internal implementation applies to most linear table data structures. Today, we take the opportunity to review the internal implementation of PHP arrays by learning the data structure of linear tables.

Internal implementation of PHP array

Arrays are very powerful and important data types in PHP. It supports both simple numeric indexed arrays and key-value pair arrays, where the key-value pair array is similar to java's HashMap. Due to the use of hash table implementation can ensure that the basic search time complexity is O (1), but also can ensure the order of data traversal.

First, let's take a look at what the data structure of PHP looks like in the kernel C language.

See what happens when you insert an element into an array in php code

$arr = ['name'= >' admin']

1. The kernel first creates a _ zend_array data object. The size of the initialization array is defined as HT_MIN_SIZE 8 in HT_MIN_SIZE,PHP; so when the array element is less than 8, inserting data does not expand the array.

two。 Use the Times 33hash algorithm to convert name to a long shaping number.

3. Save the key name of the array in the Bucket data in key [nNumUsed + +], the integer (negative) after the hash of key in h, and the address of arData [h] in the u2.next of val. Store the conversion table with the arData starting pointer as the starting point for specular mapping storage. In this way, we do not need additional space storage, and we allocate the conversion table as well as the arData space.

When looking up an array, after hash directly according to the key name, you can directly locate the Bucket that actually stores the key value, and when traversing, because the arData itself is an ordered C array, you can get the Bucket to save the key value after traversing the array. Therefore, the array of PHP can not only query the array with O (1) complexity, but also traverse the array elements sequentially.

The main core code corresponding to the source code implementation logic is as follows:

The above procedure omits hash conflicts. But even from the simple version above, you can find that the implementation of the PHP array uses a lot of knowledge of data structures.

Bucket * arData; is a C language array that corresponds to an ordered table in a data structure. Between Bucket, the u2.next of val forms a linked list structure.

At the same time, PHP degenerates all the conflicting key name data into a linked list when dealing with hash conflicts. And this way of processing, is the vast majority of hash processing.

Sequence table

The sequence table is defined as follows:

The so-called sequential table is a sequentially stored linear table. Sequential storage is a storage structure in which each element of a linear table is stored in turn by a set of consecutive address storage units.

The arData in the above PHP core code is a sequence table.

Features of the sequence table:

1. Logically adjacent data elements in a linear table are also adjacent in physical storage.

two。 The storage density is high, but it is necessary to allocate "enough application" storage space in advance, which may cause a waste of storage space.

3. It is easy to store randomly. As long as the starting position of the linear table is determined, any data element in the linear table can be accessed randomly, so the sequential storage structure of the linear table is a random access storage structure.

4. Insert and delete operations are not convenient because inserts and deletions on sequential tables cause a large number of data elements to move.

Problems with the sequence table:

1. Physically adjacent storage is not convenient for memory utilization. For example, an array with a capacity of 10 requires 10 bytes of memory, but there is no memory space available for 10 consecutive bytes, but there are many discontiguous memory spaces less than 10 bytes, so it is impossible to allocate them.

two。 The capacity of the sequence table is difficult to determine. For C language, defining an array requires specifying the size of the array. This size is to make it easier for the underlying layer to apply for continuous memory space. When initializing an empty array in the PHP source code, an arData array with a length of 16 is also created, and the array is expanded when it is needed.

3. It is not convenient to insert elements, you need to move the entire sequence table element

Linked list

The data structure of linked list is proposed to solve the problem of sequential list. Linked list is a kind of non-continuous and non-sequential storage structure in physical storage structure, and the logical order of data elements is realized through the pointer link order in the linked list. In the source code of the PHP array, each Bucket is a node in the linked list. Point to the next node through Bucket.u2.next (although it is itself for hash lookup).

According to the link mode of the linked list, it is divided into single linked list and double linked list.

In each node of the single linked list, there is only a pointer to the next node, which can not be traced back, so it is suitable for the addition and deletion of nodes.

Each node of the double-linked list has both a pointer to the next node and a pointer to the previous node, which can quickly find the previous node of the current node, which is suitable for situations that need to find node values in both directions.

Advantages of linked lists:

Insert and delete are efficient, and you only need to change the pointer to insert and delete.

Memory utilization is high, memory will not be wasted, and small discontiguous space in memory can be used to create space only when needed. The size is not fixed, and the expansion is very flexible.

The above is how to look at the linear table data structure from the principle of PHP array implementation. The editor believes that there are some knowledge points that we may see or use in our daily work. I hope you can learn more from this article. For more details, please follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.