`

详解PHP中Array结构HashTable

PHPZendArrayhashTableforeach 
阅读更多

我们知道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 << i) < nSize) {
            i++;
        }
        ht->nTableSize = 1 << i;
    }

    ht->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 <= 0) {
#if ZEND_DEBUG
		ZEND_PUTS("zend_hash_update: Can't put in empty key\n");
#endif
		return FAILURE;
	}

	CHECK_INIT(ht);                            //检查数组空间是否初始化

	h = zend_inline_hash_func(arKey, nKeyLength); //计算字符串索引的hash值
	nIndex = h & ht->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中找到详细内容。

 

分享到：
| 再谈PHP中的str_repeat函数实现
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    c#数据结构之array,arraylist,hashtable,dictionary

    C#中有多种数据结构可以用来存储和管理数据，今天我们将讨论四种常用的数据结构：Array、ArrayList、Hashtable和Dictionary。这些数据结构都是_Collections_命名空间的一部分，提供了不同的方式来存储和检索数据。 ...

    深入PHP中的HashTable结构详解

    HashTable是Zend引擎中最重要、使用最广泛的数据结构，它被用来存储几乎所有的东西。1.2.1 数据结构HashTable数据结构定义如下：复制代码 代码如下:typedef struct bucket { ulong h; // 存放hash uint ...

    C#中关于序列化HashTable的具体用法详解

    ### C#中关于序列化`HashTable`的具体用法详解 #### 一、`HashTable`简介 在.NET Framework中，`HashTable`是`System.Collections`命名空间下提供的一个容器类，主要用于处理和表现键值对（key-value pairs）。键...

    C#中哈希表(HashTable)用法实例详解(添加/移除/判断/遍历/排序等)

    哈希表(HashTable)在C#编程语言中是一种常用的数据结构，它允许高效地存储和检索键值对数据。在.NET Framework中，`System.Collections`命名空间提供了`HashTable`类，用于存储和管理这些键值对。下面我们将深入探讨...

    C＃中的集合示例（Array,ArrayList,Hashtable,List）

    在C#编程语言中，集合是用于存储一组对象的数据结构。它们提供了方便的方式来组织和操作数据。本篇文章将深入探讨三种常见的集合类型：Array、ArrayList、Hashtable以及泛型的List，并提供相关的示例代码来帮助理解...

    哈希表 HashTable 数据结构

    数据结构（C语言版）实习，哈希表，取余，二次散列法解决冲突

    比较分析Vector、ArrayList和hashtable hashmap数据结构

    比较分析Vector、ArrayList和hashtable hashmap数据结构

    HashTable

    在计算机科学中，哈希表（HashTable）是一种数据结构，它实现了关联数组的抽象数据类型，能够快速地进行查找、插入和删除操作。哈希表通过将键（Key）映射到表中的一个位置来访问记录，从而实现了快速访问。本文将...

    WinFormHashTable最简单用法,.net hashtable ,hashtable ,hashtable用法

    哈希表（Hashtable）是.NET框架中的一种常用数据结构，主要用作键值对存储，它提供了快速的数据存取方式。在WinForm应用程序中，我们可能会利用Hashtable来管理各种对象，尤其是在需要高效查找和操作数据时。下面将...

    C# json 转hashtable

    与此相关的，`Hashtable`是.NET框架中的一个古老的集合类，用于存储键值对，它在早期的.NET应用中十分常见。然而，随着.NET Framework的发展，`Dictionary, TValue&gt;`逐渐取代了`Hashtable`，因为后者不支持泛型，且...

    详解C#中HashTable的用法

    在C#编程语言中，`Hashtable` 是 .NET Framework 的 `System.Collections` 命名空间内提供的一个数据结构，它作为一个容器，用于存储键值对（key-value pairs）。`Hashtable` 实现了 `IDictionary` 接口，允许通过键...

    asp.net遍历hashtable

    在ASP.NET中，Hashtable是一种常用的数据结构，它是一个键值对集合，允许程序员存储和检索对象。本篇文章将深入探讨如何在ASP.NET中遍历Hashtable，以及相关的重要知识点。 首先，理解Hashtable的基本概念至关重要...

    hashtable存储数据.rar

    在Java编程语言中，`Hashtable`是一个非常基础且重要的数据结构，它属于集合框架的一部分，提供了键值对（key-value pairs）的存储功能。`Hashtable`类是线程安全的，意味着在多线程环境下，它能确保数据的一致性和...

    C# .net HashTable

    **C# .NET HashTable 知识点详解** 在C# .NET编程环境中，`HashTable`类是一个非同步、无序的键值对集合，它提供了快速的数据存储和检索功能。`HashTable`类是基于哈希表数据结构实现的，这使得它能够通过键（key）...

    HashMap和HashTable的区别和不同

    ### HashMap与HashTable的区别详解 #### 引言 在Java编程中，`HashMap`与`HashTable`作为两种常用的数据结构，经常被用来存储键值对数据。尽管它们在功能上相似，但在实现细节、性能表现以及使用场景方面存在显著...

    HashTable 常用操作

    HashTable是一种非常重要的数据结构，在.NET Framework中，`System.Collections`命名空间提供了`Hashtable`类来实现基于键值对（key-value pair）存储的数据结构。在该数据结构中，每一个元素由一个键（key）和一个...

    C#-Hashtable应用

    Hashtable是C#编程语言中的一种内置数据结构，属于.NET Framework的System.Collections命名空间。它是一个基于散列的键值对集合，允许程序员快速查找、添加和删除元素。在本篇文档中，我们将深入探讨如何在C#中有效...

    hashtable和dictionary的探讨

    在编程领域，哈希表（Hashtable）和字典（Dictionary）是两种常用的数据结构，它们在存储和检索键值对时提供了高效的性能。本文将深入探讨这两种数据结构的原理、性能差异以及实际应用中的考虑因素。 哈希表，通常...

    集合类Array List HashTable实例操作练习

    集合类是用于存储和操作多个数据项的数据结构，在.NET框架中，集合类广泛应用于各种场景。本篇将对ArrayList和HashTable这两个常用集合类进行实例操作练习，详细解释如何对它们进行添加、遍历和移除等操作，并探讨...

Magicbox
Global site tag (gtag.js) - Google Analytics