哈希表--HASH TABLE

File monitor一程序中用到一种数据结构叫做\"哈希表\"（hash table），我以前从来没有听说过这种数据结构，而且我也在做相似的东西，所以有必要了解。哪位仁兄能帮帮我啊 ?

你找数据结构书，在讲查找的那一部分里面，算法很简单的。

其重点在于哈希函数的选取和冲突的处理，我说的也不一定对，请高手指正。

在Driver里，用hash的主要目的是节省存储空间。因为hash算法可以把比较多的数据映射到比较少的数据上。

在Driver里，用hash的主要目的是节省存储空间。因为hash算法可以把比较多的数据映射到比较少的数据上。

不会吧？使用哈希表的目的是为了提高查找速度啊，我搞不懂他怎么节省存储空间的，数据结构书上说他是一个查找算法啊，又不是压缩算法，给我们讲一下好吗？

[quote]不会吧？使用哈希表的目的是为了提高查找速度啊，我搞不懂他怎么节省存储空间的，数据结构书上说他是一个查找算法啊，又不是压缩算法，给我们讲一下好吗？

1，我也是新手，说的很可能不对
2，节省内存是我自己的看法，和书上不一样。确实在很多情况下，hash可以节省内存，因为它可以把一个长数据映射为唯一的短数据。举例来说：
如果我们要在driver里缓存一些文件的路径，那么存字符串就比较费空间，如果存成hash，那么每一个hash entry对应的是唯一的路径。

当然了，老兄一提醒我想起来了，hash确实可以提高查找速度，也许这是它的主要用途？ :D

在数据结构书里讲哈希算法的时候，首先就讲了一大堆的查找问题，记得其中有一句话说，最快查找当然是在静态表中，通过偏移直接定位，而一般我们的一大堆数据，往往不是存在静态表中，这样的话我们就要构筑这么一张静态表，将数据添入的时候，首先就要计算添入的位置，这个值就通过哈西函数得到，哈希函数是自己定义的，得到后，将数据放了进去，当我们要找某个东西的时候，也是通过哈西函数定位到这个位置，再将他们取出来，假设有一个结构
struct tagSTUDENT {
  char name[24];
  char code[40];
  ....
} STUDENT, * PSTUDENT;

假设计算哈希值的时候，用的是name,那么我找到了以后，要想得到其他的属性，怎么得到？我想我的做法是在静态表的那个地方放的是这个结构的内容，或者是指向这么一个结构的一个指针，不管怎么样，总是要有空间来存储这些信息，这样，不但不能节省空间，反而要多出来开销一张表的消耗。

既然你退，那我就进,：）

老兄，我说的节省内存，是指hash完以后，原来的数据就不要了，只要hash表。这种技术在一些情况下非常有用，有效，有趣 :D

lov1999
   老兄，hash表不是数据压缩算法，而是为了高速查找数据之用，你想一想，如果我用别的方法来查找字符串，免不了逐一比较字符。

   hash函数就是一个字符串到一个整数的全函数（当然，最好是设计的这个函数是一个双射的函数，这是用离散数学的语言来描述的），相当于我自己定义一个函数，输入一个字符串，返回我一个整数，这个整数是怎么得到的呢？其计算方法由你定，比方说，我可以把字符串中的字符加起来在取100的模，这样我就计算出了一个 0－99之间的整数。有了这个整数怎么办？那就查表，说白了，就是用数组。好了，我的上课了，两小时后我在留一帖

兄台，我不是说hash只能用于压缩，但它确实可以在一定情况下用于压缩信息，可以选择好的算法，使产生的hash entry是独一无二的，那么我们不用存贮好长的字符串就可以判断该字符串是否存在了。

lov1999
   老兄，hash表不是数据压缩算法，而是为了高速查找数据之用，你想一想，如果我用别的方法来查找字符串，免不了逐一比较字符。

   hash函数就是一个字符串到一个整数的全函数（当然，最好是设计的这个函数是一个双射的函数，这是用离散数学的语言来描述的），相当于我自己定义一个函数，输入一个字符串，返回我一个整数，这个整数是怎么得到的呢？其计算方法由你定，比方说，我可以把字符串中的字符加起来在取100的模，这样我就计算出了一个 0－99之间的整数。有了这个整数怎么办？那就查表，说白了，就是用数组。好了，我的上课了，两小时后我在留一帖

讲得也有道理，特定情况下特定分析了！

讲得也有道理，特定情况下特定分析了！

没错。主要是我经常把hash用于节省内存，所以我才比较重视这个特性，快速查找的特性我反倒忘记了 :D

[quote]讲得也有道理，特定情况下特定分析了！

没错。主要是我经常把hash用于节省内存，所以我才比较重视这个特性，快速查找的特性我反倒忘记了 :D [/quote]

你个水货，这也值得回一条？嘿嘿，借此机会，我也赚一分，快到初级会员了，要加把劲了。

[quote][quote]讲得也有道理，特定情况下特定分析了！ 你个水货，这也值得回一条？嘿嘿，借此机会，我也赚一分，快到初级会员了，要加把劲了。

老兄，不是吧，你以为我在赚分？小人之心度君子之腹 :D :D :D

HASH TABLE是不是就是散列啊？我手头上的这本数据结构上没有找到哈希表这个概念，不过上面的散列倒好象上面大家讨论的。

HASH TABLE是不是就是散列啊？我手头上的这本数据结构上没有找到哈希表这个概念，不过上面的散列倒好象上面大家讨论的。

是不是散列我不知道，不过除了哈希表这个名称以外，还有一个中文名字是杂凑