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

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. }

复制代码

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

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

跳转到最佳答案楼层

isdkz

二次线性探测是一种哈希表的探测方法，用于解决哈希冲突。在使用二次线性探测建立的哈希表中进行查找时，是按照二次线性探测的方法查找到空位置，而不是依次查找到空位置。

具体来说，当进行哈希表查找时，如果目标元素的哈希值所对应的位置已经被占用，即发生了哈希冲突，那么二次线性探测会按照一定的规则寻找下一个可用的位置。这个规则是通过二次探测函数来确定下一个位置，而不是简单地依次查找到空位置。

二次探测函数通常采用以下形式：(hash(key) + i^2) % table_size，其中hash(key)是关键字key的哈希值，i是探测的次数，table_size是哈希表的大小。每次探测时，i的值逐渐递增，直到找到一个空位置为止。

总结来说，二次线性探测建立的哈希表查找是按照二次线性探测的方法查找到空位置，而不是依次查找到空位置。

陶远航

二次线性探测哈希表查找是一种解决哈希冲突的方法。在这种方法中，如果哈希函数返回的位置已经被占用，那么就会查找下一个可用的位置。这个“下一个”位置是通过一个二次函数计算得到的，通常是形如(i^2)的形式，其中i是探测的次数。

具体来说，如果哈希函数返回的位置是h，那么第一次探测的位置是(h+1^2) mod N，第二次探测的位置是(h+2^2) mod N，以此类推，直到找到一个空的位置或者探测了N次（N是哈希表的大小）。

所以，对于二次线性探测哈希表查找，是按照二次线性探测的方法依次查找到空的位置。
请注意，本回答来自GPT-4
如果问题已经解决，请设置最佳答案

Mike_python小

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

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. }

复制代码

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

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