详解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中找到详细内容。
?

许多用户在选择智能手表的时候都会选择的华为的品牌,其中华为GT3pro和GT4都是非常热门的选择,不少用户都很好奇华为GT3pro和GT4有什么区别,下面就就给大家介绍一下二者。华为GT3pro和GT4有什么区别一、外观GT4:46mm和41mm,材质是玻璃表镜+不锈钢机身+高分纤维后壳。GT3pro:46.6mm和42.9mm,材质是蓝宝石玻璃表镜+钛金属机身/陶瓷机身+陶瓷后壳二、健康GT4:采用最新的华为Truseen5.5+算法,结果会更加的精准。GT3pro:多了ECG心电图和血管及安

为什么截图工具在Windows11上不起作用了解问题的根本原因有助于找到正确的解决方案。以下是截图工具可能无法正常工作的主要原因:对焦助手已打开:这可以防止截图工具打开。应用程序损坏:如果截图工具在启动时崩溃,则可能已损坏。过时的图形驱动程序:不兼容的驱动程序可能会干扰截图工具。来自其他应用程序的干扰:其他正在运行的应用程序可能与截图工具冲突。证书已过期:升级过程中的错误可能会导致此issu简单的解决方案这些适合大多数用户,不需要任何特殊的技术知识。1.更新窗口和Microsoft应用商店应用程

Hash操作//为hash表中的字段赋值。成功返回1,失败返回0。若hash表不存在会先创建表再赋值,若字段已存在会覆盖旧值。$ret=$redis->hSet('user','realname','jetwu');//获取hash表中指定字段的值。若hash表不存在则返回false。$ret=$redis->hGet('user','rea

c语言中null和NULL的区别是:null是C语言中的一个宏定义,通常用来表示一个空指针,可以用于初始化指针变量,或者在条件语句中判断指针是否为空;NULL是C语言中的一个预定义常量,通常用来表示一个空值,用于表示一个空的指针、空的指针数组或者空的结构体指针。

第1部分:初始故障排除步骤检查苹果的系统状态:在深入研究复杂的解决方案之前,让我们从基础知识开始。问题可能不在于您的设备;苹果的服务器可能会关闭。访问Apple的系统状态页面,查看AppStore是否正常工作。如果有问题,您所能做的就是等待Apple修复它。检查您的互联网连接:确保您拥有稳定的互联网连接,因为“无法连接到AppStore”问题有时可归因于连接不良。尝试在Wi-Fi和移动数据之间切换或重置网络设置(“常规”>“重置”>“重置网络设置”>设置)。更新您的iOS版本:

Laravel是目前最为流行的PHPweb框架之一,为开发人员提供了许多强大的功能和组件,其中LaravelHash也是其中之一。LaravelHash是一个用于密码散列的PHP库,其可以用于保护密码的安全,并使应用程序的用户数据更加安全。在本文中,我们将了解LaravelHash的工作原理以及如何使用它来对密码进行散列和验证。前置知识在学习Lara

Java中使用Hashtable类的isEmpty()方法判断哈希表是否为空哈希表是Java集合框架中常用的数据结构之一,它实现了键值对的存储和检索。在Hashtable类中,isEmpty()方法用于判断哈希表是否为空。本文将介绍如何使用Hashtable类的isEmpty()方法,并提供相应的代码示例。首先,我们需要了解一下Hashtable类。Hash

在JavaScript 中,undefined和null都代表着“无”的概念:1、undefined 表示一个未初始化的变量或一个不存在的属性,当声明了一个变量但没有对其赋值时,这个变量的值就是undefined,访问对象中不存在的属性时,返回的值也是undefined;2、null表示一个空的对象引用,在某些情况下,可以将对象的引用设置为null,以便释放其占用的内存。


热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

AI Hentai Generator
免费生成ai无尽的。

热门文章

热工具

Atom编辑器mac版下载
最流行的的开源编辑器

Dreamweaver Mac版
视觉化网页开发工具

安全考试浏览器
Safe Exam Browser是一个安全的浏览器环境,用于安全地进行在线考试。该软件将任何计算机变成一个安全的工作站。它控制对任何实用工具的访问,并防止学生使用未经授权的资源。

DVWA
Damn Vulnerable Web App (DVWA) 是一个PHP/MySQL的Web应用程序,非常容易受到攻击。它的主要目标是成为安全专业人员在合法环境中测试自己的技能和工具的辅助工具,帮助Web开发人员更好地理解保护Web应用程序的过程,并帮助教师/学生在课堂环境中教授/学习Web应用程序安全。DVWA的目标是通过简单直接的界面练习一些最常见的Web漏洞,难度各不相同。请注意,该软件中

mPDF
mPDF是一个PHP库,可以从UTF-8编码的HTML生成PDF文件。原作者Ian Back编写mPDF以从他的网站上“即时”输出PDF文件,并处理不同的语言。与原始脚本如HTML2FPDF相比,它的速度较慢,并且在使用Unicode字体时生成的文件较大,但支持CSS样式等,并进行了大量增强。支持几乎所有语言,包括RTL(阿拉伯语和希伯来语)和CJK(中日韩)。支持嵌套的块级元素(如P、DIV),