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

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 helps 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), providing PHP with a very efficient data storage and query mechanism.
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).

Copy the code The code is as follows:

typedef struct bucket {
ulong h; /* Used for numeric indexing */
uint nKeyLength; /* key length*/
void *pData; /* Point to Bucket Pointer to saved data*/
void *pDataPtr; /* Pointer data*/
struct bucket *pListNext; /* Points to the next element in the HashTable bucket column*/
struct bucket *pListLast; /* Points to the previous element in the HashTable bucket column An element*/
struct bucket *pNext; /* Points to the next element of the bucket list with the same hash value*/
struct bucket *pLast; /* Points to the previous element of the bucket list with the same hash value*/
char arKey[1]; /* Must be the last member, key name*/
} Bucket;

In Zend HashTable, each data element (Bucket) has a key name (key), which is in the entire HashTable is unique and cannot be repeated. The data elements in the HashTable can be uniquely determined based on the key name. There are two ways of expressing 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. the address of. 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 under normal circumstances, 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.

Copy code The code is as follows:

typedef struct _hashtable {
uint nTableSize;
uint nTableMask;
uint nNumOfElements;
ulong nNextFreeElement;
Bucket *pInternalPointer;
Bucket *pListHead;
Bucket *pListTail;
Bucket **arBuckets;
dtor_func_t pDestructor;
zend_bool persistent;
unsigned char nApplyCount;
zend_bool bApplyProtection;
#if ZEND_DEBUG
int inconsistent;
#endif
} HashTable;

Current page 1/3 123Next page

The above introduces hashtable PHP source code analysis Zend HashTable detailed explanation page 1/3, including hashtable content, I hope it will be helpful to friends who are interested in PHP tutorials.