从PHP的Hash（哈希）算法开始

绝地灬酷狼 2022-08-06 16:27 201阅读 0赞

#### 转自：http://www.nowamagic.net/academy/detail/1200001 ####

#### 哈希表在PHP中的重要性 ####

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

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

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

*  如果想了解拉链法，可以参看以下链接： [拉链法][Link 2]，不过事先告诉你，这可是个神展开，得开一个大坑慢慢填……

PHP的Hash采用的是目前最为普遍的DJBX33A (Daniel J. Bernstein, Times 33 with Addition)，这个算法被广泛运用与多个软件项目，Apache、Perl和Berkeley DB等。对于字符串而言这是目前所知道的最好的哈希算法，原因在于该算法的速度非常快，而且分类非常好（冲突小，分布均匀）。具体可以参考此文：[DJBX33A APR哈希默认算法][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中尤为如此，所以人们使用一种[映射函数][Link 3]（哈希函数）来将key映射到特定的域中：

<table style="border-spacing:0px; margin:0px!important; padding:0px!important; border:0px!important; outline:0px!important; font-size:12px!important; vertical-align:baseline!important; border-collapse:collapse!important; width:auto!important; float:none!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; line-height:1.1em!important; min-height:inherit!important; background:none!important"> 
 <tbody style="margin:0px!important; padding:0px!important; border:0px!important; outline:0px!important; vertical-align:baseline!important; float:none!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; min-height:inherit!important; background:none!important"> 
  <tr style="margin:0px!important; padding:0px!important; border:0px!important; outline:0px!important; vertical-align:baseline!important; float:none!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; min-height:inherit!important; background:none!important"> 
   <td style="margin:0px!important; padding:0px!important; border:0px!important; outline:0px!important; vertical-align:top!important; float:none!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:3em!important; line-height:1.1em!important; font-family:'Courier New',Courier,monospace!important; min-height:inherit!important; color:rgb(175,175,175)!important; background:none!important"> <code style="margin:0px!important; padding:0px 0.3em 0px 0px!important; border:0px!important; outline:0px!important; vertical-align:baseline!important; text-align:right!important; float:none!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:2.7em!important; line-height:1.1em!important; font-family:'Courier New',Courier,monospace!important; min-height:inherit!important; display:block!important; background:none!important">1</code></td> 
   <td style="margin:0px!important; padding:0px 0px 0px 0.5em!important; border-width:0px 0px 0px 3px!important; border-left-style:solid!important; border-left-color:rgb(108,226,108)!important; outline:0px!important; vertical-align:top!important; float:none!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; font-family:'Courier New',Courier,monospace!important; min-height:inherit!important; background:none!important"> <code style="margin:0px!important; padding:0px!important; border:0px!important; outline:0px!important; vertical-align:baseline!important; float:none!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; font-family:'Courier New',Courier,monospace!important; min-height:inherit!important; background:none!important">h(key) -&gt; index</code></td> 
  </tr> 
 </tbody> 
</table>

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

[Link 1]: http://www.nowamagic.net/academy/tag/%E5%93%88%E5%B8%8C%E8%A1%A8
[Link 2]: http://www.nowamagic.net/academy/detail/3008060
[DJBX33A APR]: http://www.nowamagic.net/academy/detail/3008095
[Link 3]: http://www.nowamagic.net/academy/tag/%E6%98%A0%E5%B0%84%E5%87%BD%E6%95%B0
[Link 4]: http://www.nowamagic.net/academy/detail/3008010