如何使用php的hashtable

hash表（散列表）在我看来一直是个牛逼的设计，因为它时间复杂度为O(1)。简直是远离循环，减少耗时的神器。今天好好看了看hash表的实现原理，觉得其实是自己把大学期间的基础知识给忘得一干二净，不扯远了。

1、hash表的原理：

具体原理参见， http://zha-zi.iteye.com/blog/1124484   和  http://www.cnblogs.com/carbs/archive/2012/07/04/2576995.html  都写得很清楚。

一句话说就是：value值通过计算（hash算法），得到一个key（hash值），形成key->value。再将key换算为数组下标，然后每个元素形成一个链表结构（双向链表，方便数据增删）。

2、本文重点：php中的hashtable是如何被程序员使用的。

确实，通过网上资料，并没有找到php直接可以调用的hashtable类。而又有许许多多的文章在介绍php内核中已经实现了hashtable（具体实现，请看 http://blog.csdn.net/a600423444/article/details/8850617）。这让当时的我不太能理解。我当时是这么想的：既然都说php已经实现了hashtable类，但是为什么没有相关的函数支持该功能呢。继续查询资料发现，php提供的关联数组底层就是通过hashtable来实现的。于是我又不太理解了，我当时是这么想的：既然都说关联数组就具有hashtable的功能，那关联数组是如何去实现hashtable的数据结构的呢，关联数组的下标是key，并不是hashtable里面的0....6...啊。数据结构不一样啊，关联数组顶多算是一个不带链表的hashtable。后来我经过更多的思考才明白，为什么说关联数组底层实现了hashtable。其实是这样的。关联数组的下标是key，没错。但是真正内存中的数组下标都是整数，而且是连续的（指针除外），所以php的关联数组并不是真正意义上的数组，实质是在数组的基础上包了一层或者两三层。这包的一两层中，就含有hashtable结构。更直白的说，就是关联数组的下标key，实质是对应了真正数组的一个数字下标。明白了这一点，就可以理解，其实php的关联数组底层是实现了hashtable的数据结构。更详细的解释，在使用关联数组时，需要保证key不冲突（不产生碰撞）。在关联数组中，体现为key->value的数组。到了关联数组底层，就体现为不同的key对应一个数字，多个key对应到同一个数字（也就是一个真正数组元素的下标），这样，这多个key就按照hashtable结构设计，放到该数组元素后面的链表中，最终在底层实现了一个hashtable。

        说到这里也就说明白了本文想说明的问题。php中的hashtable。其实php的关联数组就实现了hashtable。只要保证产生的key不重复。之后的事儿（计算下标，插入到各个桶内）就不用php程序员操心了。