• 从PHP的Hash(哈希)算法开始

    PHP的Hash Table(哈希表)
    服务器君一共花费 25.784 ms 进行了 4 次数据库查询,努力地为您提供了这个页面。
    广告很萌的

    哈希表在PHP中的重要性

    Hash Table是PHP的核心,这话一点都不过分。

    哈希表是一种查找效率极高的数据结构,很多语言都在内部实现了哈希表。PHP中的哈希表是一种极为重要的数据结构,不但用于表示Array数据类型,还在Zend虚拟机内部用于存储上下文环境信息(执行上下文的变量及函数均使用哈希表结构存储)。PHP的数组、关联数组、对象属性、函数表、符号表等等都是用HashTable来做为容器的。基本上大部分的语言特性也都是基于哈希表的,例如:变量的作 用域和变量的存储,类的实现以及Zend引擎内部的数据有很多都是保存在哈希表中的。

    PHP的HashTable采用的拉链法(将映射到同一位置的值用双向链表保存)来解决冲突,这个这里就不展开说了。我们从这里开始关注PHP的哈希算法的设计思想,实现以及如何用哈希表实现各种PHP的语言特性的。

    • 如果想了解拉链法,可以参看以下链接:拉链法,不过事先告诉你,这可是个神展开,得开一个大坑慢慢填……

    PHP的Hash采用的是目前最为普遍的DJBX33A (Daniel J. Bernstein, Times 33 with Addition),这个算法被广泛运用与多个软件项目,Apache、Perl和Berkeley DB等。对于字符串而言这是目前所知道的最好的哈希算法,原因在于该算法的速度非常快,而且分类非常好(冲突小,分布均匀)。具体可以参考此文:DJBX33A APR哈希默认算法

    哈希表的一些基本概念

    哈希表在实践中使用的非常广泛,例如编译器通常会维护的一个符号表来保存标记,很多高级语言中也显式的支持哈希表。 哈希表通常提供查找(Search),插入(Insert),删除(Delete)等操作,这些操作在最坏的情况下和链表的性能一样为O(n)。 不过通常并不会这么坏,合理设计的哈希算法能有效的避免这类情况,通常哈希表的这些操作时间复杂度为O(1)。 这也是它被钟爱的原因。

    正是因为哈希表在使用上的便利性及效率上的表现,目前大部分动态语言的实现中都使用了哈希表。

    • 下面列举一下HashTable实现中出现的基本概念。 哈希表是一种通过哈希函数,将特定的键映射到特定值的一种数据结构,它维护键和值之间一一对应关系。
    • 键(key):用于操作数据的标示,例如PHP数组中的索引,或者字符串键等等。
    • 槽/桶(slot/bucket):哈希表中用于保存数据的一个单元,也就是数据真正存放的容器。
    • 哈希函数(hash function):将key映射(map)到数据应该存放的slot所在位置的函数。
    • 哈希冲突(hash collision):哈希函数将两个不同的key映射到同一个索引的情况。
    • 可以试着这么去理解哈希表。哈希表可以理解为数组的扩展或者关联数组,数组使用数字下标来寻址,如果关键字(key)的范围较小且是数字的话,我们可以直接使用数组来完成哈希表,而如果关键字范围太大,如果直接使用数组我们需要为所有可能的key申请空间。很多情况下这是不现实的。即使空间足够,空间利用率也会很低,这并不理想。

    同时键也可能并不是数字,在PHP中尤为如此,所以人们使用一种映射函数(哈希函数)来将key映射到特定的域中:

    h(key) -> index
    

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

更多 推荐条目

Welcome to NowaMagic Academy!

现代魔法 推荐于 2013-02-27 10:23   

本章最新发布
随机专题
  1. [移动开发] 简单了解Android Fragment 3 个条目
  2. [移动开发] 从代码角度去认识 Thread 9 个条目
  3. [移动开发] Activity 初步知识 2 个条目
  4. [移动开发] Android开发基础知识 4 个条目
  5. [数据结构] 图的定义 1 个条目
  6. [软件工程与项目管理] 了解一点WebKit 9 个条目
  7. [移动开发] 从代码角度去认识HttpClient 2 个条目
  8. [移动开发] 从代码角度去认识 Activity 4 个条目
  9. [运维管理] 防火墙原理与应用 5 个条目
  10. [移动开发] Content Provider内容提供者 3 个条目
  11. [移动开发] Android加载器Loaders 5 个条目
  12. [Python程序设计] Tornado 服务器环境配置 3 个条目
窗口 -- [协会]