首页 > PHP > PHP哈希表概念及实现

PHP哈希表概念及实现

来源:原创 作者:thomas 分类:PHP 阅读:600 日期:2014-05-23

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

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

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

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

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

目前解决hash冲突的方法主要有两种:链接法和开放寻址法。

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

目前PHP中HashTable的哈希冲突解决方法就是链接法。

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

十日谈技术博客

 

热门文章 更多>

微信扫一扫,关注技术十日谈