PHP 源代码分析 Zend HashTable详解第1/3页_php技巧

HashTable在通常的数据结构教材中也称作散列表,哈希表。其基本原理比较简单(如果你对其不熟悉,请查阅随便一本数据结构教材或在网上搜索),但PHP的实现有其独特的地方。理解了HashTable的数据存储结构,对我们分析PHP的源代码,特别是Zend Engine中的虚拟机的实现时,有很重要的帮助。它可以帮助我们在大脑中模拟一个完整的虚拟机的形象。它也是PHP中其它一些数据结构如数组实现的基础。
Zend HashTable的实现结合了双向链表和向量(数组)两种数据结构的优点,为PHP提供了非常高效的数据存储和查询机制。
Let's begin!
一、 HashTable的数据结构
在Zend Engine中的HashTable的实现代码主要包括zend_hash.h, zend_hash.c这两个文件中。Zend HashTable包括两个主要的数据结构,其一是Bucket(桶)结构,另一个是HashTable结构。Bucket结构是用于保存数据的容器,而HashTable结构则提供了对所有这些Bucket(或桶列)进行管理的机制。

复制代码 代码如下:

typedef struct bucket {
ulong h; /* Used for numeric indexing */
uint nKeyLength; /* key 长度 */
void *pData; /* 指向Bucket中保存的数据的指针 */
void *pDataPtr; /* 指针数据 */
struct bucket *pListNext; /* 指向HashTable桶列中下一个元素 */
struct bucket *pListLast; /* 指向HashTable桶列中前一个元素 */
struct bucket *pNext; /* 指向具有同一个hash值的桶列的后一个元素 */
struct bucket *pLast; /* 指向具有同一个hash值的桶列的前一个元素 */
char arKey[1]; /* 必须是最后一个成员,key名称*/
} Bucket;

在Zend HashTable中,每个数据元素(Bucket)有一个键名(key),它在整个HashTable中是唯一的,不能重复。根据键名可以唯一确定HashTable中的数据元素。键名有两种表示方式。第一种方式使用字符串arKey作为键名,该字符串的长度为nKeyLength。注意到在上面的数据结构中arKey虽然只是一个长度为1的字符数组,但它并不意味着key只能是一个字符。实际上Bucket是一个可变长的结构体,由于arKey是Bucket的最后一个成员变量,通过arKey与nKeyLength结合可确定一个长度为nKeyLength的key。这是C语言编程中的一个比较常用的技巧。另一种键名的表示方式是索引方式,这时nKeyLength总是0,长整型字段h就表示该数据元素的键名。简单的来说,即如果nKeyLength=0,则键名为h;否则键名为arKey, 键名的长度为nKeyLength。
当nKeyLength > 0时,并不表示这时的h值就没有意义。事实上,此时它保存的是arKey对应的hash值。不管hash函数怎么设计,冲突都是不可避免的,也就是说不同的arKey可能有相同的hash值。具有相同hash值的Bucket保存在HashTable的arBuckets数组(参考下面的解释)的同一个索引对应的桶列中。这个桶列是一个双向链表,其前向元素,后向元素分别用pLast, pNext来表示。新插入的Bucket放在该桶列的最前面。
在Bucket中,实际的数据是保存在pData指针指向的内存块中,通常这个内存块是系统另外分配的。但有一种情况例外,就是当Bucket保存的数据是一个指针时,HashTable将不会另外请求系统分配空间来保存这个指针,而是直接将该指针保存到pDataPtr中,然后再将pData指向本结构成员的地址。这样可以提高效率,减少内存碎片。由此我们可以看到PHP HashTable设计的精妙之处。如果Bucket中的数据不是一个指针,pDataPtr为NULL。
HashTable中所有的Bucket通过pListNext, pListLast构成了一个双向链表。最新插入的Bucket放在这个双向链表的最后。
注意在一般情况下,Bucket并不能提供它所存储的数据大小的信息。所以在PHP的实现中,Bucket中保存的数据必须具有管理自身大小的能力。

复制代码 代码如下:

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;

当前1/3页 123下一页阅读全文

时间: 2024-09-24 15:20:47

PHP 源代码分析 Zend HashTable详解第1/3页_php技巧的相关文章

Win2003下IIS+PHP+MySQL+Zend配置步骤详解第1/2页_php技巧

一.软件的获取 1.php首先去http://www.php.net/downloads.php下载最新的PHP 5.2.0版本. 2.MySQL可以在http://dev.mysql.com/downloads/mysql/5.0.html#downloads下载到最新的5.0.xx版本. 3.Zend Optimizer可以去http://www.zend.com/free_download/optimizer下载最新的3.X.X版本. 4.phpmyadmin可以到http://www1.

PHP中session使用方法详解第1/2页_php技巧

由于 Session 是以文本文件形式存储在服务器端的,所以不怕客户端修改 Session 内容.实际上在服务器端的 Session 文件,PHP 自动修改 session 文件的权限,只保留了系统读和写权限,而且不能通过 ftp 修改,所以安全得多.PHPChina 开源社区门户 对于 Cookie 来说,假设我们要验证用户是否登陆,就必须在 Cookie 中保存用户名和密码(可能是 md5 加密后字符串),并在每次请求页面的时候进行验证.如果用户名和密码存储在数据库,每次都要执行一次数据库查

php代码出现错误分析详解第1/2页_php技巧

错误类型: 一.未使用二进制上传   代码:    Fatal error: This encoded file is corrupted. Please refer to http://www.zend.com/support/support_faq.php?id=loader_file_corrupt for further help in  /webhome/****.com/web/www/index.php on line 0  二.数据表中缺少字段   代码:    An error

举例详解PHP脚本的测试方法_php技巧

一.常用测试示例 我们经常会遇到这种情况:将一些没有经过任何测试的遗留代码进行重新编写测试,甚至这些代码还是用面向对象写的.要对这样的代码进行测试,我的建议是把代码分解成块,这样就容易测试了. 然而,这些遗留代码并不是那么好重构的,比如:测试前,你不能在把代码重新编写,这是为了避免影响原有程序,当然也不好进行单元测试. 在PHP程序中,通常有一部分代码是写在几个index.php和script.php文件中的,这些.php文件存放在几个不同的文件夹里.如果不找到它们的入口点,是无法直接由Web服

详解php的socket通信_php技巧

 对 TCP/IP . UDP . Socket 编程这些词你不会很陌生吧?随着网络技术的发展,这些词充斥着我们的耳朵. 那什么是TCP/IP.UDP? TCP/IP(Transmission Control Protocol/Internet Protocol)即传输控制协议/网间协议,是一个工业标准的协议集,它是为广域网(WANs)设计的. UDP(User Data Protocol,用户数据报协议)是与TCP相对应的协议.它是属于TCP/IP协议族中的一种. 这里有一张图,表明了这些协议

详解PHP实现执行定时任务_php技巧

PHP在这方面应该说是比较弱,如果只用php去实现可以如下: <?php ignore_user_abort();//关闭浏览器后,继续执行php代码 set_time_limit(0);//程序执行时间无限制 $sleep_time = 1;//多长时间执行一次 do{ $fp = fopen('test.txt','a+'); fwrite($fp,"这是一个php博客:phpddt.com \n"); fclose($fp); sleep($sleep_time); }wh

PHP冒泡算法详解(递归实现)_php技巧

实现 复制代码 代码如下: /*     冒泡算法(递归实现) */ function maoPao($array, $index=0) {     $count = count($array);     if(($count-1) <= $index)         return $array;     for($i=$count-1; $i>$index; $i-- )     {         if($array[$i] < $array[$i-1])         {   

PHP实现多进程并行操作的详解(可做守护进程)_php技巧

如下所示: 复制代码 代码如下: /** * 入口函数 * 将此文件保存为 ProcessOpera.php * 在terminal中运行 /usr/local/php/bin/php ProcessOpera.php & * 查看进程 ps aux|grep php */ProcessOpera("runCode", array(), 8); /** * run Code */function runCode($opt = array()) {   //需要在守护进程中运行的

解析用PHP读写音频文件信息的详解(支持WMA和MP3)_php技巧

复制代码 代码如下: <?php// AudioExif.class.php// 用PHP进行音频文件头部信息的读取与写入// 目前只支持 WMA 和 MP3 两种格式, 只支持常用的几个头部信息//// 写入信息支持: Title(名称), Artist(艺术家), Copyright(版权), Description (描述)//               Year(年代),  Genre (流派),   AlbumTitle (专辑标题)// 其中 mp3 和 wma 略有不同, 具体返