PHP内核中哈希表是如何实现的？

本文共计2737个文字，预计阅读时间需要11分钟。

在PHP内核中，一个至关重要的数据结构是HashTable。我们常用的数组在内核中实际上就是通过HashTable实现的。那么，PHP的HashTable是如何实现的呢？最近在研究HashTable的数据结构，但看到的都是算法书籍。

在PHP内核中，其中一个很重要的数据结构就是HashTable。我们常用的数组，在内核中就是用HashTable来实现。那么，PHP的HashTable是怎么实现的呢？最近在看HashTable的数据结构，但是算法书籍里面没有具体的实现算法，刚好最近也在阅读PHP的源码，于是参考PHP的HashTable的实现，自己实现了一个简易版的HashTable，总结了一些心得，下面给大家分享一下。

笔者github上有一个简易版的HashTable的实现：HashTable实现

另外，我在github有对PHP源码更详细的注解。感兴趣的可以围观一下，给个star。PHP5.4源码注解。可以通过commit记录查看已添加的注解。

HashTable的介绍

哈希表是实现字典操作的一种有效数据结构。

定义

简单地说，HashTable(哈希表)就是一种键值对的数据结构。支持插入，查找，删除等操作。在一些合理的假设下，在哈希表中的所有操作的时间复杂度是O(1)(对相关证明感兴趣的可以自行查阅)。

实现哈希表的关键

在哈希表中，不是使用关键字做下标，而是通过哈希函数计算出key的哈希值作为下标，然后查找/删除时再计算出key的哈希值，从而快速定位元素保存的位置。

在一个哈希表中，不同的关键字可能会计算得到相同的哈希值，这叫做“哈希冲突”，就是处理两个或多个键的哈希值相同的情况。解决哈希冲突的方法有很多，开放寻址法，拉链法等等。