文档章节

PHP中HASH函数的优化技巧

ChefXu
 ChefXu
发布于 2015/12/04 13:35
字数 1246
阅读 1.2K
收藏 35

Hash数据结构是一种非常常见的数据结构,作为一个程序员,你可能每天都在和它接触, 尽管很多时候你可能没有意识到。Hash在PHP内核中扮演了非常重要的角色,数组、变量作用域、函数参数列表等均是基于Hash实现。所以,在PHP里你能看到各种对于Hash的优化。


Hash数据结构

Hash数据结构,本质上为了解决计算机中真正意义的数组只能使用数字作为索引,而程序员却经常需要使用字符串或者其他更复杂的类型来作为数组key的问题。首先我们需要一个函数能把字符串转成数字。然后,由于数组的长度有限,我们还需要把这个数字映射到数组长度的区间里,一般使用取模操作。最后, 如果两个字符串最终计算出来的Hash值一样,将保存到数组相同的位置上,这种情况叫做Hash冲突。解决冲突的常见办法之一就是拉链法, 就是将Hash冲突的数据维护在一个链表里; 另一种比较常见的解决冲突的办法叫开放寻址。下图所示是一个典型的Hash结构:



Hash函数的最优情况是,将key平均分布在数组空间中, 这样能获得最大的性能。最坏的情况是完全冲突,这个时候Hash表事实上已经退化为一个链表。前几年比较火的Hash攻击事实上就是构造大量的冲突key,使PHP的POST数组退化为链表,从而耗尽服务器的CPU资源。

因此我们可以得出一个结论, 一个优秀的hash函数应该符合两点:足够随机分布,足够快


DJB2算法

PHP内核中的hash函数(http://www.cse.yorku.ca/~oz/hash.html)采用的是经典的djb2算法,源码为:

关于这个算法背后其实有很复杂的数学证明,我曾经看到过一篇文章给出了完整证明,受限于数学水平这里我只能从工程的角度来简单说一下结论:

  1. 奇数和素数能比偶数得到更随机的结果,所以可以看到hash函数里使用的是5381和33两个数。

  2. 为什么是5381?在这个讨论里(https://groups.google.com/forum/#!topic/comp.lang.c/lSKWXiuNOAk)谈到采用一个比255大而又不是特别大的素数都可以,djb2的作者也参与了讨论,他在讨论里说他选择了5381,只是因为5381符合这个条件, 并没有其他特殊的原因。

  3. 为什么是33?其实有很多数都可以,采用33是因为n*33可以优化为n << 5 + n,可以把一个耗时的乘法操作优化为移位操作,毕竟hash函数的效率是非常重要的。


我们看下PHP内核中的Hash函数实现:

可以看出来PHP采用的就是djb2算法,但是似乎和经典的djb2算法有些差距。其实是PHP内核开发者对这个函数做了进一步的优化。


达夫设备

达夫设备(https://zh.wikipedia.org/wiki/%E8%BE%BE%E5%A4%AB%E8%AE%BE%E5%A4%87)的本质在于减少循环次数。考虑下面的代码:

这段代码的特点是非常简单,简单到循环本身就占用了大多数性能开销,因为每次循环都需要做累减和比较。因此减少循环次数反而成为了优化重点,这种情况在系统底层的内存复制的场景中经常出现。PHP中的Hash函数就采用了达夫设备这种技巧来优化, 循环次数减少为原来的1/8。


顺便说一句,实际上最早的达夫设备程序版本是这样的:

而且这段代码真的能编译通过。


取模优化

计算出来hash值之后我们需要把hash值映射到数组中, 比如hash值为15,数组a长度为10,15%10得到5, 最终保存在a[5]的位置上。但是取模操作在特定条件下是可以优化的。在PHP内核中,hash table的大小会设定为2的n次方。当数组大小为2的n次方时, hash % ht->nTableSize 可以优化为 hash & (ht->nTableSize - 1),也就是把除法操作优化成了位操作。


结语

我们看到,一个简单的hash函数背后都蕴含了如此丰富的优化技巧,难怪都说PHP是世界上最好的语言 :) 。


© 著作权归作者所有

ChefXu
粉丝 13
博文 6
码字总数 11518
作品 0
海淀
程序员
私信 提问
加载中

评论(4)

假装在纽约
假装在纽约
结尾漂亮
ChefXu
ChefXu 博主

引用来自“AngusXer”的评论

其实这些是C开发者的必备技巧,这是算法之外的语言应用技巧。
我写代码一般都是这么干的……当然,不要忘了写修饰~
你说得对, 的确是一些基础技巧, 不过惊艳的性能也少不了这些细节优化。
手握华为赛神仙
手握华为赛神仙
其实这些是C开发者的必备技巧,这是算法之外的语言应用技巧。
我写代码一般都是这么干的……当然,不要忘了写修饰~
西南茂
西南茂
牛逼,收藏
深入理解PHP之数组遍历

本文地址: http://www.laruence.com/2009/08/23/1065.html 经常会有人问我, PHP的数组, 如果用foreach来访问, 遍历的顺序是固定的么? 以什么顺序遍历呢? 比如: $val) { //结果是什么? } 又比...

晨曦之光
2012/03/09
183
1
深入理解PHP之数组(遍历顺序)

经常会有人问我, PHP的数组, 如果用foreach来访问, 遍历的顺序是固定的么? 以什么顺序遍历呢? 比如: <?php $arr['laruence'] = 'huixinchen'; $arr['yahoo'] = 2007; $arr['baidu'] = 2008; ......

botkenni
2016/10/09
28
0
慎用php的array_search函数

arraysearch是phper使用频次非常高的一个数组函数,但是arraysearch也是经常被滥用的一个函数,比如假设下面这种业务场景,需要把两个大数组内相同的元素统计出来(恩,没错有个array_inter...

anoty
2018/08/10
259
0
SQL优化二(SQL性能调优)

一·、前言:这篇博文内容非原创,是我们公司的架构师给我们做技术培训的时候讲的内容,我稍微整理了下,借花献佛。这篇博文只是做一个大概的科普介绍,毕竟SQL优化的知识太大了,几乎可以用...

jmcui
2017/08/20
0
0
shen-go接下来的一些优化方向

shen-go接下来的一些优化方向 Arthur的博客2017-12-241 阅读 go优化方向 想不到居然已经时隔一个多月了, 接上篇 ,编译到字节码的工作算是基本完成。 shen-go 是shen语言在Go的实现。前几天...

Arthur的博客
2017/12/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Vue组件通信应知必知

前言 本章我们来学习Vue组件通信中的可以算是所有内容,在此之前,您最好掌握Vue的基础语法、指令等内容,同时也建议您查看我其他的文章进行补充。 组件通信 父子组件关系 通过上图顺带给大家...

涂老师
17分钟前
64
0
按下时会两次调用UILongPressGestureRecognizer

我正在检测用户是否已按下2秒钟: UILongPressGestureRecognizer *longPress = [[UILongPressGestureRecognizer alloc] initWithTarget:self......

javail
21分钟前
48
0
图示JVM工作原理

JDK,JRE,JVM的联系是啥? JVM Java Virtual Machine JDK Java Development Kit JRE Java Runtime Environment 看上图官方的介绍讲的很清楚 JVM的作用是啥? JVM有2个特别有意思的特性,语言...

erlieStar
29分钟前
59
0
webpack 阶段回顾 之 webpack-dev-server

webpack-dev-server是一个让我们可以模拟线上环境进行项目调试的工具 主要功能有: 路径重定向 浏览器中显示编译错误 接口代理 如解决跨域 热更新 使用步骤 安装webpack-dev-server 配置dev...

东东笔记
54分钟前
78
0
sql按任意时间段分组统计

任意时间序列数据都可以按时间分组。 timestamp 为时间戳。 按每五分钟统计日志的数目 select floor(cast(logs.timestamp as int) / 60 / 5) as dt, count(logs.id)from ( selec...

Mr小Z
今天
90
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部