从散列到HashMap的简单实现

         在程序中，我们常常用数组和链表来保存一些数据。作为两种最基本也最常用的保存数据的结构，数组和链表也是各有千秋：数组可以通过下标提供十分高效的查找，而链表可以利用本身在内存中的离散分布特性进行灵活的增删操作。两者可以说是各有优劣，但是为什么不能将两者的优点结合起来呢？这样不就可以提供一种既方便插入又方便查找的数据结构吗？是的，从你开始在Google上输入关键字搜索的时候你就已经知道答案了，它就是HashMap。

         在介绍HashMap之间，首先要介绍一下散列技术。散列就是hash的中文名字，虽然我觉得叫做哈希更加的fashion。散列技术是为了解决符号表的增删查问题应运而生的。我们知道，符号表是一种抽象数据类型（ADT），它基于无序集合，支持增删查三种基本操作。在Hash技术之前，我们有两种方法实现符号表的基本功能：位向量和集合的链表，但它们都有一个共同的弊病：时间复杂度高。而散列技术可以将符号表的操作的平均时间保持在一个常数水平。这也是散列技术受到欢迎的重要原因。
         散列可以分为两种：开散列（外部散列）和闭散列（内部散列）。开散列，顾名思义，是一种open的散列方式，它支持容量的动态分配，也就是说，它存储数据的空间可以说是无穷的（前提是你的计算机可以提供无穷的空间），而站在对立面的闭散列则是将数据保存在一个密闭的空间内，是一个闭关锁国政策的骨灰级粉丝。我们可以将它们想象成一堆保存数据的水桶，这些桶按照一定的规律摆放，开散列可以在一个桶里存放多个集合中元素，但是这些元素都有共同的特性；而闭散列的宪法规定，一个桶里只能有一个集合元素，其他的要想进来：没门！
         这里主要介绍开散列。前面提到开散列的桶里的元素有共同的特性，这个特性就是由hash函数决定的。Hash函数会为每个想要进来的元素进行检查和分组，然后发给他们一个号码牌，对“桶”入座。这点有点像垃圾分类，可回收垃圾请投入绿色垃圾桶，不可回收垃圾请自觉投入旁边的黄色桶（爱护地球，从我做起！）。散列函数也是有多种多样的。下面取几种常见的进行介绍：
         取余法：这个最常用也最没有技术含量。直接对key值的hashcode（什么是hashcode请关注www.google.com或者我未来的blog，或者，you let me know！）进行取余运算，然后得到一个哈希值h(x)，作为保存的位置；这种方法简单易懂而且效果不错；
         随机数法：这个相信大家可以明白，h(x)=random(k)，这种方法也是很简单，但是效果一般不如第一种；
         叠加法：一般我们可以把要查找的值的hashcode各位数相加得到一个新的整数，一般的hashcode是8、9位，因此得到的新的整数一般不会超过81，当然这样不符合散列表的动态扩容的特性，因此我们可以采取另一种叠加的方式，例如hashcode为123456789，我们可以将其分为三组，然后相加：123+456+789=1368，对于这个散列函数，散列表最大的大小是2997。如果还是数字大于2997，可以再将其分组：29+97。当然，这里只是一种示例，相信聪明如你，一定会有办法解决和完善。

         聪明如你，肯定会发现我们得到的h(x)会出现重复，专业一点叫做冲突，这时就需要一个救世主出来拯救世界了。还好，电视上说了：如果冲突在所难免，重新散列在你身边。重新散列（rehash）就是散列冲突的终结者。常见的rehash一般有两种（参考《Data Abstraction and Problem Solving With JAVA-walls and mirrors》Frank M.Carrano & Janet J.Prichard）：
        1.开放寻址：即如果一个待插入的位置已经被其他的元素占据，则探测其他的空位置来放置新项。当然，这种方案必须找到其有效查找的方法。开放寻址一般有三种方案:
         ①线性探测：这是一种相对简单的检测方案，当a位置已经被占据了，则探测a+1、a+2位置，以此类推，直到找到可用位置。但是这种方案增加了删除的复杂度，而且还会出现主要聚集的现象（表中包含多组连续占用的位置），这会降低散列的总体效率；
         ②二次探测：这种方案是不从原始位置开始探测，而是有规律地检查a+1^2、a+2^2等等，以此类推。当然这种方法也会导致聚集的发生；
         ③双散列：这种方案可以极大的减少聚集。双散列比较麻烦，它定义了两个hash函数h1、h2，h1以查找的key为自变量，产生一个0到m-1的整数x，h2同样以key作为自变量，得到一个1到m-1之间且和x互为素数的整数y，然后将y作为增量，直到找到空位为止。
        2.重新构建散列表：这种方案是改变了表的结构。一般有以下两种方法：
         ①桶：这是将数组里存储的元素也定义为数组，但是这个元素级别的数组需要有一个合适的大小，若太小则不能很好的解决冲突，若太大又可能造成空间的浪费；
         ②分离链表：可以把数组当成元素进行保存，当然也就可以把链表放进去，而且链表具有灵活增删的优点。这样，表中的每一个项保存的都是一个链表的引用，而所要保存的元素都在链表中。

         下面介绍一个我自己实现的MyHashMap。
         好的，在这里我可以很负责的告诉你，下面的HashMap简单实现真的不是吹的，那真的不是一般的简单，它只是用来介绍HashMap的实现的思想的，谁当真谁就输了。其实，如果你理解了HashMap的禅理，那么相信你一定可以写一个更好的出来。但是，如果你想在被砖头拍一下再得到璞玉的话，那么我就抛一个砖出来吧！客官，你可接好喽！
         首先，MyHashMap的实现了put、get、keyset、values、remove、isempty、containskey、clear和size这几个功能。它使用了分离链表法。它首先创建了一个保存链表的数组，默认的初始容量是10，默认的装载因子是0.85（Sun提供的HashMap的默认装载因子是0.75，这里因为为了使内存的浪费程度降低，我将其提升至0.85）。另一方面，我把要保存的内容包装成了一个MyHashElem对象，它拥有Key和Value两个属性。
         HashMap的核心当然是Hash函数。这里用了一个很简单的方法得到要保存的key值的散列位置。



         看到了吧，这种hash值的求解和sun提供的比起来，看上去的专业水平确实不是一两个层次的（不过取余是最常用的hash函数）。但是，前面说过，这个MyHashMap是用来了解HashMap的实现原理与机制的。因此大家就不要追究了，嘿嘿。
         其实，与其说自己的方法很简单，不如说我的方法很fashion。这里可以从我的rehash方法看出来：



         我知道，又有人会惊呼：Daddy Trap！（翻译为：坑爹啊！！）这个也太浪费内存了吧。是的，我当初也考虑到了，但是想想我做这件事的初衷只是为了了解HashMap的机制，而且这个可以节省rehash的时间，不是吗？而且，这里是很有优化的空间的，这里的思想是减少数组复制的时间，我们可以利用数学方法或其它操作使得其旧数组元素在新的数组的下标呈现出一定的规律性。我的简单实现是以大量内存的浪费为惨痛代价的。有细心的哥们姐们会觉察到：抛开内存浪费不说，这样固然节省了rehash的时间，但是查找呢？假如我插入的是345，当容量还够的时候，345%10=5，所以插在第六个位置，但是在一次扩充后，再查找345，位置就变成了345%100=45，也就是第46个位置，怎么会查到呢？别急，先看我查找的方法：



         这样就可以保证能够遍历到我们要找的元素了。这里先得到一个链表，即先查找46号位置上的链表是否包含有我们要找的元素，如果没有再继续往回找6号。这样从平均时间水平上讲，可以在一定程度上降低查找的时间复杂度，当然还有优化的空间，读者不妨一试。
         相信解决了hash和rehash之后，其余的功能对熟悉编程的人来说，肯定是手到擒来了。所以也没必要去展示和讲解其它的代码了，毕竟都是散列以外的知识了。不过有一点需要注意，就是HashMap的特性：key值不能重复！因此在put的时候，需要特别注意key值的检测。
         MyHashMap的实现其实是毫无技术含量可言，至少我是这么认为的，但是如果可以在一定程度上帮助你理解HashMap的实现，也算是功德一桩了。最后还是那句话：能力有限，欢迎拍砖！

评论

5 楼 青春的、脚步 2012-12-31  

楼主书法练过

4 楼 guokwei 2012-09-29  

这书法，眼前一亮啊

3 楼 sghcel 2011-10-30  

字体太非主流了

2 楼 pywepe 2011-10-30  

你的eclipse的字体 真个性  行业少有的个性

1 楼 javafound 2011-10-29  

引用

如果冲突在所难免，重新散列在你身边