php源码学习日志hash表-创新互联

 php 的源码实现中,很多数据是用一张hash表维护的,比如对象的方法,数组等

成都创新互联从2013年成立,先为南昌等服务建站,南昌等地企业,进行企业商务咨询服务。为南昌企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。

   基本概念

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

键(key):用于操作数据的标示,例如PHP数组中的索引,或者字符串键等等。

槽(slot/bucket):哈希表中用于保存数据的一个单元,也就是数据真正存放的容器。

哈希函数(hash function):将key映射(map)到数据应该存放的slot所在位置的函数。

哈希冲突(hash collision):哈希函数将两个不同的key映射到同一个索引的情况。

 但是hash算法再好,在无线的数据下,总会出现不同key对应相同值的情况,应为hash后的值是等长的,而这个时候,就是hash冲突了,解决冲突目前有两个方法,链表发和寻址法

冲突解决 链接法

    链接法通过使用一个链表来保存slot值的方式来解决冲突,也就是当不同的key映射到一个槽中的时候使用链表来保存这些值。所以使用链接法是在最坏的情况下,也就是所有的key都映射到同一个槽中了,这样哈希表就退化成了一个链表,这样的话操作链表的时间复杂度则成了O(n),这样哈希表的性能优势就没有了,所以选择一个合适的哈希函数是最为关键的。

弱点

   由于目前大部分的编程语言的哈希表实现都是开源的,大部分语言的哈希算法都是公开的算法,虽然目前的哈希算法都能良好的将key进行比较均匀的分布,而这个假使的前提是key是随机的,正是由于算法的确定性,这就导致了别有用心的***能利用已知算法的可确定性来构造一些特殊的key,让这些key都映射到同一个槽位导致哈希表退化成单链表,导致程序的性能急剧下降,从而造成一些应用的吞吐能力急剧下降,尤其是对于高并发的应用影响很大,通过大量类似的请求可以让服务器遭受DoS(服务拒绝***),这个问题一直就存在着,只是最近才被各个语言重视起来。

哈希冲突***利用的哈希表最根本的弱点是:开源算法和哈希实现的确定性以及可预测性,这样***者才可以利用特殊构造的key来进行***。要解决这个问题的方法则是让***者无法轻易构造能够进行***的key序列。

开放寻址法

        通常还有另外一种解决冲突的方法:开放寻址法。使用开放寻址法是槽本身直接存放数据,在插入数据时如果key所映射到的索引已经有数据了,这说明发生了冲突,这是会寻找下一个槽,如果该槽也被占用了则继续寻找下一个槽,直到寻找到没有被占用的槽,在查找时也使用同样的策律来进行。

由于开放寻址法处理冲突的时候占用的是其他槽位的空间,这可能会导致后续的key在插入的时候更加容易出现哈希冲突,所以采用开放寻址法的哈希表的装载因子不能太高,否则容易出现性能下降。

装载因子是哈希表保存的元素数量和哈希表容量的比,通常采用链接法解决冲突的哈希表的装载 因子最好不要大于1,而采用开放寻址法的哈希表最好不要大于0.5。

另外有需要云服务器可以了解下创新互联cdcxhl.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


当前文章:php源码学习日志hash表-创新互联
本文地址:http://scyanting.com/article/hjjjh.html