首页 > 代码库 > hash使用示例

hash使用示例

2024-07-03 19:16:29   226人阅读

题目见 http://125.221.232.253/JudgeOnline/problem.php?id=1073

http://125.221.232.253/JudgeOnline/problem.php?cid=1073&pid=4

 

有不少方法可以解决该题,这里使用hash来解决. hash函数很简单,见下. hash表的大小取大于n的第一个质数.

剩下的关键问题就是冲突如何处理? 采用链式方法对于OJ上的题目太麻烦了,建议同学们做一下.

我采用了一个变通的方式:

如果某个key通过hash函数映射到hash表的下标ind,每个ind最多可以放10个关键字, hash_table[ind][0]存放已经放置的关键字个数.hash_table[ind][1]至hash_table[ind][10]可以存放有冲突的key.

如果映射到同一个ind的key多余10个怎么办? 程序可能就不行了,解决方法是加大slot或者调整质数值等等.事实上,10是我凭感觉取的,经测试,更小的值也能AC

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
  
int hash_table[110000][11];
  
int hash(int key, int sz)
{
    return abs(key) % sz;
}
  
int main()
{
    int n, m;
    while(scanf("%d%d", &n, &m) != EOF)
    {
        int i, j;
        int buckets;
  
        //find first prime which is larger than n
        for(i = n; ;i++){
            for(j = 2; j * j <= i; j++)
                if(i % j == 0)
                    break;
            if(j * j > i)
                break;
        }
        buckets = i;
        memset(hash_table, 0, (buckets + 1) * sizeof(hash_table[0]));
  
  
        for(i = 0; i < n; i++){
            int t;
            scanf("%d", &t);
            int ind = hash(t, buckets); //hash  function
            hash_table[ind][++hash_table[ind][0]] = t;  //insert t into hash_table
        }
        for(i = 0; i < m; i++){
            int t;
            scanf("%d", &t);
            int ind = hash(t, buckets);
            for(j = 1; j <= hash_table[ind][0]; j++){ //search t in hash_table
                if(hash_table[ind][j] == t)
                    break;
            }
            if(j <= hash_table[ind][0])
                puts("yes");
            else
                puts("no");
        }
    }
    return 0;
}

　　

 

 

 


联系
我们