Cuckoo for Hashing(hash)hunnuoj

Problem B:Cuckoo for HashingAn integer hash table is a data structure that supports insert, delete and lookup of integer values inconstant time. Traditional hash structures consist of an array (the hash table) of some size n, and ahash function f(x) which is typically f(x) = x mod n. To insert a value x into the table, you computeits hash value f(x) which serves as an index into the hash table for the location to store x. For example,if x = 1234 and the hash table has size 101, then 1234 would be stored in location 22 = 1234 mod 101.Of course, it’s possible that some other value is already stored in location 22 (x = 22 for example),which leads to a collision. Collisions can be handled in a variety of ways which you can discuss withyour faculty advisor on the way home from the contest.Cuckoo hashing is a form of hashing that employs two hash tables T1and T2, each with its own hashfunction f1(x) and f2(x). Insertion of a value x proceeds as follows: you first try to store x in T1usingf1(x). If that location is empty, then simply store x there and you’re done. Otherwise there is a collisionwhich must be handled. Let y be the value currently in that location. You replace y with x in T1, andthen try to store y in T2 using f2(y). Again, if this location is empty, you store y there and you’redone. Otherwise, replace the value there (call it z) with y, and now try to store z back in T1usingf1(z), and so on. This continues, bouncing back and forth between the two tables until either you findan empty location, or until a certain number of swaps have occurred, at which point you rehash bothtables (again, something to discuss with your faculty advisor). For the purposes of this problem, thislatter occurrence will never happen, i.e., the process should always continue until an empty location isfound, which will be guaranteed to happen for each inserted value.Given the size of the two tables and a series of insertions, your job is to determine what is stored ineach of the tables.(For those interested, cuckoo hashing gets its name from the behavior of the cuckoo bird, which isknown to fly to other bird’s nests and lay its own eggs in it alongside the eggs already there. Whenthe larger cuckoo chick hatches, it pushes the other chicks out of the nest, thus getting all the food foritself. Gruesome but efficient.)InputInput for each test case starts with 3 positive integers n1n2m, where n1and n2are the sizes of thetables T1 and T2 (with n1,n2 ≤ 1000 and n1 6= n2) and m is the number of inserts. Following thiswill be m integer values which are the values to be inserted into the tables. All of these values will benon-negative. Each table is initially empty, and table Tiuses the hash function fi(x) = x mod ni. Aline containing 3 zeros will terminate input.OutputFor each test case, output the non-empty locations in T1followed by the non-empty locations in T2.Use one line for each such location and the form i:v, where i is the index location of the table, and vis the value stored there. Output values in each table from lowest index to highest. If either table isempty, output nothing for that table.2013 East Central Regional Contest4Sample Input5 7 48 18 29 46 7 48 18 29 41000 999 2100020000 0 0Sample OutputCase 1:Table 13:84:4Table 21:294:18Case 2:Table 10:182:84:45:29Case 3:Table 10:2000Table 21:1000
 
제목: 뜻은 해시가 왔다는 것이다. 구체적인 의미는 두 개의 해시표가 있고 그 다음에 이런 데이터가 있다는 것이다.
너로 하여금 이 데이터를 이 두 개의 해시 시계에 저장하게 한 다음에 중복할 수 없게 해라. 먼저 데이터를 시계 1에 저장하게 하는 것이 맞다
표1의 길이를 나머지로 하고 나머지라는 위치에 숫자가 없으면 저장하고 있으면 이 숫자를 저장하고
원래의 수를 다시 표 2에 저장하는 것도 이 방식에 따른다.그냥 왔다 갔다 차는...내 생각엔...
//사고방식: 두 개의 해시표, 하나는 순환해서 찾으면 된다...
 
>> 제목 링크<<

#include <stdio.h>

#include <string.h>

#include <map>

#include <iostream>



using namespace std ;

int ch[1100];

int sh[1100];

int main()

{

    int n1,n2,k ;

    int t = 1 ;

    while(scanf("%d%d%d",&n1,&n2,&k)!=EOF)

    {

        if(n1 == 0&&n2==0&&k==0) break;

        memset(ch,-1,sizeof(ch));

        memset(sh,-1,sizeof(sh)) ;



        int x ;

        for(int i = 1 ; i <= k ; i++)

        {

            scanf("%d",&x);

            while(1)

            {

                int s=x%n1;

                if(ch[s] == -1)

                {

                    ch[s]=x;

                    break;

                }

                else

                {

                    int temp=ch[s];

                    ch[s]=x;

                    int tt=temp%n2;

                    if(sh[tt]==-1)

                    {

                        sh[tt]=temp;

                        break;

                    }

                    else

                    {

                        x=sh[tt];

                        sh[tt]=temp;

                    }

                }

            }

        }

        printf("Case %d:
",t);

        t++;

        int flag = 0 ;

        for(int i = 0 ; i < n1 ; i++)

        {

            if(ch[i] != -1)

            {

                flag = 1 ;

                break ;

            }

        }

        if(flag)

        {

            printf("Table 1
");

            for(int i = 0 ; i < n1 ; i++)

            {

                if(ch[i] != -1)

                {

                    printf("%d:%d
",i,ch[i]);

                }

            }

        }

        flag = 0 ;

        for(int i = 0 ; i < n2 ; i++)

        {

            if(sh[i] != -1)

            {

                flag = 1 ;

                break ;

            }

        }

        if(flag)

        {

            printf("Table 2
");

            for(int i = 0 ; i < n2 ; i++)

            {

                if(sh[i] != -1)

                {

                    printf("%d:%d
",i,sh[i]) ;

                }

            }

        }

    }

    return 0 ;

}