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

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下一页阅读全文

(0)

相关推荐

  • Zend Framework教程之Zend_Db_Table用法详解

    本文实例讲述了Zend_Db_Table用法.分享给大家供大家参考,具体如下: 1. 简介 Zend_Db_Table 是Zend Framework的表模块.它通过zend_db_adapter连接到 数据库,为数据库模式检查表对象,并对该表进行操作和查询. 2. 开始 首先需要为抽象类zend_db_table(ares注:该类为抽象类,所以不能直接实例 化,只能先继承该类,然后实例化子类)设定一个默认对数据库adapter;除非你 指定其他类型数据库adapter,否则,所有的zend_d

  • Zend Framework教程之Application和Bootstrap用法详解

    本文实例讲述了Zend Framework教程之Application和Bootstrap用法.分享给大家供大家参考,具体如下: 在一个MVC应用程序中,我们需要初始化建立数据库链接,配置视图和视图助手,配置布局,注册相关插件,注册action 助手等等,这些配置和准备工作我们都需要一一完成.有时候可能有一些初始化操作需要,但是在有些情况下这些初始化可能不需要.通过Zend_Application不仅仅可以完成这些操作,而且可以让这些配置和初始化工作更统一有序,重用性更高. Zend_Appli

  • Zend Framework教程之Zend_Db_Table_Row用法实例分析

    本文实例讲述了Zend Framework教程之Zend_Db_Table_Row用法.分享给大家供大家参考,具体如下: 1. 简介 Zend_Db_Table_Row是Zend Framework的行数据网关.通常来说,你不可以自己实例化Zend_Db_Table_Row, 而是通过调用Zend_Db_Table::find()方法或者Zend_Db_Table::fetchRow()方法将Zend_Db_Table_Row作为 结果数据返回过来.一旦你得到来一个Zend_Db_Table_R

  • Zend Framework+smarty用法实例详解

    本文实例讲述了Zend Framework+smarty用法.分享给大家供大家参考,具体如下: 一.Zend Framework简介 Zend Framework使用模型-视图-控制器(Model-View-Controller(MVC))结构.这个用来把你的程序分离成不同部分使得开发和维护变得容易. 运行Zend Framework需要:PHP 5.1.4 (或更高) .Web 服务器支持 mod_rewrite功能,本实例采用Apache. 从这里http://framework.zend.

  • Zend Framework教程之Zend_Controller_Plugin插件用法详解

    本文实例讲述了Zend Framework教程之Zend_Controller_Plugin插件用法.分享给大家供大家参考,具体如下: 通过Zend_Controller_Plugin可以向前端控制器增加附加的功能.便于w一些特殊功能.以下是Zend_Controller_Plugin的简单介绍. Zend_Controller_Plugin的基本实现 ├── Plugin │   ├── Abstract.php │   ├── ActionStack.php │   ├── Broker.p

  • Zend Framework教程之Loader以及PluginLoader用法详解

    本文实例分析了Zend Framework中Loader以及PluginLoader用法.分享给大家供大家参考,具体如下: Zend Framework提供了Zend_Loader,用来动态加载文件. 以下是具体用法,以及具体实现: 1.加载文件 使用方法: Zend_Loader::loadFile($filename, $dirs=null, $once=false); 具体实现: /** * Loads a PHP file. This is a wrapper for PHP's inc

  • zf框架的db类select查询器join链表使用示例(zend框架)

    zend框架的查询器join()链表使用示例 复制代码 代码如下: <?php//引入Loader类(自动加载类)require_once("Zend/Loader.php");//使用Loader类引入一个Db类Zend_Loader::loadClass("Zend_Db");//引入Zend_Db的状态器Zend_Loader::loadClass("Zend_Db_Statement_Pdo");//配置数据库连接信息$Config

  • Zend Framework教程之Resource Autoloading用法实例

    本文实例讲述了Zend Framework中Resource Autoloading用法.分享给大家供大家参考,具体如下: 通常,在开发应用程序中,可能类文件名不能按照标准Zend Framework的建议定义的,这意味着你的类文件不能被自动加载器发现.Zend_Loader_Autoloader_Resource提供了解决方案. 资源仅仅是一个名称对应一个组件的命名空间(追加到自动加载器的命名空间)和路径(相对的自动加载器的基本路径),例如可以这样: $loader = new Zend_Ap

  • Zend Framework教程之MVC框架的Controller用法分析

    本文讲述了Zend Framework教程之MVC框架的Controller用法.分享给大家供大家参考,具体如下: 这里简单讲讲MVC模式中Controller的基本使用方法. 基本使用实例: root@coder-671T-M:/www/zf_demo1/application# tree. ├── Bootstrap.php ├── configs │   └── application.ini ├── controllers │   ├── ErrorController.php │  

  • Zend Framework入门知识点小结

    本文总结分析了Zend Framework入门知识点.分享给大家供大家参考,具体如下: zend framework是MVC模式的一种实现,要快速的入门差不多只看Zend_Controller Zend_View 部分就可以了吧. 1.Zend_Controller部分.最重要的类是Zend_Controller_Front.使用它的经典代码很 简单: $front=Zend_Controller_Front::getInstance(); $front-> setControllerDirec

  • Zend Framework缓存Cache用法简单实例

    本文实例讲述了Zend Framework缓存Cache用法.分享给大家供大家参考,具体如下: <?php require 'Zend/Loader.php'; Zend_Loader::loadClass('Zend_Cache'); Zend_Loader::loadClass('Zend_Config'); Zend_Loader::loadClass('Zend_Registry'); $config = new Zend_Config_Ini('configsecr/config.in

  • Zend Framework教程之路由功能Zend_Controller_Router详解

    本文实例讲述了Zend Framework教程之路由功能Zend_Controller_Router用法.分享给大家供大家参考,具体如下: Zend Framework的路由提供了两个主要功能路由和创建路由. Zend_Controller_Router的Route类和相应Route目录下的类定义常见的路由操作. 接口Zend_Controller_Router_Interface,类Zend_Controller_Router_Abstract和Zend_Controller_Router_R

  • Zend Framework连接Mysql数据库实例分析

    本文实例讲述了Zend Framework连接Mysql数据库的方法.分享给大家供大家参考,具体如下: 在看这些之前请确保你正确加载了PDO扩展.做法是编辑php.ini . 手动增加这两行(前面要没有分号;): extension=php_pdo.dll extension=php_pdo_mysql.dll 然后要把extension_dir 指向php_pdo.dll及php_pdo_mysql.dll所在目录,如 extension_dir = "C:/php5/ext" OK

  • Zend Framework教程之Autoloading用法详解

    本文实例讲述了Zend Framework教程之Autoloading用法.分享给大家供大家参考,具体如下: 一.概述 自动加载是一种机制,无需依赖手动编写PHP代码.参考»PHP手册自动加载,一旦自动加载器被定义,你试图使用一个没有定义的类或接口的情况下,它会自动被调用. 使用自动加载,在项目中你不必担心类的存放位置.定义一个良好定义的自动加载器,您不需要考虑一个类文件相对于当前类文件的位置,您只需使用类,自动加载器将自动查找文件. 此外,自动加载,确保只加载一次,提升了性能 -所以可以用它替

随机推荐