Hash的理解与应用（理论篇）

 

（1）    为什么要使用hash这种数据结构？

众所周知，在编写的程序中，对数据的查找和处理是司空见惯的，特别是对一大堆数据而言。而作为最基本的数据结构，数组和链表而言，它们各具优势与缺陷。数组由于其存储的地址连续性及长度固定性，在查找操作上极具优势，只需要一次换算就能找到相应位置的数据，但是在插入、删除等操作上，却需要重新构造一个新的数组，这在空间及时间上是及其浪费的；而链表这种数据结构刚好相反，由于物理地址空间是随机分布的，各个节点之间是用索引相互串联起来的，所以其查找效率低的可怕，为了查找一个数据就不得不全部遍历一遍，但是对于插入、删除等操作而言，链表就极具优越性，它只需要改变操作位的索引即可，不需要像数组那样重新构造，这样效率也就极大的提高了。

由上可见，数组和链表在不同的操作上各具其优势，那么，我们所需要的就是如何做到这两种优势的融合，诞生出一种新的数据结构，既在查找上具有数组的速度，在插入和删除上也具有链表的效率。Hash就是为了实现这种效果而产生的，它天生就是为了提高查找和其他操作等效率而存在的，那么Hash到底是以一种什么样的结构存在呢，它又是如何做到效率的提高呢？

 

（2）    什么是Hash？

Hash这种算法的概念，可以理解为一种分组处理的方法，把大的数据分组成小的数据量，再在上面进行处理，以此来提高效率。它将任意输入的数据同过Hash()函数的运算得出该数据的hash值，也可理解为是该数据的标识，hash通过该数据的hash值对其进行处理。每个数据都通过这种方法进行映射处理，把不同的数据映射到一个用数组数据结构建立的表，这种表称为hash表或者散列，其地址空间是有限的。这种通过hash()函数的映射是一种压缩映射，也就是说hash表上的空间远远小于输入的数据的空间，不同的数据输入可能会映射成相同的hash值输出，因此，不可能从hash值来唯一确定输入的数据数值，这就是hash()函数所做的。

对于不同的数据，当其hash值一样时，就把它加入到该hash表中对应的位置，如果该位置尚且为空则大可直接放入，否则就在该hash表的位置上构建一个链表，把该数据用链表的方式加入到该位置上。

由此可见，hash是一种数组和链表的融合，在两者的优势上取的平衡，当然随着数据量的增加，这种平衡可能会被打破，这时我们就需要重新构造一个hash，这个过程叫做reHahs(),这个会在后面详细讲述。当你需要查找并处理一个数据是，你可以通过hash()函数映射到其所在的hash表上的位置，然后再在该位置上的链表结构上查找和处理该数据，查找的代价也就是在链表中，但由于这个链表比起原数据量少的多，几乎没有什么迭代的代价可言了，所以其操作速度也就大大提升。就这样达到了在数组与链表上取得平衡，提高了数据处理效率。

 

（3）    reHash()？

在上面已经说过，虽然在hash结构建立后取得了平衡，但是由于数据量及其类型往往是动态的，所以当输入数据量过多时，这种平衡就必然会被打破，这样也必然使该hash的效率降低，性能递减，因此，我们必须设置一个阈值来作为这个平衡的容差标准。当超过这个阈值时，就不得不重新定义及构造一个新的hash，当然这样的情况不会很平凡，所以对效率的影响不至于很大。那么这个阈值要根据什么来定义呢？

我们知道，hash对于效率的提高是通过分组来实现的，在hash表上的快速定位后，在只有少量数据的链表上进行操作。也就是说，由于hash表的地址是有限的，输入数据不断增加时，链表的长度也会随之增加，当大部分的链表上的数据超过过一定的量后，就会使得该hash结构的效率降低。

为此，我们rehash()所要做的就是当超过阈值后，加长hash表的地址空间，改变hash()函数，重新分配数据，以此来解决链表过于冗余的现状。

当然，阈值的设置因使用情况和所需处理的数据而定，主要目的就是为了保持平衡，保持效率。

 

评论

1 楼 南侠1999 2012-04-02  

少强牛逼啊