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

0351-5608878

热门课程

PHP内核探索:PHP中的哈希表(一)

  • 时间:2016-07-07
  • 发布:太原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培训班

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

太原达内php机构

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

拉链法

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

太原达内php培训班

PHP的HashTable结构

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

(图片源自网络,侵权即删)

PHP内核hashtable的定义:

太原大呢iphp培训班

nTableSize,HashTable的大小,以2的倍数增长

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

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

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

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

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

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

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

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

persistent,标识内存分配函数,如果是TRUE,则使用操作系统本身的内存分配函数,否则使用PHP的内存分配函数

nApplyCount,保存当前bucket被递归访问的次数,防止多次递归

bApplyProtection,标识哈希表是否要使用递归保护,默认是1,要使用

举一个哈希与mask结合的例子:

太原达内php培训班

例如,”foo”真正的哈希值(使用DJBX33A哈希函数)是193491849。如果我们现在有64容量的哈希表,我们明显不能使用它作为数组的下标。取而代之的是通过应用哈希表的mask,然后只取哈希表的低位。

因此,在哈希表中,foo是保存在arBuckets中下标为9的bucket向量中。

上一篇:程序员的基础生存技能:搜索引擎
下一篇:PHP内核探索:PHP中的哈希表(二)

PHP autoload 机制详解

太原达内php培训班:10个值得深思的PHP面试问题

太原php培训班:10个值得深思的PHP面试问题(一)

选择城市和中心
贵州省

广西省

海南省