HNU 13064 Cuckoo for Hashing解题报告 North America - East Central 2013

题目大意：使用两个哈希表来解决哈希冲突的问题。假如现在有两个哈希表分别为：H1,H2 ，大小分别为：n1,n2；现有一数据X需要插入，其插入方法为：

1、计算index1 = X MOD N1，  若哈希表H1的index1位置没有保存数据，则直接将X保存到H1得index1；否则，若哈希表H1的index1位置已经保存有数据X1，则将原来已保存的数据X1进行缓存，然后将X插入H1的index1的位置。

2、将上一步缓存的X1插入到哈希表H2，首先计算index2=X1 MOD N2，若H2的index2没有保存数据，则直接将X1保存至index2,；否则，缓存原来在H2中index2的数据X2，然后将X1保存到H2的index2中。

3、将上一步得X2重新插入到哈希表H1中，依次类推。

样例输入输出

Sample Input

5 7 4 8 18 29 4 6 7 4 8 18 29 4 1000 999 2 1000 2000 0 0 0

Sample Output

Case 1: Table 1 3:8 4:4 Table 2 1:29 4:18 Case 2: Table 1 0:18 2:8 4:4 5:29 Case 3: Table 1 0:2000 Table 2 1:1000

解题思路：

1、创建两个新的空哈希表，对于每个需要插入的数据分别进行处理。

2、对于每一个需要插入的数据，根据两个哈希表以上的性质，进行插入。

代码如下：

<span style="font-size:18px;">#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int t1[1002],t2[1002];
int flag;
/*flag==0, the operation in the table1
  flag==1, the operation in the table2
  when the collision occur, it will
  */
void insert(int n1, int n2, int value)
{
    int index, hel, tmp;
    switch (flag)
    {
        case 0:            //in the table1
            hel = value%n1;
            if(t1[hel] != 0)
            {
                flag = 1;
                tmp = t1[hel];
                t1[hel] = value;
                insert(n1, n2, tmp);
            }
            else {
                t1[hel] = value;
            }
            break;
        case 1:            //in the table2;
            hel = value%n2;
            if(t2[hel] != 0)
            {
                flag=0;
                tmp = t2[hel];
                t2[hel] = value;
                insert(n1, n2, tmp);
            }
            else{
                t2[hel] = value;
            }
            break;
    }
}
int main()
{
    int n1,n2,m,count;
    int i,value,f;

    count = 0;
    while(scanf("%d%d%d",&n1,&n2,&m)==3)
    {
        if(!n1 && !n2 && !m)
            break;
        memset(t1,0,sizeof(t1));
        memset(t2,0,sizeof(t2));
        for(i=0; i<m; i++)
        {
            scanf("%d",&value);
            flag = 0;
            insert(n1, n2, value);

        }
        printf("Case %d:\n",++count);
        f=0;
        for(i=0; i<n1; i++)
        {
            if(t1[i] != 0)
            {
                if(0 == f)
                {
                    printf("Table 1\n");
                    f = 1;
                }
                printf("%d:%d\n",i,t1[i]);
            }
        }
        f=0;
        for(i=0; i<n2; i++)
            if(t2[i] != 0)
            {
                if(0 == f)
                {
                    printf("Table 2\n");
                    f=1;
                }
                printf("%d:%d\n",i,t2[i]);
            }
    }
    return 0;
}</span>