LaneBlog

蝼蚁虽小,也有梦想

PHP Socket服务 | PHP微信开发框架 | 开源博客

初探哈希表HashTable

Clicks: 3211 Date: 2014-10-10 19:17:04 Power By 李轩Lane

哈希 hash

    

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

    对于高级语言内核来讲,哈希表hashTable绝对是数据结构中的关键,很多高级语言是显示的支持哈希表hashTable的,哈希表hashTable的实践应用也非常广泛,编译器会维护一个符号表来保存标记,提供增删改查等操作。

    设计合理的哈希表hashTable的时间复杂度是O(1),而最最糟糕的哈希表hashTable时间复杂度为O(n),通常,它总是O(1)。而O(n)是因为,哈希表hashTable变成了一个链表。

    名词解释:

    1、键:操作数据的标识,例如PHP数组中的索引。

    2、槽:用于保存数据的坑。

    3、哈希映射函数:将键映射到数据应该存放的槽所在位置的函数。

    4、哈希冲突:哈希函数将两个不同的键映射到同一个索引的情况。

    哈希表hashTable可以理解为关联数组,数组使用键来寻址,如果键的范围较小且是数字的话, 我们可以直接使用数组来完成哈希表hashTable,而如果关键字范围太大,如果直接使用数组我们需要为所有可能的键申请空间。 很多情况下这是不现实的。即使空间足够,空间利用率也会很低,这并不理想。同时键也可能并不是数字, 在PHP中尤为如此,所以人们使用一种映射函数(哈希函数)来将键映射到特定的域中。

    通过合理设计的哈希函数,我们就能将键映射到合适的范围,因为我们的键空间可以很大(例如字符串键), 在映射到一个较小的空间中时可能会出现两个不同的键映射被到同一个index上的情况, 这就是我们所说的出现了冲突。 目前解决哈希表hashTable冲突的方法主要有两种:链接法和开放寻址法。目前PHP中哈希冲突解决方法就是链接法。

    冲突解决 - 连接法:

    链接法通过使用一个链表来保存槽值的方式来解决冲突,也就是当不同的键映射到一个槽中的时候使用链表来保存这些值。 所以使用链接法是在最坏的情况下,也就是所有的键都映射到同一个槽中了,这样哈希表hashTable就退化成了一个链表, 这样的话操作链表的时间复杂度则成了O(n),这样哈希表hashTable的性能优势就没有了, 所以选择一个合适的哈希函数是最为关键的。由于目前大部分的编程语言的哈希表hashTable实现都是开源的,大部分语言的哈希算法都是公开的算法, 虽然目前的哈希算法都能良好的将键进行比较均匀的分布,而这个假使的前提是键是随机的,正是由于算法的确定性, 这就导致了别有用心的黑客能利用已知算法的可确定性来构造一些特殊的键,让这些键都映射到 同一个槽位导致哈希表hashTable退化成单链表,导致程序的性能急剧下降,从而造成一些应用的吞吐能力急剧下降, 尤其是对于高并发的应用影响很大,通过大量类似的请求可以让服务器遭受DoS(服务拒绝攻击), 这个问题一直就存在着,只是最近才被各个语言重视起来。哈希冲突攻击利用的哈希表hashTable最根本的弱点是:开源算法和哈希实现的确定性以及可预测性, 这样攻击者才可以利用特殊构造的键来进行攻击。要解决这个问题的方法则是让攻击者无法轻易构造 能够进行攻击的键序列。PHP采用的是一种治标不治本的做法: 限制用户提交数据字段数量。这样可以避免大部分的攻击,不过应用程序通常会有很多的数据输入方式,比如,SOAP,REST等等, 比如很多应用都会接受用户传入的JSON字符串,在执行json_decode()的时候也可能会遭受攻击。 所以最根本的解决方法是让哈希表hashTable的碰撞键序列无法轻易的构造,目前PHP中还没有引入不增加额外的复杂性情况下的完美解决方案。

    冲突解决 - 开放寻址法:

    通常还有另外一种解决冲突的方法:开放寻址法。使用开放寻址法是槽本身直接存放数据, 在插入数据时如果键所映射到的索引已经有数据了,这说明发生了冲突,这是会寻找下一个槽, 如果该槽也被占用了则继续寻找下一个槽,直到寻找到没有被占用的槽,在查找时也使用同样的策略来进行。由于开放寻址法处理冲突的时候占用的是其他槽位的空间,这可能会导致后续的键在插入的时候更加容易出现 哈希冲突,所以采用开放寻址法的哈希表hashTable的装载因子不能太高,否则容易出现性能下降。



相关内容:用PHP的实现一个高效的数据库(文件存储,NOSQL)  使用哈希表来构建自己的数据库 

©2014 www.lanecn.com , All rights reserved. Power By Li Xuan.  京ICP备14005030号