HASH表原理

    今天由于天气不好，整天就闷在家里无所事事，偶然间想起前段时间与一个朋友讨论的问题，就是关于哈希函数以及哈希表使用上的，而他对哈希表的理解却是一塌糊涂，当时由于比较忙，也没有仔细与他具体讨论此问题，趁今天有空就想将关于哈希表的概念简单的写一下，其实我知道虽然很多朋友在开发的过程中经常使用哈希表，但是实际上对于哈希表原理理解的应该很少，希望在此能让各位朋友对哈希表有所了解。

    言归正传，哈希表又名散列表，其主要目的是用于解决数据的快速定位问题。考虑如下一个场景。
   
    一列键值对数据，存储在一个table中，如何通过数据的关键字快速查找相应值呢？不要告诉我一个个拿出来比较key啊，呵呵。

    大家都知道，在所有的线性数据结构中，数组的定位速度最快，因为它可通过数组下标直接定位到相应的数组空间，就不需要一个个查找。而哈希表就是利用数组这个能够快速定位数据的结构解决以上的问题的。

    具体如何做呢？大家是否有注意到前面说的话：“数组可以通过下标直接定位到相应的空间”，对就是这句，哈希表的做法其实很简单，就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里，而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位。

    不知道说到这里，一些不了解的朋友是否大概了解了哈希表的原理，其实就是通过空间换取时间的做法。到这里，可能有的朋友就会问，哈希函数对key进行转换，取余的值一定是唯一的吗？这个当然不能保证，主要是由于hashcode会对数组长度进行取余，因此其结果由于数组长度的限制必然会出现重复，所以就会有“冲突”这一问题，至于解决冲突的办法其实有很多种，比如重复散列的方式，大概就是定位的空间已经存在value且key不同的话就重新进行哈希加一并求模数组元素个数，既 (h(k)+i) mod S , i=1,2,3…… ，直到找到空间为止。还有其他的方式大家如果有兴趣的话可以自己找找资料看看。

    不知道写的这些是否足够清楚，如果还有不明白的欢迎各位朋友提出意见，谢谢！

评论

3 楼 calmness 2008-04-20  

是啊，数据结构都有的，可惜如今很多开发人员连数据结构都没看过

2 楼 kaipingk 2008-04-20  

数据结构应该学过吧

1 楼 422232121 2008-04-20  

呵呵。。。。