問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2503思路:
字符串哈希
這里使用的哈希函數是ELFHash
1 int ELFHash(char *str)
2 {
3 unsigned long t, hash = 0;
4 while(*str) {
5 hash = (hash<<4) + (*str++);
6 if((t = hash&0xF0000000L))
7 hash ^= t>>24;
8 hash &= ~t;
9 }
10 return (hash & 0x7FFFFFFF)%PRIME;
11 }
因為之前寫哈希表解決沖突都是用的鏈接法，這里想嘗試一下開放地址法，采用最簡單的線性探查，結果居然TLE
無奈還是改成鏈接法，然后就AC了
不過，時間卻有719MS之多，而網上幾乎相同的代碼只需要230MS左右，不知道是何原因
代碼:
TLE的開放地址法
1 void
2 insert(int hash_val, int index)
3 {
4 if(!hash[hash_val].used) {
5 hash[hash_val].used = 1;
6 hash[hash_val].index = index;
7 } else
8 insert((hash_val+1)%PRIME, index); /* linear probing */
9 }
10
11 int
12 search(char *f_word)
13 {
14 int hash_val = ELFHash(f_word);
15 int i = 0;
16 while(1) {
17 if(!hash[hash_val].used || i==PRIME)
18 break;
19 if(strcmp(f_word, flg[hash[hash_val].index])==0)
20 return hash[hash_val].index;
21 hash_val = (hash_val+1)%PRIME;
22 ++i;
23 }
24 return -1;
25 }
26
27 void
28 input_hash()
29 {
30 int hash_val, index = 0;
31 char tmp[MAX_LEN*2+1];
32 memset(hash, 0, sizeof(hash));
33 while(gets(tmp) && tmp[0]) {
34 sscanf(tmp, "%s %s", eng[index], flg[index]);
35 hash_val = ELFHash(flg[index]);
36 insert(hash_val, index);
37 ++index;
38 }
39 }
AC的鏈接法
1 void
2 insert(int hash_val, int index)
3 {
4 struct Node *node = (struct Node *)malloc(sizeof(struct Node));
5 if(node == NULL) {
6 fprintf(stderr, "malloc error in: insert\n");
7 exit(1);
8 }
9 node->index = index;
10 node->next = hash[hash_val];
11 hash[hash_val] = node;
12 }
13
14 int
15 search(char *f_word)
16 {
17 int hash_val = ELFHash(f_word);
18 struct Node *node = hash[hash_val];
19 while(node != NULL) {
20 if(strcmp(f_word, flg[node->index]) == 0)
21 return node->index;
22 node = node->next;
23 }
24 return -1;
25 }
26
27 void
28 input_hash()
29 {
30 int hash_val, index = 0;
31 char tmp[MAX_LEN*2+1];
32 memset(hash, 0, sizeof(hash));
33 while(gets(tmp) && tmp[0]) {
34 sscanf(tmp, "%s %s", eng[index], flg[index]);
35 hash_val = ELFHash(flg[index]);
36 insert(hash_val, index);
37 ++index;
38 }
39 }