又是坑人的一题。必须要在哈希表中查找 tSize+1 次还没找到才能停止，我觉得不太对啊，第 tSize+1 次查找，(x + tSize*tSize) % tSize 不是显而易见地是跟第一次查找是一毛一样的位置吗？？？为什么还要没事找事再找一遍？？？反正我不理解。。
#include <bits/stdc++.h> using namespace std; const int maxn = 1e4+1e2; int tSize, n, m; int hashTable[maxn]; int sum; bool isPrime(int x) { if (x == 0 || x == 1) return false; for (int i = 2; i*i <= x; ++i) { if (x % i == 0) { return false; } } return true; } int findMinimumPrime(int x) { if (x % 2 == 0) x++; while (!isPrime(x)) { x += 2; } return x; } int getHash(int x, bool isCount) { int h, probe = 0; do { h = (x + probe*probe) % tSize; if (isCount) sum++; //计算查询次数 } while (++probe <= tSize && hashTable[h] && hashTable[h] != x); // 退出查找的条件：1）探测了共tSize+1次还没找到空位 2）找到了空位 3）找到了自身的值 return probe > tSize ? -1 : h; // 如果找了tSize+1次说明查找失败，否则就是找到了 } void read() { scanf("%d%d%d", &tSize, &n, &m); tSize = findMinimumPrime(tSize); //找到大于等于tSize的最小素数 for (int i = 0; i < n; ++i) { int x, hx; scanf("%d", &x); if (~(hx = getHash(x, false))) { //如果返回值不等于-1，就说明有空位了 hashTable[hx] = x; } else { printf("%d cannot be inserted.\n", x); //否则就是无法插入 } } } void solve() { for (int i = 0; i < m; ++i) { int x; scanf("%d", &x); getHash(x, true); } printf("%.1f\n", 1.0*sum/m); } int main() { read(); solve(); return 0; }
