search
HomeBackend DevelopmentPHP Tutorial 详解PHP中Array构造HashTable

详解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;

?

一个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;
}
?

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

?

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;
}

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

?

#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)
?

?

然后计算要插入的字符串索引的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);                \
    }

?

在这一步中如果新元素的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);                 \
    }
?

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

?

?

?

动态示例:

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

?

1.

插入第一个元素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

?

2.

插入第二个元素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

?

3.

插入第三个元素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三个元素都已插入了,现在我们要实现两个任务:

?

1.

查找某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相同的值,则找到,否则找不到。

?

2.

遍历数组:

由于我们的例子中的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中找到详细内容。

?

Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
PHP vs. Python: Understanding the DifferencesPHP vs. Python: Understanding the DifferencesApr 11, 2025 am 12:15 AM

PHP and Python each have their own advantages, and the choice should be based on project requirements. 1.PHP is suitable for web development, with simple syntax and high execution efficiency. 2. Python is suitable for data science and machine learning, with concise syntax and rich libraries.

PHP: Is It Dying or Simply Adapting?PHP: Is It Dying or Simply Adapting?Apr 11, 2025 am 12:13 AM

PHP is not dying, but constantly adapting and evolving. 1) PHP has undergone multiple version iterations since 1994 to adapt to new technology trends. 2) It is currently widely used in e-commerce, content management systems and other fields. 3) PHP8 introduces JIT compiler and other functions to improve performance and modernization. 4) Use OPcache and follow PSR-12 standards to optimize performance and code quality.

The Future of PHP: Adaptations and InnovationsThe Future of PHP: Adaptations and InnovationsApr 11, 2025 am 12:01 AM

The future of PHP will be achieved by adapting to new technology trends and introducing innovative features: 1) Adapting to cloud computing, containerization and microservice architectures, supporting Docker and Kubernetes; 2) introducing JIT compilers and enumeration types to improve performance and data processing efficiency; 3) Continuously optimize performance and promote best practices.

When would you use a trait versus an abstract class or interface in PHP?When would you use a trait versus an abstract class or interface in PHP?Apr 10, 2025 am 09:39 AM

In PHP, trait is suitable for situations where method reuse is required but not suitable for inheritance. 1) Trait allows multiplexing methods in classes to avoid multiple inheritance complexity. 2) When using trait, you need to pay attention to method conflicts, which can be resolved through the alternative and as keywords. 3) Overuse of trait should be avoided and its single responsibility should be maintained to optimize performance and improve code maintainability.

What is a Dependency Injection Container (DIC) and why use one in PHP?What is a Dependency Injection Container (DIC) and why use one in PHP?Apr 10, 2025 am 09:38 AM

Dependency Injection Container (DIC) is a tool that manages and provides object dependencies for use in PHP projects. The main benefits of DIC include: 1. Decoupling, making components independent, and the code is easy to maintain and test; 2. Flexibility, easy to replace or modify dependencies; 3. Testability, convenient for injecting mock objects for unit testing.

Explain the SPL SplFixedArray and its performance characteristics compared to regular PHP arrays.Explain the SPL SplFixedArray and its performance characteristics compared to regular PHP arrays.Apr 10, 2025 am 09:37 AM

SplFixedArray is a fixed-size array in PHP, suitable for scenarios where high performance and low memory usage are required. 1) It needs to specify the size when creating to avoid the overhead caused by dynamic adjustment. 2) Based on C language array, directly operates memory and fast access speed. 3) Suitable for large-scale data processing and memory-sensitive environments, but it needs to be used with caution because its size is fixed.

How does PHP handle file uploads securely?How does PHP handle file uploads securely?Apr 10, 2025 am 09:37 AM

PHP handles file uploads through the $\_FILES variable. The methods to ensure security include: 1. Check upload errors, 2. Verify file type and size, 3. Prevent file overwriting, 4. Move files to a permanent storage location.

What is the Null Coalescing Operator (??) and Null Coalescing Assignment Operator (??=)?What is the Null Coalescing Operator (??) and Null Coalescing Assignment Operator (??=)?Apr 10, 2025 am 09:33 AM

In JavaScript, you can use NullCoalescingOperator(??) and NullCoalescingAssignmentOperator(??=). 1.??Returns the first non-null or non-undefined operand. 2.??= Assign the variable to the value of the right operand, but only if the variable is null or undefined. These operators simplify code logic, improve readability and performance.

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
3 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Best Graphic Settings
3 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. How to Fix Audio if You Can't Hear Anyone
3 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
WWE 2K25: How To Unlock Everything In MyRise
3 weeks agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Dreamweaver Mac version

Dreamweaver Mac version

Visual web development tools

EditPlus Chinese cracked version

EditPlus Chinese cracked version

Small size, syntax highlighting, does not support code prompt function

WebStorm Mac version

WebStorm Mac version

Useful JavaScript development tools

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

Integrate Eclipse with SAP NetWeaver application server.

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)