黑马程序员技术交流社区

标题: 哈希表的查找 [打印本页]

作者: 倪鹏博 时间: 2012-9-8 22:26
标题: 哈希表的查找
在包含冲突的哈希表之中，用链地址法解决冲突！
例如有：关键字集合序列｛100，300，500，700，800，900，101 , 801｝
可以构造哈希函数为：Hash(key)=key/100
在内存中的格式如下：
   0       1    2       3       4       5    6       7       8       9

         100          300             500          700    800 900

         101                                                             801

问题：其遍历过程是怎么样的呢？
如果查找的时候，查找的过程是怎么样的呢？比如分别查找801,802！

作者: 广驰 时间: 2012-9-9 23:10
本帖最后由应广驰于 2012-9-10 00:20 编辑

使用链表地址法，在哈希表每个单元中设置链表。某个数据项的关键字还是像通常一样映射到哈希表的单元，单元中记录的是头指针，你要查找哪一个元素，就用这个元素去运行哈希值的获得方法，然后去这个地址块链表看看是否有这个值，比如801是先获得哈希值，然后去这个地址找，找到第一个equlas判断一下，不同，在往这个地址块的下面找如果有继续equlas比较，找到就返回true，所以hash表是查找最快的存储方式，所以内存的地址分配也都是用这种方法

说实话对于java的数据结构为哈希表类，并不是很了解，我以前学的的C语言版的数据结构，不过应该都是大同小异吧，在C语言数据结构中没有给出具体实现，但是类似你这样就存放一列数据，通常直接定义一个散列表直接就是存放了这些元素哈希值或者说这些值的链表，遍历就如同List遍历一样，从哈希表头地址开始挨个判断是否有下一个，有就按照该单元链表一个个输出，知道没有下一个。

如果对这些有兴趣，建议还是买本数据结构看看

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2