A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 倪鹏博 中级黑马   /  2012-9-8 22:26  /  2341 人查看  /  2 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

在包含冲突的哈希表之中,用链地址法解决冲突!
例如有:关键字集合序列{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!

2 个回复

正序浏览
本帖最后由 应广驰 于 2012-9-10 00:20 编辑

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

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

如果对这些有兴趣,建议还是买本数据结构看看
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马