简单介绍hash
rt 问题点数：32、回复次数：10Top
1 楼forulong（龙行天下）回复于 2001-10-23 22:37:37 得分 0
in my opinion,hashing is a technology which facilites the querying of data.Top
2 楼starfish（海星）回复于 2001-10-23 23:02:18 得分 28
简单来说，hash就是找到一种数据内容和数据存放地址之间的映射关系。比如，由若干字符串要存放到一个哈西表中，希望能够
在O(1)的时间内在表中定位某个特定的字符串，我们可以用数组来实现哈西表，找到某种函数sting -> integer，记为 p =
f(s)，其中p是一个整数，s是一个字符串，p就是字符串s在数组中的下标。这样如果需要在数组中定位s，只要直接根据函
数p=f(s)就可以计算s的位置。在哈西表中添加一个字符串也类似，根据字符串的值计算出其应该存放在数组中的位置，然后将字
符串放入。但是这种函数（成为哈西函数）很难找，找到一个一一对应的函数几乎不可能，所以经常采用非一一对应的哈西函数
。比如对于上面的例子，我们可以设计一个简单的哈西函数，我们设f(s)定义为s的各个字符的Ascii码的和除以n的余数，这里n
是我们的数组的长度，我们假设了哈西表中最多需要存储n个元素。但是这个哈西函数有个显而易见的缺点，比如对于字符串s1= "abc"和s2="acb"，显然计算出来的哈西函数值都是一样的，但是一个位置上只能存放一个元素，如果先将s1放入哈西表的位置p1，再将s2放入哈西表，这时候因为计算出p2=f(s2) = p1，所以s2应该放置的位置已经被s1占据了，所以就出现了麻烦。这就叫做“冲突”。解决这个冲突的一个简单的办法是，因为p1已经被s1占据，我们就看p1+1，如果该位置为空，则放入s2，否则继续看p1+2，……一直找到一个空位。假设我们将s2放在p1+1，但是这时候要加入s3，而f(s3)恰好等于p1+1，s3的位置又被s2占据了，我们可以继续看p1+2,p1+3……是否为空，直到找到一个空位放入s3，依此类推。在查找s2的时候，我们先根据f(s2)计算出s2应该在p1位置上，然后我们看p1位置上的元素，发现不是s2(该位置上是s1)，于是我们继续看p1+1，p1+2，……一直到找到s2，或者到表尾，或者发现一个空位就可以中止了，后两种情况表示s2不在表中。
显而易见，如果冲突发生的太多的话，哈西表的效率会下降。事实上我刚才举的例子中的哈西函数很不好，所以冲突发生的可能性很大。如果找一个比较好的哈西函数，哈西表的效率还是很高的。至于找哈西函数的方法，要根据具体的数据类型和应用场合来分析，也有一些原则，这里就不一一介绍了~~
打字累死我了~~不知道听懂了没有：）Top
3 楼starfish（海星）回复于 2001-10-23 23:03:57 得分 0
写错了，上文括号中应该是
“……但是这种函数（称为哈西函数）很难找……”
....................~~~~......Top
4 楼lovedog（不坐飞机）回复于 2001-10-24 13:42:23 得分 0
楼在上的不错啊！：）
http://www.csdn.net/expert/topic/337/337498.shtmTop
5 楼ritchiex（hxx）回复于 2001-10-24 16:09:59 得分 4
说白拉，就是用一个记录的某个数据项的值（称为关键字）通过一个函数来求出这个记录的地址。Top
6 楼hz1101（lake）回复于 2001-10-24 17:11:30 得分 0
up
Top
7 楼dongmen（东门吹气）回复于 2001-10-24 18:06:03 得分 0
听懂了，不过也明白我没本事用Top
8 楼sclzmbie（忘我）回复于 2001-10-25 15:58:07 得分 0
一种快速查找的算法，或者说是一种压缩映象。Top
9 楼chenggn（chenggn）回复于 2001-10-25 20:52:59 得分 0
不一定一一对应吧
是不是影射出一个范围?Top
10 楼xml2002（xml）回复于 2002-03-29 11:03:01 得分 0
very good.
解决了我想的“冲突”问题。
谢谢。Top
