One of the most fundamental data structure problems is
the dictionary problem: given a set
of words you want to be able to
quickly determine if any given query string
is present in the dictionary
or not. Hashing is a
well-known solution for the problem. The idea is to create a
function
from all strings to the integer range
, i.e. you
describe a fast deterministic program which takes a string as
input and outputs an integer between
and
. Next you allocate an empty hash
table
of size
and for each word
in
, you set
. Thus, given a query
string
, you only need
to calculate
and
see if
equals
, to determine if
is in the dictionary.
Seems simple enough, but aren’t we forgetting something? Of
course, what if two words in
map to the same location in the
table? This phenomenon, called collision, happens fairly often
(remember the Birthday paradox: in a class of 24 pupils there
is more than
% chance
that two of them share birthday). On average you will only be
able to put roughly
-sized dictionaries into the table without getting
collisions, quite poor space usage!
A stronger variant is Cuckoo Hashing. The
idea is to use two hash functions and . Thus each string maps to two
positions in the table. A query string is now handled as follows: you
compute both and
, and if
, or
, you
conclude that is in
. The name “Cuckoo
Hashing” stems from the process of creating the table.
Initially you have an empty table. You iterate over the words
in , and insert them one by one. If
is free, you
set .
Otherwise if
is free, you set . If both are occupied
however, just like the cuckoo with other birds’ eggs, you evict
the word in
and set
. Next you
put back into the
table in its alternative place (and if that entry was already
occupied you evict that word and move it to its alternative
place, and so on). Of course, we may end up in an infinite loop
here, in which case we need to rebuild the table with other
choices of hash functions. The good news is that this will not
happen with great probability even if contains up to words!
Input
On the first line of input is a single positive integer
specifying the number of test cases to follow. Each test case
begins with two positive integers on a line
of itself, telling the
number of words in the dictionary and the size of the hash table in the
test case. Next follow
lines of which the :th
describes the :th word
in the dictionary
by two non-negative
integers and
less than
giving the two hash
function values of the word . The two values may be identical.
Output
For each test case there should be exactly one line of
output either containing the string “successful hashing” if it is possible to insert
all words in the given order into the table, or the string
“rehash necessary” if it is
impossible.
| Sample Input 1 |
Sample Output 1 |
2
3 3
0 1
1 2
2 0
5 6
2 3
3 1
1 2
5 1
2 5
|
successful hashing
rehash necessary
|
