[已解决]二次线性探测建立的哈希表查找

bomu

对用二次线性探测建立的哈希表查找，是按二次线性探测的方法查找到空，还是依次查找到空

最佳答案

月排行榜 / 总排行榜

Mike_python小

2023-10-22 18:49:58

在使用二次线性探测法的哈希表中，查找过程并不是依次查找到空位置，而是按照以下方式进行：

1. 计算目标元素的哈希值 h，如果 h 存放的位置为空，则表示该元素不存在于哈希表中；
2. 如果 h 存放的位置被占用了，并且存放的元素不是目标元素，那么就按照二次探测序列计算下一个位置 h'，如果 h' 也被占用了并且存放的元素不是目标元素，就继续按照二次探测序列计算下一个位置，以此类推，直到找到目标元素或者遇到空位置。

因此，在哈希表中使用二次线性探测法进行查找时，会按照二次探测序列计算下一个位置，而不是依次查找到空位置。

下面是使用二次探测法实现的哈希表查找的示例代码：

2. const int N = 100000;
3. int h[N];
4. int sz = 0;
6. // 计算哈希值
7. int hash(int x) {
8.     return (x % N + N) % N;
9. }
11. // 插入元素
12. void insert(int x) {
13.     int k = hash(x);
14.     for (int i = 0; i < N; i++) {
15.         int j = (k + i * i) % N;
16.         if (h[j] == x) return; // 元素已存在
17.         if (!h[j]) {
18.             h[j] = x;
19.             sz++;
20.             return;
21.         }
22.     }
23. }
25. // 查找元素
26. bool find(int x) {
27.     int k = hash(x);
28.     for (int i = 0; i < N; i++) {
29.         int j = (k + i * i) % N;
30.         if (h[j] == x) return true; // 找到元素
31.         if (!h[j]) return false; // 遇到空位置，元素不存在
32.     }
33.     return false;
34. }

复制代码

希望能够帮助到你，如有疑问请继续追问。

球一个最佳答案谢谢啦！这对我非常重要！

跳转到最佳答案楼层