PHP内核介绍及扩展开发指南—基础知识
| sp; 总的来说，Zend的HashTable是一种链表散列，同时也为线性遍历进行了优化，图示如下：  HashTable中包含两种数据结构，一个链表散列和一个双向链表，前者用于进行快速键-值查询，后者方便线性遍历和排序，一个Bucket同时存在于这两个数据结构中。 关于该数据结构的几点解释： l 链表散列中为什么使用双向链表? 一般的链表散列只需要按key进行操作，只需要单链表就够了。但是，Zend有时需要从链表散列中删除给定的Bucket，使用双链表可以非常高效的实现。 l nTableMask是干什么的? 这个值用于hash值到arBuckets数组下标的转换。当初始化一个HashTable，Zend首先为arBuckets数组分配nTableSize大小的内存，nTableSize取不小于用户指定大小的最小的2^n，即二进制的10*。nTableMask = nTableSize – 1，即二进制的01*，此时h & nTableMask就恰好落在 [0, nTableSize – 1] 里，Zend就以其为index来访问arBuckets数组。 l pDataPtr是干什么的? 通常情况下，当用户插入一个键值对时，Zend会将value复制一份，并将pData指向value副本。复制操作需要调用Zend内部例程 emalloc来分配内存，这是个非常耗时的操作，并且会消耗比value大的一块内存(多出的内存用于存放cookie)，如果value很小的话，将会造成较大的浪费。考虑到HashTable多用于存放指针值，于是Zend引入pDataPtr，当value小到和指针一样长时，Zend就直接将其复制到pDataPtr里，并且将pData指向pDataPtr。这就避免了emalloc操作，同时也有利于提高Cache命中率。 arKey大小为什么只有1?为什么不使用指针管理key? arKey是存放key的数组，但其大小却只有1，并不足以放下key。在HashTable的初始化函数里可以找到如下代码： 1p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent); 可见，Zend为一个Bucket分配了一块足够放下自己和key的内存， l 上半部分是Bucket，下半部分是key，而arKey“恰好”是Bucket的最后一个元素，于是就可以使用arKey来访问key了。这种手法在内存管理例程中最为常见，当分配内存时，实际上是分配了比指定大小要大的内存，多出的上半部分通常被称为cookie，它存储了这块内存的信息，比如块大小、上一块指针、下一块指针等，baidu的Transmit程序就使用了这种方法。 不用指针管理key，是为了减少一次emalloc操作，同时也可以提高Cache命中率。另一个必需的理由是，key绝大部分情况下是固定不变的，不会因为key变长了而导致重新分配整个Bucket。这同时也解释了为什么不把value也一起作为数组分配了——因为value是可变的。 1.2.2 PHP数组 关于HashTable还有一个疑问没有回答，就是nNextFreeElement是干什么的? 不同于一般的散列，Zend的HashTable允许用户直接指定hash值，而忽略key，甚至可以不指定key(此时，nKeyLength为0)。同时，HashTable也支持append操作，用户连hash值 |
凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢! |
