太原PHP培训
达内太原php培训中心

0351-5608878

热门课程

PHP内核探索之PHP中的哈希表(上)

  • 时间:2016-12-21
  • 发布:51CTO
  • 来源:51CTO

PHP内核探索之PHP中的哈希表(上)

PHP内核中,其中一个很重要的数据结构就是HashTable。我们常用的数组,在内核中就是用HashTable来实现。那么,PHPHashTable是怎么实现的呢?最近在看HashTable的数据结构,但是算法书籍里面没有具体的实现算法,刚好最近也在阅读PHP的源码,于是参考PHPHashTable的实现,自己实现了一个简易版的HashTable,总结了一些心得,下面给大家分享一下。

另外,我在github有对PHP源码更详细的注解。感兴趣的可以围观一下,给个star PHP5.4源码注解 。可以通过 commit记录 查看已添加的注解。

HashTable的介绍

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

定义

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

实现哈希表的关键

在哈希表中,不是使用关键字做下标,而是通过哈希函数计算出key的哈希值作为下标,然后查找/删除时再计算出key的哈希值,从而快速定位元素保存的位置。

在一个哈希表中,不同的关键字可能会计算得到相同的哈希值,这叫做哈希冲突,就是处理两个或多个键的哈希值相同的情况。解决哈希冲突的方法有很多,开放寻址法,拉链法等等。

因此,实现一个好的哈希表的关键就是一个好的哈希函数和处理哈希冲突的方法。

Hash函数

判断一个哈希算法的好坏有以下四个定义: > * 一致性,等价的键必然产生相等的哈希值; > * 高效性,计算简便; > * 均匀性,均匀地对所有的键进行哈希。

哈希函数建立了关键值与哈希值的对应关系,即:h = hash_func(key)

设计一个完美的哈希函数就交由专家去做吧,我们只管用已有的较成熟的哈希函数就好了。PHP内核使用的哈希函数是time33函数,又叫DJBX33A,其实现如下:

static inline ulong zend_inline_hash_func(const char *arKey, uint KeyLength)

{

register ulong hash = 5381;

/* variant with the hash unrolled eight times */

for (; nKeyLength >= 8; nKeyLength -= 8) {

hash = ((hash << 5) + hash) + *arKey++;

hash = ((hash << 5) + hash) + *arKey++;

hash = ((hash << 5) + hash) + *arKey++;

hash = ((hash << 5) + hash) + *arKey++;

hash = ((hash << 5) + hash) + *arKey++;

hash = ((hash << 5) + hash) + *arKey++;

hash = ((hash << 5) + hash) + *arKey++;

hash = ((hash << 5) + hash) + *arKey++;

}

switch (nKeyLength) {

case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */

case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */

case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */

case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */

case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */

case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */

case 1: hash = ((hash << 5) + hash) + *arKey++; break;

case 0: break;

EMPTY_SWITCH_DEFAULT_CASE()

}

return hash;

}

注:函数使用了一个8次循环+switch来实现,是对for循环的优化,减少循环的运行次数,然后在switch里面执行剩下的没有遍历到的元素。

拉链法

将所有具有相同哈希值的元素都保存在一条链表中的方法叫拉链法。查找的时候通过先计算key对应的哈希值,然后根据哈希值找到对应的链表,最后沿着链表顺序查找相应的值。

PHPHashTable结构

简单地介绍了哈希表的数据结构之后,继续看看PHP中是如何实现哈希表的。

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;

nTableSizeHashTable的大小,以2的倍数增长

nTableMask,用在与哈希值做与运算获得该哈希值的索引取值,arBuckets初始化后永远是nTableSize-1

nNumOfElementsHashTable当前拥有的元素个数,count函数直接返回这个值

nNextFreeElement,表示数字键值数组中下一个数字索引的位置

pInternalPointer,内部指针,指向当前成员,用于遍历元素

pListHead,指向HashTable的第一个元素,也是数组的第一个元素

pListTail,指向HashTable的最后一个元素,也是数组的最后一个元素。与上面的指针结合,在遍历数组时非常方便,比如resetendAPI

arBuckets,包含bucket组成的双向链表的数组,索引用key的哈希值和nTableMask做与运算生成

pDestructor,删除哈希表中的元素使用的析构函数

好了,今天就给大家讲这么多吧,喜欢我的内容可以关注或者分享(微信公众平台:tytedu)选择太原达内培训,不再孤军奋战,轻轻松松做IT高薪白领。太原达内培训带领有明确目标的学子迈向成功之路!

上一篇:PHP之二分法
下一篇:PHP内核探索之PHP中的哈希表(下)

PHP中十六个魔术方法详解(三)

CakePHP 3.4.4 发布,PHP 开发框架

JavaScript 与 Java、PHP 的比较

太原php培训资源站

选择城市和中心
贵州省

广西省

海南省