PHP内核学习:PHP中的HashTable(一)

标签: hashtable, 哈希表, php内核

本文只讲了哈希表的基础概念等,尚未涉及PHP中哈希表的实现。
不想看,请略过

0x01 前言

HashTable(哈希表)对于PHP来说是一种非常重要的数据结构,PHP的变量、数组、类的属性和方法等都是通过哈希表来实现的。众所周知,PHP7的性能优化也是花了大力气来优化哈希表的实现方式。

相关内容参考鸟哥的PPT

本篇文章开始将陆续的分享关于哈希表和PHP中具体的应用实现。

0x02 关于HashTable(哈希表)

什么是哈希表?哈希表是一种通过哈希函数,将特定的键映射到特定值的一种数据结构,它维护键和值之间一一对应关系。

在数据结构相关书籍中大家可能见过一个词“散列表”,这里所说的散列表就是哈希表。哈希表是将键名Key用哈希函数计算后映射到表中的一个位置,实现直接定位到数据位置,提高访问速度。

理想情况下,哈希表的时间复杂度是O(1),数据项可以在哈希表长度无关的情况下,通过哈希函数hash(key)出一个值,然后在固定时间内定位到一个槽(bucket,表示哈希表中一个位置),时间主要消耗在哈希函数的计算和槽的定位上。

首先明确几个名词:

键(key):用于操作数据的标示,例如PHP数组中的索引,或者字符串键等等。
槽(slot/bucket):哈希表中用于保存数据的一个单元,也就是数据真正存放的容器。
哈希函数(hash function):将key映射(map)到数据应该存放的slot所在位置的函数。
哈希冲突(hash collision):哈希函数将两个不同的key映射到同一个索引的情况。

我们知道C语言的数组是用数字下标来查找数据元素的,而PHP的数组可以用字符串作为key来读取数据。我们可以把这个理解成一个加强版的C语言数组,即用hash(key)得到一个整数,作为C语言中数组的下标。
如图:

543fd66bbbc57.jpg

因为哈希表的长度是有限的,所以一定存在不同的数据项指向相同的位置(即hash(key1)和hash(key2)在哈希表中指向同一个bucket,哈希值不一定相同)。像这种两个元素被指向同一个槽(bucket)时,我们称为哈希碰撞。

所以哈希冲突是哈希表的一个缺点。

0x03 哈希冲突

解决哈希冲突一般有:

  1. 开放定址法
  2. 拉链法

1.开放定址法

开放定址法就是将哈希表中的空位置向处理地址冲突开放。具体做法是,当发生地址冲突时,从发生地址冲突的位置开始,使用某种方法在哈希表中形成一个探查序列。沿此序列依次检查,直到找到一个空闲位置把发生冲突的待插入数据写入。

产生探查序列的方法一般有:线性探查法、二次探查法和随机探查法。

1)线性探查法
线性探查法是开放定址法消除哈希冲突的最简单方法。原理就是将表长为m的哈希表看做是一个首尾相连的环型表,若在0 ~ m-1上发生冲突的位置是d,则依次探查d+1,d+2,d+3...m-1,0,1,2,3...d-1,直到找到空闲位置为止。

从原理中不难看出,线性探查法容易造成堆积现象,即hash(a)和hash(b)会争夺同一个后继散列位置的现象,导致不同的哈希值记录在同一个探查序列中,增加了探查序列的长度。

如图:先插入A,M已被占用,则继续向后探测三次后插入到蓝色方块;当插入B时,和A(蓝色块)冲突,则向后探查后插入。这导致两个本来不应该发生冲突的数据之间也会发生冲突。这种情况就叫做堆积现象。
20150901172910.png

为了减少堆积的发生,不能像线性探查法那样探查一个顺序的地址序列(相当于顺序查找),而应该使用探查序列跳跃式地散列在整个散列表中。

2)二次探查法
原理是在哈希值的基础上每次探查累加当前次数的平方。
二次探查法的探查序列是:
hi=(h(key)+i*i)%m 0≤i≤m-1,m为哈希表长度
即探查序列为d=hash(a),d+1,d+4,d+9...
该方法的缺陷是不易探查到整个散列空间。

3)双重散列法
该方法是开放定址法中最好的探查方法之一,它的探查序列是:
hi=(h(key)+i*h1(key))%m 0≤i≤m-1,m为哈希表长度
即,d=h(key),(d+h1(key))%m,(d+2h1(key))%m,…,等。
该方法使用了两个散列函数h(key)和h1(key),故也称为双散列函数探查法。

定义h1(key)的方法较多,但无论采用什么方法定义,都必须使h1(key)的值和m互素,才能使发生冲突的同义词地址均匀地分布在整个表中,否则可能造成同义词地址的循环计算。
【例】 若m为素数,则h1(key)取1到m-1之间的任何数均与m互素,因此,我们可以简单地将它定义为:
h1(key)=key%(m-2)+1
【例】对例9.1,我们可取h(key)=key%13,而h1(key)=key%11+1。
【例】若m是2的方幂,则h1(key)可取1到m-1之间的任何奇数。

2.拉链法

拉链法解决哈希冲突的方式是将冲突的元素链接成一个单链表,然后将单链表指向哈希表中冲突的位置。
若选定的哈希表长度为m,则可将哈希表定义为一个由m个头指针组成的指针数组T[0..m-1]。凡是哈希地址为i的结点,均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中,装填因子α可以大于1,但为了哈希表的性能,一般均取α≤1。

如图:1-12030113255c46.jpg

拉链法的优点:

与开放定址法相比,拉链法有如下几个优点:
  (1)拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;
  (2)由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;
  (3)开放定址法为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间;
  (4)在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表,删除结点不能简单地将被删结点的空间置为空,否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中,空地址单元(即开放地址)都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行删除操作,只能在被删结点上做删除标记,而不能真正删除结点。

拉链法的缺点:

拉链法的缺点是:指针需要额外的空间,故当结点规模较小时,开放定址法较为节省空间,而若将节省的指针空间用来扩大散列表的规模,可使装填因子变小,这又减少了开放定址法中的冲突,从而提高平均查找速度。

PHP使用的是拉链法解决哈希冲突,具体实现方式请关注后续文章。

关于PHP的哈希冲突bug


评论已关闭