[PHP内核探索]PHP中的哈希表

在PHP内核中，其中一个很重要的数据结构就是HashTable。我们常用的数组，在内核中就是用HashTable来实现。那么，PHP的HashTable是怎么实现的呢？最近在看HashTable的数据结构，但是算法书籍里面没有具体的实现算法，刚好最近也在阅读PHP的源码，于是参考PHP的HashTable的实现，自己实现了一个简易版的HashTable，总结了一些心得，下面给大家分享一下。
笔者github上有一个简易版的HashTable的实现：HashTable实现
另外，我在github有对PHP源码更详细的注解。感兴趣的可以围观一下，给个star。PHP5.4源码注解。可以通过commit记录查看已添加的注解。
HashTable的介绍

哈希表是实现字典操作的一种有效数据结构。
定义

简单地说，HashTable(哈希表)就是一种键值对的数据结构。支持插入，查找，删除等操作。在一些合理的假设下，在哈希表中的所有操作的时间复杂度是O(1)(对相关证明感兴趣的可以自行查阅)。
实现哈希表的关键

在哈希表中，不是使用关键字做下标，而是通过哈希函数计算出key的哈希值作为下标，然后查找/删除时再计算出key的哈希值，从而快速定位元素保存的位置。
在一个哈希表中，不同的关键字可能会计算得到相同的哈希值，这叫做“哈希冲突”，就是处理两个或多个键的哈希值相同的情况。解决哈希冲突的方法有很多，开放寻址法，拉链法等等。
因此，实现一个好的哈希表的关键就是一个好的哈希函数和处理哈希冲突的方法。
Hash函数

判断一个哈希算法的好坏有以下四个定义：

• 一致性，等价的键必然产生相等的哈希值；
  
• 高效性，计算简便；
  
• 均匀性，均匀地对所有的键进行哈希。
  

哈希函数建立了关键值与哈希值的对应关系，即：h = hash_func(key)。对应关系见下图：

设计一个完美的哈希函数就交由专家去做吧，我们只管用已有的较成熟的哈希函数就好了。PHP内核使用的哈希函数是time33函数，又叫DJBX33A，其实现如下：
[code]static inline ulong zend_inline_hash_func(const char *arKey, uint nKeyLength){         register ulong hash = 5381;        /* variant with the hash unrolled eight times */        for (; nKeyLength >= 8; nKeyLength -= 8) {            hash = ((hash