2008-04-19

HASH表原理

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

言归正传，哈希表又名散列表，其主要目的是用于解决数据的快速定位问题。考虑如下一个场景。

一列键值对数据，存储在一个table中，如何通过数据的关键字快速查找相应值呢？不要告诉我一个个拿出来比较key啊，呵呵。

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

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

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

不知道写的这些是否足够清楚，如果还有不明白的欢迎各位朋友提出意见，谢谢！
评论
shxiao 2008-04-23
这儿有一个简单的c实现http://uthash.sourceforge.net/
jiangshaolin 2008-04-22
用C把HASH实现出来,才算理解了
calmness 2008-04-21
引用

挺清晰的,大概是看了HashMap的源代码总结出来的吧!呵呵!


HashMap的源代码是看过，不过其原理倒不是因为看了这个源码才知道，以前读书的时候都有学过其原理的。
calmness 2008-04-21
大致修改了一下文章中有问题的地方，如果仍有问题请各位指正，我可不想成为误导别人的人。
form_rr 2008-04-21
挺清晰的,大概是看了HashMap的源代码总结出来的吧!呵呵!
calmness 2008-04-21
pf_miles 写道

一点也不虚心呢...

引用
哈希函数对key进行转换，返回的值一定是唯一的吗？这个当然不能保证

这话要怎么理解？
我语文不过关吧，无话可说，越说越累。


呵呵，我承认我的语句存在问题，容易导致误解，我也很感谢你的指正，但没有必要去争论什么，你也不需要觉得累。
pf_miles 2008-04-21
一点也不虚心呢...
引用
哈希函数对key进行转换，返回的值一定是唯一的吗？这个当然不能保证

这话要怎么理解？
我语文不过关吧，无话可说，越说越累。
huyuhong001 2008-04-21
fffff
huyuhong001 2008-04-21
数字为下标的数
calmness 2008-04-21
引用

不同对象有不同的hashcode,但不同的hashCode经过与长度的取余,就很可能产生相同的index,这个才是hash算法的真正冲突，冲突时不可避免的,hashCode超出了int的范围也是一种，不过一般不考虑。当几个对象产生了俄相同的index时候，解冲突就是把这个index的位置放置的是一个链表,再通过hashcode和key取得对于的数据


没错，主要的冲突就在于数组长度限制导致hash取余相等，这是无法避免的。
angeltping 2008-04-21
不同对象有不同的hashcode,但不同的hashCode经过与长度的取余,就很可能产生相同的index,这个才是hash算法的真正冲突，冲突时不可避免的,hashCode超出了int的范围也是一种，不过一般不考虑。当几个对象产生了俄相同的index时候，解冲突就是把这个index的位置放置的是一个链表,再通过hashcode和key取得对于的数据
calmness 2008-04-21
引用

纠正几个错误：

引用
不要告诉我一个个拿出来比较key啊，呵呵。

一个个拿出来比较也是一种hash算法，只不过很低效。

引用
哈希函数对key进行转换，返回的值一定是唯一的吗？这个当然不能保证

是唯一的，如果把hash函数设为y=f(x)，y是结果，x是key，那么这是一个多对一的关系，即多个x对应一个y，也就是说通过一个x能唯一确定一个y值，但由一个y值却不能倒推出x的值。你想想看，如果返回值不唯一，你第一次把x放进去了，第二次你再想找这个x了，但f(x)算出来跟第一次不一样了，还上哪去找？如果你用java，那么equals和hashCode方法的联系就能涉及到这些基本问题。

另外，存储值的数组一般不是一个简单数组，一般来说数组元素又是一个数组，因为有“碰撞”，所以会发生多个值放在一个“桶”内的情况。

真正研究hash算法能获得博士学位，但一般程序员没有必要自己写一个hash算法，用eclipse生成一个很高效了。

总觉得现在的程序员应该补基本功...



很感谢你的回复，在此我也想纠正一下你的误解。

第一，我并没有说一个个拿出来比较是错，只是这种方法不被推荐。

第二，hash出来得值的重复是不可避免的，而如果加上key的话，确实是唯一的，事实上java的算法就是使用你说的那种方法，将相同hash值的value放到同一个桶里，再通过key进行区分，这种方式只能说是解决冲突的一种方法，而非是一定的，而我上面举的重复散列也是其中一种，所以我在后面就说了，还有很多种解决冲突的方式。
pf_miles 2008-04-21
纠正几个错误：
引用
不要告诉我一个个拿出来比较key啊，呵呵。

一个个拿出来比较也是一种hash算法，只不过很低效。
引用
哈希函数对key进行转换，返回的值一定是唯一的吗？这个当然不能保证

是唯一的，如果把hash函数设为y=f(x)，y是结果，x是key，那么这是一个多对一的关系，即多个x对应一个y，也就是说通过一个x能唯一确定一个y值，但由一个y值却不能倒推出x的值。你想想看，如果返回值不唯一，你第一次把x放进去了，第二次你再想找这个x了，但f(x)算出来跟第一次不一样了，还上哪去找？如果你用java，那么equals和hashCode方法的联系就能涉及到这些基本问题。

另外，存储值的数组一般不是一个简单数组，一般来说数组元素又是一个数组，因为有“碰撞”，所以会发生多个值放在一个“桶”内的情况。

真正研究hash算法能获得博士学位，但一般程序员没有必要自己写一个hash算法，用eclipse生成一个很高效了。

总觉得现在的程序员应该补基本功...
calmness 2008-04-20
KKFC 写道

从ECMAScript人手如何?因为我想整个JS对象结构都是Hash?

很抱歉，我不是很明白你的意思。
KKFC 2008-04-20
从ECMAScript人手如何?因为我想整个JS对象结构都是Hash?
calmness 2008-04-20
是啊，数据结构都有的，可惜如今很多开发人员连数据结构都没看过
kaipingk@gmail.com 2008-04-20
数据结构应该学过吧
422232121 2008-04-20
呵呵。。。。
发表评论

您还没有登录，请登录后发表评论

calmness
搜索本博客
我的相册
F75ae93d-5e2f-343f-b0aa-f3ed98f0e14f-thumb
1
共 9 张
存档
最新评论