哈希表的查找实现
构建哈希表时，可以使用多种方法来构造哈希函数，而且在处理冲突时也有多种方法可供选
择，在实际应用中可根据具体情况选择不同的方法。接下来通过一个简单的案例来实现哈希表的创建查找。创建一个哈希表来存储一组数据{107,8,13,22,16,30,103, 76,220,94}，具体如例1所示。
例1
1 #define _CRT_SECURE_NO_WARNINGS
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 #define HASHSIZE 10 //哈希表长度
5
6 typedef struct
7 {
8 int* elem; //数组，动态分配
9 int count; //当前元素个数
10 }HashTable;
11
12 int m = 0; //哈希表长，全局变量
13
14
15 //哈希表初始化
16 void InitHashTable(HashTable* h)
17 {
18 int i;
19 m = HASHSIZE;
20 h->count = m;
21 h->elem = (int*)malloc(m*sizeof(int));
22 for (i = 0; i < m; i++)
23 h->elem[i] = NULL;
24 return;
25 }
26
27 //构造哈希函数
28 int Hash(int key)
29 {
30 return key%m; //除留余数法
31 }
32
33 //插入操作
34 void InsertHash(HashTable* h, int key)
35 {
36 int addr = Hash(key); //求哈希地址
37 while (h->elem[addr] != NULL)
38 addr = (addr + 1) % m; //线性探测法处理冲突
39 h->elem[addr] = key;
40 }
41
42 //查找
43 int SearchHash(HashTable h, int key, int *addr)
44 {
45 *addr = Hash(key); //求哈希地址
46 while (h.elem[*addr] != key)
47 {
48 *addr = (*addr + 1) % m; //开放定址的线性探测
49 if (h.elem[*addr] == NULL || *addr == Hash(key)) //如果循环回到原点
50 return 0; //说明关键字不存在
51 }
52 return 1;
53 }
54
55 int main()
56 {
57 HashTable ht;
58 InitHashTable(&ht);
59 int arr[10] = { 107, 8, 13, 22, 16, 30, 103, 76, 220, 94 };
60 for (int i = 0; i < 10; i++)
61 InsertHash(&ht, arr[i]);
62
63 int num; //要查找的数据
64 printf("请输入要查找的数据：\n");
65 scanf("%d", &num);
66
67 int addr = Hash(num);
68 int ret = SearchHash(ht, num, &addr);
69 if (ret)
70 printf("查找成功！\n");
71 else
72 printf("查找失败！\n");
73
74 system("pause");
75 return 0;
76 }运行结果如图1所示。
图1 例1运行结果
例1中，在构造哈希函数时，利用除留余数法计算哈希地址；在插入数据元素和查找
元素时，是利用开放定址法中的线性探测法来解决冲突。代码60~61行成功在哈希表中插入一组数据，代码68行调用SearchHash()函数来查找数据，从键盘输入103时，由图1可知查找成功！
当然在创建哈希表时也可以选择用其他的方法来构造哈希函数，处理哈希冲突。如果没有冲突，哈希查找的复杂度为O(1)，速度是非常快的，但在实际应用中冲突是不可避免的。当然即便是需要解决冲突，选对了方法则其查找效率还是要远远高于其他数据结构的查找效率。这只是一个小的哈希表，如果在某些大数据中，如人口统计，文献检索，它可以在数以亿计的数据中快速的查找定位要找的信息，应用优势非常大。
多学一招：哈希表的装填因子
哈希表的装填因子α，标志着哈希表装满的程度，其计算公式如下所示：
1 α= 填入表中的记录个数/哈希表长度；α越小表明哈希表中存储的记录数越少，发生冲突的可能性越小；哈希表的平均查找长度取决于装填因子，而不是取决于查找集合中的记录个数。
不管哈希表长是多大，总能选择一个合适的装填因子以便将平均查找长度限定在一个范围内，此时哈希表查找的时间复杂度就是O(1)，为此，通常将哈希表设置的比查找集合大，虽然浪费了空间，但查找效率却是大大提高了。
点击此处
隐藏目录
隐藏目录
