问答

算法:关于哈希表中开放寻址法的疑问

作者:admin 2021-05-14 我要评论

橙色代表已插入数据的位置,黄色代表未插入数据的位置 将 x 进行哈希计算,得知 x 需插入位置 7,但位置 7 已被占用,故通过线性探测查找到位置 2 未被占用,故...

在说正事之前,我要推荐一个福利:你还在原价购买阿里云、腾讯云、华为云服务器吗?那太亏啦!来这里,新购、升级、续费都打折,能够为您省60%的钱呢!2核4G企业级云服务器低至69元/年,点击进去看看吧>>>)

image
橙色代表已插入数据的位置,黄色代表未插入数据的位置
将 x 进行哈希计算,得知 x 需插入位置 7,但位置 7 已被占用,故通过线性探测查找到位置 2 未被占用,故插入位置 2

但在查找数据时,将 x 进行哈希计算仍会得到 7,但我之前的数据不是插在 7,而是插在 2,这样找到的不就不是我之前插入的数据了么?没想明白,请教大佬

###

感觉题主的问题是,没有理解hash算法找数据的详细步骤。
hash过程主要分成两部分:hash值计算方法 和 冲突解决方法

实际使用中,可以把hash存储分成三部分看,key=>value,还有存储地址

如上的问题,通过hash(key)=7,得出的这个7是算出来的第一个存储地址,它里面会保存key。

如果key1,和key2,通过hash算法得出的值是一样的,即hash(key1)=hash(key2)=7,这个就是hash冲突。
根据设置的冲突解决方法来重新找存储地址,比如找到了2,那么2里面保存的实际是(key2=>value2)。

在用key2获取数据时,先执行hash(key2)=7,但是取出7的数据发现是key1。
那么就会按预设的冲突解决算法继续找,找到2发现里面的key2,才会把数据返回,获取到里面的value2

###

你所说的问题是存在的,如果要获取x,它是没有办法根据7来获取成功的。

但问题也在这,我们应该没有这样的需要:

// 什么情况下要根据x的值来获取x呢?
x = hasMap.getByValue(x);

所以它有的方法应该类似于这样:

// 判断x是否存在于hasMap中
exists = hasMap.contains(x);

那么此时计算得到的是7。7中没有,则按线性探测的方法继续查找其它的。如果都不等于x,则返回false;如果有一个等于x,则返回true.

版权声明:本文转载自网络,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。本站转载出于传播更多优秀技术知识之目的,如有侵权请联系QQ/微信:153890879删除

相关文章
  • 请问下prometheus怎么进行自定义的按业

    请问下prometheus怎么进行自定义的按业

  • 节流函数为什么,点击无效,监听窗口大

    节流函数为什么,点击无效,监听窗口大

  • express访问静态资源失败

    express访问静态资源失败

  • IE 浏览器下 match 方法报错

    IE 浏览器下 match 方法报错

腾讯云代理商
海外云服务器