쿠쿠 해싱

가장 기본적인 자료구조 문제 중 하나는 사전(dictionary) 문제입니다. 단어들의 집합 $D$가 주어졌을 때, 임의의 질의 문자열 $q$가 $D$에 들어 있는지를 빠르게 판별하려고 합니다. 해싱은 이 문제의 대표적인 해법입니다. 모든 문자열을 정수 범위 $\{0, 1, \dots, n-1\}$의 값으로 보내는 빠르고 결정적인 해시 함수 $h : \Sigma^* \to [0..n-1]$를 설계하고, 크기 $n$의 빈 해시 테이블 $T$를 준비한 뒤 각 단어 $w \in D$에 대해 $T[h(w)] = w$로 저장합니다. 질의 $q$가 들어오면 $h(q)$를 계산하여 $T[h(q)] = q$인지 확인하면 됩니다.

문제는 충돌(collision)입니다. 서로 다른 두 단어가 같은 칸으로 해싱될 수 있습니다(생일 역설을 떠올려 보세요. 24명인 학급에서 생일이 같은 두 사람이 있을 확률은 이미 50%가 넘습니다). 평균적으로 충돌 없이 저장할 수 있는 단어 수는 약 $\sqrt{n}$개에 불과해 공간 사용이 매우 비효율적입니다.

쿠쿠 해싱(cuckoo hashing)은 두 개의 해시 함수 $h_1$과 $h_2$를 사용하는 더 강력한 변형입니다. 따라서 각 단어는 두 개의 후보 칸을 가집니다. 질의 $q$에 대해서는 $h_1(q)$와 $h_2(q)$를 모두 계산하여 $T[h_1(q)] = q$ 또는 $T[h_2(q)] = q$이면 $q \in D$라고 답합니다.

이 이름은 테이블을 만드는 방식에서 유래했습니다. 빈 테이블에서 시작하여 단어를 하나씩 삽입합니다. 단어 $d$를 삽입할 때:

• $T[h_1(d)]$가 비어 있으면 $T[h_1(d)] = d$로 둡니다.
• 그렇지 않고 $T[h_2(d)]$가 비어 있으면 $T[h_2(d)] = d$로 둡니다.
• 두 칸이 모두 차 있으면, 뻐꾸기가 다른 새의 알을 둥지 밖으로 밀어내듯이 현재 $T[h_1(d)]$에 있던 단어 $r$를 쫓아내고 $T[h_1(d)] = d$로 둡니다. 그런 다음 쫓겨난 $r$를 자신의 다른 후보 칸으로 다시 넣습니다. 그 칸도 차 있으면 거기 있던 단어를 같은 방식으로 쫓아내 옮기고, 이 과정을 반복합니다.

이 재배치 과정은 영원히 끝나지 않을 수도 있습니다. 무한 반복에 빠지면 다른 해시 함수로 테이블을 다시 만들어야 합니다. 다행히 $D$에 들어 있는 단어가 $n/2$개 이하라면 이런 일은 높은 확률로 일어나지 않습니다.

각 단어가 해싱되는 두 칸이 주어질 때, 주어진 순서대로 모든 단어를 삽입하면서 무한 재배치 반복에 빠지지 않고 넣을 수 있는지 판별하세요.

(쿠쿠 해싱은 2001년 R. Pagh와 F. F. Rödler가 제안했습니다.)

첫 번째 줄에 테스트 케이스의 수 $t$ ($1 \le t \le 50$)가 주어집니다.

각 테스트 케이스의 첫 줄에는 두 정수 $m$과 $n$ ($1 \le m \le n \le 10000$)이 주어집니다. $m$은 사전에 들어 있는 단어의 수이고, $n$은 해시 테이블의 크기입니다. 이어지는 $m$개의 줄 중 $i$번째 줄에는 삽입 순서상 $i$번째 단어 $d_i$의 두 해시 값 $h_1(d_i)$와 $h_2(d_i)$ ($0 \le h_1(d_i), h_2(d_i) < n$)가 주어집니다. 두 값은 같을 수도 있습니다.

각 테스트 케이스마다 한 줄을 출력합니다. 주어진 순서대로 모든 단어를 삽입할 수 있으면 successful hashing을, 불가능하면 rehash necessary를 출력합니다.