PHP Source Code Analysis Zend HashTable Detailed Explanation Page 1/3

HashTable is also called a hash table and hash table in the usual data structure textbook. 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 of great help to us when analyzing the source code of PHP, especially the implementation of virtual machines in Zend Engine. It can help us simulate the image of a complete virtual machine in our brain. It is also the basis for the implementation of some other data structures such as arrays in PHP.
The implementation of Zend HashTable combines the advantages of two data structures: bidirectional linked list and vector (array), providing PHP with a very efficient data storage and query mechanism.
Let's begin!
1. HashTable's data structure
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 hold data, while 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 throughout the HashTable and cannot be repeated. The data element 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 of length 1, it does not mean that the key can only be one character. In fact, a Bucket is a variable-length structure. Since arKey is the last member variable of the 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 way to represent key names is indexing. At this time, nKeyLength is always 0, and the long integer field h represents the key name of the data element. Simply put, 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, at this time it saves the hash value corresponding to arKey. No matter how the hash function is designed, conflicts are inevitable, that is, different arKeys may have the same hash value. Buckets with the same hash value are saved in the bucket column corresponding to the same index of the arBuckets array of HashTable (see explanation below). This bucket column is a bidirectional linked list, with forward elements and backward elements represented by pLast and pNext respectively. The newly inserted bucket is placed at the front of the bucket column.
In a bucket, the actual data is stored in the memory block pointed to by the pData pointer, which is usually allocated by the system. But there is an exception, that is, when the data saved by the Bucket is a pointer, HashTable will not request the system to allocate space to save the pointer, but will directly save the pointer to pDataPtr, and then point pData to the address of the member of this structure. This can improve efficiency and reduce memory fragmentation. From this we can see the exquisiteness of PHP HashTable design. If the data in the bucket is not a pointer, pDataPtr is NULL.
All Buckets in HashTable form a bidirectional linked list through pListNext and pListLast. The latest inserted bucket is placed at the end of this bidirectional linked list.
Note that in general, a Bucket cannot provide information on the size of the data it stores. Therefore, in PHP implementation, the data saved in the bucket must have the ability to manage its own size.