详解PHP中Array构造HashTable -PHP Tutorial-php.cn

详解PHP中Array结构HashTable

我们知道PHP中的Array在内部是以Hash的结构进行存储的。本文主要重点也是对PHP中Array的静态结构和动态结构进行分析和记录。

这里的静态结构，是指存储PHP中Array数据时使用的数据结构，即所谓的HashTable。

动态结构，是指程序在运行过程中，Array数据的存储状态。

首先PHP中的hashTable的结构如下：

typedef struct bucket {
    ulong h;                        /* Used for numeric indexing */
    uint nKeyLength;
    void *pData;
    void *pDataPtr;
    struct bucket *pListNext;
    struct bucket *pListLast;
    struct bucket *pNext;
    struct bucket *pLast;
    char *arKey;
} Bucket;


typedef struct _hashtable {
    uint nTableSize;
    uint nTableMask;
    uint nNumOfElements;
    ulong nNextFreeElement;
    Bucket *pInternalPointer;   /* Used for element traversal */
    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;

Copy after login

一个PHP中的Array在内部对应一个HashTable,HashTable内部的四个Bucket类型的指针数据记录着数组实际存储的元素内容的地址。具体的内容，各字段名都可以自解释，不做多说明了。

如果只看这几行代码，可能无法理解PHP数组实际的工作原理，接下来，我们可以手工模拟一下PHP数组中的一些最简单的操作。

1. 从无到有

HashTable的初始化，首先需要给一个HashTable构造一个内存空间，具体代码如下：

//hash_func_t在函数内用不到，hash函数在PHP范围内都是固定的
int _zend_hash_init(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC)
{
    uint i = 3;

    SET_INCONSISTENT(HT_OK);

    if (nSize >= 0x80000000) {
        /* prevent overflow */
        ht->nTableSize = 0x80000000;
    } else {
        while ((1U nTableSize = 1 nTableMask = 0; /* 0 means that ht->arBuckets is uninitialized */
    ht->pDestructor = pDestructor;
    ht->arBuckets = (Bucket**)&uninitialized_bucket; ? //实际的数据存储空间还未创建
    ht->pListHead = NULL;
    ht->pListTail = NULL;
    ht->nNumOfElements = 0; ? ? ? ? ? ? ? ? ? //表示数组内还没有一个元素，
    ht->nNextFreeElement = 0;
    ht->pInternalPointer = NULL;
    ht->persistent = persistent;
    ht->nApplyCount = 0;
    ht->bApplyProtection = 1;
    return SUCCESS;
}

Copy after login

上述代码可以理解为，为数组构造了一个总的大门，数据都可以经由这个门进入到自己对应的内存块中。当然现在门里还没有“座位”呢。

2. 数据插入

对于一个一无所有的空间，怎么给它加点东西呢？这就是数据的插入，即数据是如何保存到这个HashTable中的。

PHP的数组索引可以是数值或字符串，我们首先看字符串的索引如何存储，代码如下：

int _zend_hash_add_or_update(HashTable *ht, const char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC)
{
	ulong h;
	uint nIndex;
	Bucket *p;

	IS_CONSISTENT(ht);

	if (nKeyLength nTableMask;

	p = ht->arBuckets[nIndex];
	while (p != NULL) {
		if (p->arKey == arKey ||
			((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) {
				if (flag & HASH_ADD) {
					return FAILURE;
				}
				HANDLE_BLOCK_INTERRUPTIONS();
#if ZEND_DEBUG
				if (p->pData == pData) {
					ZEND_PUTS("Fatal error in zend_hash_update: p->pData == pData\n");
					HANDLE_UNBLOCK_INTERRUPTIONS();
					return FAILURE;
				}
#endif
				if (ht->pDestructor) {
					ht->pDestructor(p->pData);
				}
				UPDATE_DATA(ht, p, pData, nDataSize);
				if (pDest) {
					*pDest = p->pData;
				}
				HANDLE_UNBLOCK_INTERRUPTIONS();
				return SUCCESS; ?//更新之后直接退出
		}
		p = p->pNext;
	}
	
	if (IS_INTERNED(arKey)) {
		p = (Bucket *) pemalloc(sizeof(Bucket), ht->persistent);
		if (!p) {
			return FAILURE;
		}
		p->arKey = (char*)arKey;
	} else {
		p = (Bucket *) pemalloc(sizeof(Bucket) + nKeyLength, ht->persistent);
		if (!p) {
			return FAILURE;
		}
		p->arKey = (char*)(p + 1);
		memcpy(p->arKey, arKey, nKeyLength);
	}
	p->nKeyLength = nKeyLength;
	INIT_DATA(ht, p, pData, nDataSize);
	p->h = h;
	CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
	if (pDest) {
		*pDest = p->pData;
	}

	HANDLE_BLOCK_INTERRUPTIONS();
	CONNECT_TO_GLOBAL_DLLIST(p, ht);
	ht->arBuckets[nIndex] = p;
	HANDLE_UNBLOCK_INTERRUPTIONS();

	ht->nNumOfElements++;
	ZEND_HASH_IF_FULL_DO_RESIZE(ht);		/* If the Hash table is full, resize it */
	return SUCCESS;
}

Copy after login

首先，检查数组空间是否初始化，代码如下：

#define CHECK_INIT(ht) do {                                             \
    if (UNEXPECTED((ht)->nTableMask == 0)) {                                \
        (ht)->arBuckets = (Bucket **) pecalloc((ht)->nTableSize, sizeof(Bucket *), (ht)->persistent);   \
        (ht)->nTableMask = (ht)->nTableSize - 1;                        \
    }                                                                   \
} while (0)

Copy after login

然后计算要插入的字符串索引的hash值，并与nTableMask做按位与，得到nindex，这个nIndex就是对应的bucket*在二维数组arBucket**中的偏移量。根据代码逻辑，如果nIndex位置不为空，则说明当前计算得到的hash值之前存在。如果连key也相同并且flag为HASH_ADD则失败，否则就是更新操作。如果是更新操作则不会对现有数组结构有任何影响，更新了对应的值之后直接退出即可。

在需要有新元素插入到HashTable时，构造好的新元素会经过两步来链入该HashTable

第一步代码如下：

#define CONNECT_TO_BUCKET_DLLIST(element, list_head)        \
    (element)->pNext = (list_head);                         \
    (element)->pLast = NULL;                                \
    if ((element)->pNext) {                                 \
        (element)->pNext->pLast = (element);                \
    }

Copy after login

在这一步中如果新元素的key的hash值之前存在过，则list_head为HashTable.arBucket[nIndex],nIndex怎么来的前面已经说过了。在这一步过后会将HashTable.arBucket[nIndex]赋值为当前的新元素，你懂得。

如果新元素的key对应的hash之前没有存在过，则list_head就为NULL，因为HashTable.arBucket[nIndex]为NULL。你也懂得。

第二步代码如下：

#define CONNECT_TO_GLOBAL_DLLIST(element, ht)               \
    (element)->pListLast = (ht)->pListTail;                 \
    (ht)->pListTail = (element);                            \
    (element)->pListNext = NULL;                            \
    if ((element)->pListLast != NULL) {                     \
        (element)->pListLast->pListNext = (element);        \
    }                                                       \
    if (!(ht)->pListHead) {                                 \
        (ht)->pListHead = (element);                        \
    }                                                       \
    if ((ht)->pInternalPointer == NULL) {                   \
        (ht)->pInternalPointer = (element);                 \
    }

Copy after login

关于这一步会对HashTable的内容有什么样的影响，请参看下面的动态示例。相信你也懂得。

动态示例：

现在我们假设数组中没有任何元素，则进行插入操作。现在我们按照代码的逻辑，手动模拟一下数据插入的过程：

插入第一个元素A,假设其key对应的hash值为1

则插入之后，内存中的状态如下：

HashTable.arBucket[1]=A;

HashTable.pListHead = A

HashTable.pListTail = A

HashTable.pInternalPointer = A

A.pNext = null

A.pLast = null

A.pListLast = null

A.pListNext = null

插入第二个元素B，假设其key对应的hash值为2

则插入之后内存的状态如下：

HashTable.arBucket[2] = B;

HashTable.pListHead = A

HashTable.pListTail = B

HashTable.pInternalPointer = A?????? //这个只在第一次的时候设置

A.pNext=null

A.pLast = null

A.pListNext = B

A.pListLast = null

B.pListLast = A

B.pListNext = null

B.pNext = null

B.pLast = null

插入第三个元素C，假设其key的hash值为1，和A相同

则插入之后内存状态如下：

HashTable.arBucket[1] = C;

HashTable.pListHead = A

HashTable.pListTail =C

HashTable.pInternalPointer = A?????? //这个只在第一次的时候设置

A.pNext=null

A.pLast = C

A.pListNext = B

A.pListLast = null

B.pNext = null

B.pLast = null

B.pListLast = A

B.pListNext = C

C.pNext = A

C.pLast = null

C.pListNext = null

C.pListLast = B

插入A，B，C三个值之后的内存中状态即为：

HashTable.arBucket[1] = C;

HashTable.pListHead = A

HashTable.pListTail =C

HashTable.pInternalPointer = A

A.pNext=null

A.pLast = C

A.pListNext = B

A.pListLast = null

B.pNext = null

B.pLast = null

B.pListLast = A

B.pListNext = C

C.pNext = A

C.pLast = null

C.pListNext = null

C.pListLast = B

OK，A、B、C三个元素都已插入了，现在我们要实现两个任务：

查找某key的元素值(value)：

如果我们要访问A元素，则提供A的key：key_a,得到对应的hash值为1

然后找HastTable.arBucket[1]。这时HastTable.arBucket[1]其实为C不是A，但由于C的key不等于A的key，因此，要沿着pNext的指针找下去，直到NULL，而此时C.pNext就是A，即找到了key_a对应的值A。

总之由key查找一个元素时，首先要hash，然后顺着hash后的索引位置的pNext指针一直找下去，直到NULL，如果遇到了和要查找的key相同的值，则找到，否则找不到。

遍历数组：

由于我们的例子中的key是字符串类型的，全部循环遍历不能用for。只能用foreach，那foreach的遍历是如何实现的呢？

简单，根据最后的HashTable的状态，我们从HastTable.pListHead开始沿着pListNext指针顺序找下去即可了。以本文例子为例，则结果为：

HashTable.pListHead====>A

A.pListNext?????????????????? ====>B

B.pListNext?????????????????? ====>C

则最后的遍历顺序就是A，B，C，发现foreach的遍历顺序是和元素插入到数组的顺序相关的。

如果插入的元素的key不是字符串，而是数值。则可以省去做计算hash值这一步，直接拿数值的key做为hash值使用。

这样就不存在hash冲突的问题，这样也就不会用到每个元素的pNext、pLast两个指针了，这两个指针都只会是NULL。

这样我们可以通过使用for循环来遍历数组了，因为不存在hash冲突。

同样，如果我们使用foreach来遍历数组的话，遍历顺序还是元素的插入顺序，这个你当然懂得。

ps：

本文并未对zend中的hash结够做全面的记录，只是对本文主题涉及到的逻辑的重点代码进行了分析和演示。同时也为了能抓住重点。有些代码并未列出，如：再hash的逻辑，和索引为数值类型数据的代码等。这些可在代码文件Zend/zend_hash.c中找到详细内容。

Php8, I'm coming too

Learn website layout in 30 minutes

Shangguan Oracle Beginner to Proficient Video Tutorial

Your first line of UNI-APP code

Flutter from scratch to app launch

Brother Lian New Linux Video Tutorial

AXURE 9 Video Tutorial (Suitable for Product Manager Interactive Product Design UI)

Zero Basic Proficiency PS Video Tutorial

16 day UI video tutorial to get you started

PS Techniques and Slicing Techniques Video Tutorial

Alibaba Cloud Environment Construction and Project Launch Video Tutorial

Overview of Computer Networks - Basic Knowledge that Programmers Must Master

Essential Tutorial for Programmers - HTTP Protocol Explanation

Websocket Video Tutorial

详解PHP中Array构造HashTable