Cuckoo for Hashing_双哈希表
<center>
提交: 24 解决: 12
[提交][状态][讨论版] </center>
问题 B: Cuckoo for Hashing
时间限制: 1 Sec 内存限制: 64 MB提交: 24 解决: 12
[提交][状态][讨论版] </center>
题目描述
An integer hash table is a data structure that supports insert, delete and lookup of integer values in constant time. Traditional hash structures consist of an array (the hash table) of some size n, and a hash function f(x) which is typically f(x) = x mod n. To insert a value x into the table, you compute its 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 with your faculty advisor on the way home from the contest.
Cuckoo hashing is a form of hashing that employs two hash tables T1 and T2, each with its own hash function f1(x) and f2(x). Insertion of a value x proceeds as follows: you first try to store x in T1 using f1(x). If that location is empty, then simply store x there and you’re done. Otherwise there is a collision which must be handled. Let y be the value currently in that location. You replace y with x in T1, and then try to store y in T2 using f2(y). Again, if this location is empty, you store y there and you’re done. Otherwise, replace the value there (call it z) with y, and now try to store z back in T1 using f1(z), and so on. This continues, bouncing back and forth between the two tables until either you find an empty location, or until a certain number of swaps have occurred, at which point you rehash both tables (again, something to discuss with your faculty advisor). For the purposes of this problem, this latter occurrence will never happen, i.e., the process should always continue until an empty location is found, 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 in each of the tables.
(For those interested, cuckoo hashing gets its name from the behavior of the cuckoo bird, which is known to fly to other bird’s nests and lay its own eggs in it alongside the eggs already there. When the larger cuckoo chick hatches, it pushes the other chicks out of the nest, thus getting all the food for itself. Gruesome but efficient.)
Cuckoo hashing is a form of hashing that employs two hash tables T1 and T2, each with its own hash function f1(x) and f2(x). Insertion of a value x proceeds as follows: you first try to store x in T1 using f1(x). If that location is empty, then simply store x there and you’re done. Otherwise there is a collision which must be handled. Let y be the value currently in that location. You replace y with x in T1, and then try to store y in T2 using f2(y). Again, if this location is empty, you store y there and you’re done. Otherwise, replace the value there (call it z) with y, and now try to store z back in T1 using f1(z), and so on. This continues, bouncing back and forth between the two tables until either you find an empty location, or until a certain number of swaps have occurred, at which point you rehash both tables (again, something to discuss with your faculty advisor). For the purposes of this problem, this latter occurrence will never happen, i.e., the process should always continue until an empty location is found, 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 in each of the tables.
(For those interested, cuckoo hashing gets its name from the behavior of the cuckoo bird, which is known to fly to other bird’s nests and lay its own eggs in it alongside the eggs already there. When the larger cuckoo chick hatches, it pushes the other chicks out of the nest, thus getting all the food for itself. Gruesome but efficient.)
输入
Input for each test case starts with 3 positive integers n1 n2 m, where n1 and n2 are the sizes of the tables T1 and T2 (with n1, n2 ≤ 1000 and n1 6= n2) and m is the number of inserts. Following this will be m integer values which are the values to be inserted into the tables. All of these values will be non-negative. Each table is initially empty, and table Ti uses the hash function fi(x) = x mod ni. A line containing 3 zeros will terminate input.
输出
For each test case, output the non-empty locations in T1 followed 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 v is the value stored there. Output values in each table from lowest index to highest. If either table is empty, output nothing for that table.
样例输入
5 7 4
8 18 29 4
6 7 4
8 18 29 4
1000 999 2
1000
2000
0 0 0
样例输出
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
解题思路：
这个题并不难，只要弄懂题意就比较容易了，但是英语是一大障碍啊！！！多学英语！！！ #include <iostream> #include <cstdio> #include <cstring> using namespace std; int main() { int n1,n2,m; int a[1000]; int b=1; int bq=1; int h1[1005]; int h2[1005]; int cc=0; while(scanf("%d %d %d",&n1,&n2,&m)!=EOF&&m!=0){ b=1; bq=1; memset(h1,0,sizeof(h1)); memset(h2,0,sizeof(h2)); for(int i=0;i<m;i++){ scanf("%d",&a[i]); } for(int i=0;i<m;i++){ int locat=a[i]%n1; int locat2=a[i]%n2; if(b==1 && h1[locat]!=0){ int t=h1[locat]; h1[locat]=a[i]; a[i]=t; i--; b=2; continue; } if(b==1 && h1[locat]==0){ h1[locat]=a[i]; if(bq==1){ bq=1; b=1; }else{ bq=2; b=2; } continue; } if(b==2 && h2[locat2]!=0){ int t=h2[locat2]; h2[locat2]=a[i]; a[i]=t; i--; b=1; continue; } if(b==2 && h2[locat2]==0){ h2[locat2]=a[i]; if(bq==2){ bq=2; b=2; }else{ bq=1; b=1; } continue; } } printf("Case %d:\n",cc+1); int cou=0; for(int i=0;i<n1;i++){ if(h1[i]!=0){ cou++; break; } } if(cou!=0){ printf("Table 1\n"); for(int i=0;i<n1;i++){ if(h1[i]!=0){ printf("%d:%d\n",i,h1[i]); } } } cou=0; for(int i=0;i<n2;i++){ if(h2[i]!=0){ cou++; break; } } if(cou!=0){ printf("Table 2\n"); for(int i=0;i<n2;i++){ if(h2[i]!=0){ printf("%d:%d\n",i,h2[i]); } } } cc++; } return 0; } /************************************************************** Problem: 2692 User: zz13 Language: C++ Result: 正确 Time:0 ms Memory:1700 kb ****************************************************************/
得物app公司福利 406人发布
