哈希表
通过数组下标索引到值
任意类型映射成一个整型 (下标)
简单举例
val % size
假如 val = 16、size = 9
16 % 9 = 7 (下标)
假如 val = 7、size = 9
7 % 9 = 7 (下标) 产生冲突了 - 优秀的哈希都会冲突
解决哈希冲突的 四 种 方法
- 开放定值法
- 拉链法
- 在哈希法 (在散列法)
- 建立公共溢出区
解决哈希冲突方法 - 开放定值法
可以使用开放定值法 (二次探测法) - 不好用会堆聚
下标7后面8是空着的所以7可以存放到此处
| 下标 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
|
|
|
|
|
|
|
16 |
7 |
解决哈希冲突方法 - 拉链法
顾名思义拉链法就是以下标为7的位置做成一个链表
| 下标 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
|
|
|
|
|
|
|
16 |
|
|
|
|
|
|
|
|
|
7 |
|
解决哈希冲突方法 - 在哈希法 (在散列法)
如果第一个哈希函数冲突了，那么就可以利用第二个哈希函数在去做映射，如果在冲突了那么就利用第三个哈希函数在做。。。(禁止套娃)🤐
解决哈希冲突方法 - 建立公共溢出区
将冲突的元素集中去管理
时间复杂度
平均复杂度 ： $O(1)$
字符串-哈希
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
|
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node {
char *str;
struct Node *next;
} Node;
typedef struct HashTable {
Node **data;
int size;
} HashTable;
Node *init_node(char *str, Node *head) {
Node *p =(Node *)malloc(sizeof(Node));
p->str = strdup(str);
p->next = head;
return p;
}
HashTable *init_hash(int n) {
HashTable *h = (HashTable *)malloc(sizeof(HashTable));
h->size = (n << 1);
h->data = (Node **)calloc(h->size, sizeof(Node *));
return h;
}
int BKDRHash(char *str) {
int seed = 31, hash = 0;
for(int i = 0; str[i]; i++) hash = hash * seed + str[i];
return hash & 0x7fffffff;
}
int insert(HashTable *h, char *str) {
if(h == NULL) return 0;
int hash = BKDRHash(str);
int ind = hash % h->size;
h->data[ind] = init_node(str, h->data[ind]);
return 1;
}
int search(HashTable *h, char *str) {
if(h == NULL) return 0;
int hash = BKDRHash(str);
int ind = hash % h->size;
Node *p = h->data[ind];
while(p && strcmp(p->str, str)) p = p->next;
return p != NULL;
}
void clear_node(Node *node) {
if(node == NULL) return ;
Node *p = node, *t;
while(p) {
t = p->next;
free(p->str);
free(p);
p = t;
}
return ;
}
void clear(HashTable *h) {
if(h == NULL) return ;
for(int i = 0; i < h->size; i++) {
clear_node(h->data[i]);
}
free(h);
return ;
}
int main() {
#define MAX_N 100
int op;
char str[MAX_N + 5] = {0};
HashTable *h = init_hash(MAX_N);
while(~scanf("%d%s", &op, str)) {
switch(op) {
case 0 : {
printf("insert %s to HashTable\n", str);
insert(h, str);
} break;
case 1 : {
printf("search %s from HashTable result = %d\n", str, search(h, str));
}break;
}
}
#undef MAX_N
clear(h);
return 0;
}
|
