POJ 3631 - Cuckoo Hashing

http://poj.org/problem?id=3631

概要

Cuckoo Hashing というアルゴリズムでハッシュテーブルを作る。

このアルゴリズムは1つの値 \(q\) に対して2つのハッシュ関数 \(h_1, h_2\) を使ってハッシュ値を計算する。 このとき \(h_1(q) = h_2(q)\) ともなりうる。

値 \(d\) をハッシュテーブル \(T\) に挿入するときの手順は以下である。

  1. \(T[h_1(d)]\) が空のとき、\(T[h_1(d)] := d\) として挿入を終了する
  2. \(T[h_2(d)]\) が空のとき、\(T[h_2(d)] := d\) として挿入を終了する
  3. どちらも空でないとき、\(T[h_1(d)] = d'\) とすると \(T[h_1(d)] := d\) とした後 \(d'\) を再び挿入する

この手順はもちろん無限ループに陥ることがある。そのときは再ハッシュが必要になる。

サイズ \(n\) のハッシュテーブルに与えられた \(m\) 個の値を挿入したとき、再ハッシュが必要になるかどうか答える。

制約

解法

上記のアルゴリズムを愚直に実装しても間に合った。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 static const int MAXN = 10000;
 5 
 6 int h[MAXN][2];
 7 int tbl[MAXN];
 8 bool visited[MAXN];
 9 
10 bool insert(int x)
11 {
12   for (int i = 0; i < 2; i++) {
13     int k = h[x][i];
14     if (!visited[k]) {
15       visited[k] = true;
16       if (tbl[k] == -1 || insert(tbl[k])) {
17         tbl[k] = x;
18         return true;
19       }
20     }
21   }
22   return false;
23 }
24 
25 void solve(int N, int M)
26 {
27   for (int i = 0; i < M; i++) {
28     fill_n(visited, N, false);
29     if (!insert(i)) {
30       puts("rehash necessary");
31       return;
32     }
33   }
34   puts("successful hashing");
35 }
36 
37 int main()
38 {
39   int T;
40   scanf("%d", &T);
41   while (T-- > 0) {
42     int M, N;
43     scanf("%d %d", &M, &N);
44     for (int i = 0; i < M; i++) {
45       scanf("%d %d", &h[i][0], &h[i][1]);
46     }
47     fill_n(tbl, N, -1);
48     solve(N, M);
49   }
50   return 0;
51 }
poj/3631.cc