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

Question

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

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

Answer 1

感觉题主的问题是，没有理解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

Answer 2

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

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

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

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

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

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