深入PHP内核.doc

【问底】王帅：深入PHP内核（三）——内核利器哈希表与哈希碰撞攻击 发表于2014-10-16 22:26|?7006次阅读| 来源CSDN|?20?条评论| 作者王帅 问底王帅PHP 摘要：PHP作为一门简单而强大的语言，能够提供很多Web适用的语言特性。从实践出发，继弱类型变量原理探究后，王帅将继续带大家弄清PHP内核中的一些常用部分，本期则是内核利器哈希表与哈希碰撞攻击。 【导读】王帅在海量分布式Web系统有超过8年沉淀，主导过多个大型系统的架构设计，目前在腾讯企业SaaS团队。 PHP内核系列文章，是作者在PHP领域实践中，把相关原理性的知识，通过更便于理解的方式，系统整理出来分享给读者。希望通过PHP原理性的轻量解读，对这门Web领域最热门技术的优秀架构分析解构，让更多的人不断的深入了解语言的原理本身，更容易定位、理解一些问题背后原因，更游刃有余的做基础架构设计。同时希望影响更多的人才投入Web开源领域，不仅是应用和学习一门技术、组件，同样能够贡献更多高质量组件，像战国时期的百家争鸣一样，PHP开源界花开遍地。 作者一直倡导技术的深入学习就像职业篮球训练，80%的时间都是基本功的训练，球场上实际战术的练习只是基本功的应用。同样的，学习PHP语言本身的特性，应当是每个PHP领域工程师所掌握、理解的，至于系统的架构设计也是基于对Linux、Mysql、Nginx等原理机制足够理解后，战术性的使用。 在PHP的Zend?Engine（下面简称ZE）中，有一个非常重要的数据结构——哈希表（HashTable）。哈希表在ZE中有非常广泛的应用，PHP的复杂数据结构中数组和类的存储和访问就是用哈希表来组织，PHP语言结构中的常量、变量、函数等符号表也是用它来组织。 什么是哈希表呢？哈希表在数据结构中也叫散列表。是根据键名经过hash函数计算后，映射到表中的一个位置，来直接访问记录，加快了访问速度。在理想情况下，哈希表的操作时间复杂度为O(1)。数据项可以在一个与哈希表长度无关的时间内，计算出一个值hash(key)，在固定时间内定位到一个桶(bucket，表示哈希表的一个位置)，主要时间消耗在于哈希函数计算和桶的定位。 在分析PHP中HashTable实现原理之前，先介绍一下相关的基本概念： 如下图例子，希望通过人名检索一个数据，键名通过哈希函数，得到指向bucket的指针，最后访问真实的bucket。 ? 键名(Key)：在哈希函数转换前，数据的标识。 桶(Bucket)：在哈希表中，真正保存数据的容器。 哈希函数(Hash?Function)：将Key通过哈希函数，得到一个指向bucket的指针。MD5，SHA-1是我们在业务中常用的哈希函数。 哈希冲突(Hash?Collision)：两个不同的Key，经过哈希函数，得到同一个bucket的指针。 哈希表的结构： [php]?view plaincopy Zend/zend_hash.h?? ?typedef?struct?_hashtable?{?? ????????uint?nTableSize;????????????????????//哈希表的长度，不是元素个数?? ????????uint?nTableMask;??????????????????//哈希表的掩码，设置为nTableSize-1?? ????????uint?nNumOfElements;??????????//哈希表实际元素个数?? ????????ulong?nNextFreeElement;??????//指向下一个空元素位置?? ????????Bucket?*pInternalPointer;???????//用于遍历哈希表的内部指针?? ????????Bucket?*pListHead;???????????????//哈希表队列的头部?? ????????Bucket?*pListTail;?????????????????//哈希表队列的尾部?? ????????Bucket?**arBuckets;???????????????//哈希表存储的元素数组?? ????????dtor_func_t?pDestructor;??????????//哈希表的元素析构函数指针?? ????????zend_bool?persistent;??????????????//是否是持久保存，用于pmalloc的参数，可以持久存储在内存中?? ????????unsigned?char?nApplyCount;?????//?zend_hash_apply的次数，用来限制嵌套遍历的层数，限制为3层?? ????????zend_bool?bApplyProtection;?????//是否开启