PHP source code analysis Zend HashTable detailed explanation page 1/3_PHP tutorial

HashTable is also called hash table or hash table in common data structure textbooks. The basic principle is relatively simple (if you are not familiar with it, please consult any data structure textbook or search online), but the implementation of PHP has its own unique features. Understanding the data storage structure of HashTable is very helpful for us when analyzing the source code of PHP, especially the implementation of the virtual machine in Zend Engine. It can help us simulate the image of a complete virtual machine in our brains. It is also the basis for the implementation of other data structures in PHP such as arrays.
The implementation of Zend HashTable combines the advantages of two data structures, doubly linked list and vector (array), and provides a very efficient data storage and query mechanism for PHP.
Let's begin!
1. Data structure of HashTable
The implementation code of HashTable in Zend Engine mainly includes the two files zend_hash.h and zend_hash.c. Zend HashTable includes two main data structures, one is the Bucket structure and the other is the HashTable structure. The Bucket structure is a container used to save data, and the HashTable structure provides a mechanism to manage all these Buckets (or bucket columns).

In Zend HashTable, each data element (Bucket) has a key name (key), which is unique in the entire HashTable and cannot repeat. The data elements in the HashTable can be uniquely determined based on the key name. There are two ways to represent key names. The first method uses the string arKey as the key name, and the length of the string is nKeyLength. Note that in the above data structure, although arKey is just a character array with a length of 1, it does not mean that the key can only be one character. In fact, Bucket is a variable-length structure. Since arKey is the last member variable of Bucket, a key with a length of nKeyLength can be determined by combining arKey with nKeyLength. This is a common technique in C language programming. Another key name representation method is the index method. In this case, nKeyLength is always 0, and the long integer field h represents the key name of the data element. To put it simply, if nKeyLength=0, the key name is h; otherwise, the key name is arKey, and the length of the key name is nKeyLength.
When nKeyLength > 0, it does not mean that the h value at this time is meaningless. In fact, what it saves at this time is the hash value corresponding to arKey. No matter how the hash function is designed, conflicts are inevitable, which means that different arKeys may have the same hash value. Buckets with the same hash value are stored in the bucket column corresponding to the same index in the arBuckets array of HashTable (refer to the explanation below). This bucket column is a doubly linked list, and its forward elements and backward elements are represented by pLast and pNext respectively. The newly inserted Bucket is placed at the front of the bucket column.
In Bucket, the actual data is stored in the memory block pointed to by the pData pointer. Usually this memory block is allocated separately by the system. But there is an exception, that is, when the data saved by the Bucket is a pointer, the HashTable will not request the system to allocate space to save the pointer, but directly save the pointer to pDataPtr, and then point pData to the member of this structure. address. This improves efficiency and reduces memory fragmentation. From this we can see the subtleties of PHP HashTable design. If the data in the Bucket is not a pointer, pDataPtr is NULL.
All Buckets in HashTable form a doubly linked list through pListNext and pListLast. The latest inserted Bucket is placed at the end of this doubly linked list.
Note that in general, Bucket cannot provide information about the size of the data it stores. Therefore, in the implementation of PHP, the data saved in the Bucket must have the ability to manage its own size.