站长网_站长创业_站长主页_站长之家_易采站长站

会员投稿 投稿指南 站长资讯通告: PHP实现的QQ空间g_tk加密算法
搜索:
您的位置: 主页 > 教程 > 网页编程 > PHP编程 > » 正文

深入PHP中的HashTable结构详解

来源: 易采站长站

HashTable是Zend引擎中最重要、使用最广泛的数据结构,它被用来存储几乎所有的东西。
1.2.1 数据结构
HashTable数据结构定义如下:
代码如下:
typedef struct bucket {
 ulong h;    // 存放hash
 uint nKeyLength;
 void *pData;   // 指向value,是用户数据的副本
 void *pDataPtr;
 struct bucket *pListNext; // pListNext和pListLast组成
 struct bucket *pListLast; // 整个HashTable的双链表
 struct bucket *pNext;  // pNext和pLast用于组成某个hash对应
 struct bucket *pLast;  // 的双链表
 char arKey[1];    // key
} Bucket;

typedef struct _hashtable {
 uint nTableSize;
 uint nTableMask;
 uint nNumOfElements;
 ulong nNextFreeElement;
 Bucket *pInternalPointer; /* Used for element traversal */
 Bucket *pListHead;
 Bucket *pListTail;
 Bucket **arBuckets;   // hash数组
 dtor_func_t pDestructor; // HashTable初始化时指定,销毁Bucket时调用
 zend_bool persistent;  // 是否采用C的内存分配例程
 unsigned char nApplyCount;
 zend_bool bApplyProtection;
#if ZEND_DEBUG
 int inconsistent;
#endif
} HashTable;

总的来说,Zend的HashTable是一种链表散列,同时也为线性遍历进行了优化,图示如下:


HashTable中包含两种数据结构,一个链表散列和一个双向链表,前者用于进行快速键-值查询,后者方便线性遍历和排序,一个Bucket同时存在于这两个数据结构中。
关于该数据结构的几点解释:
链表散列中为什么使用双向链表?
一般的链表散列只需要按key进行操作,只需要单链表就够了。但是,Zend有时需要从链表散列中删除给定的Bucket,使用双链表可以非常高效的实现。
nTableMask是干什么的?
这个值用于hash值到arBuckets数组下标的转换。当初始化一个HashTable,Zend首先为arBuckets数组分配nTableSize大小的内存,nTableSize取不小于用户指定大小的最小的2^n,即二进制的10*。nTableMask = nTableSize – 1,即二进制的01*,此时h & nTableMask就恰好落在 [0, nTableSize – 1] 里,Zend就以其为index来访问arBuckets数组。
pDataPtr是干什么的?
通常情况下,当用户插入一个键值对时,Zend会将value复制一份,并将pData指向value副本。复制操作需要调用Zend内部例程 emalloc来分配内存,这是个非常耗时的操作,并且会消耗比value大的一块内存(多出的内存用于存放cookie),如果value很小的话,将会造成较大的浪费。考虑到HashTable多用于存放指针值,于是Zend引入pDataPtr,当value小到和指针一样长时,Zend就直接将其复制到pDataPtr里,并且将pData指向pDataPtr。这就避免了emalloc操作,同时也有利于提高Cache命中率。

Tags:
最新图文资讯
1 2 3 4 5 6
相关文章列表:
易采站长站 - 联系我们 - 广告服务 - 友情链接 - 网站地图 - 版权声明 - 人才招聘 - 帮助 -