数据结构与算法——哈希表
2021-03-13 13:29
标签：const 计算 其它 数据 system 哈希表 方便 main lse 首先有这么一种情况，有24个人编号分别为1~24，我们需要将 24 人均分成 6 个组！ 编号除 6 余数为 0 的为第零组： 6、12、18、24 编号除 6 余数为 1 的为第一组： 1、7、13、19 编号除 6 余数为 2 的为第二组： 2、8、14、20 编号除 6 余数为 3 的为第三组： 3、9、15、21 编号除 6 余数为 4 的为第四组： 4、10、16、22 编号除 6 余数为 5 的为第五组： 5、11、17、23 通过这种编号方式划分队列，寻找某一个数会非常方便，比如寻找19，19 % 6 = 1，19再第一组。这种编号的方式就是高效的散列，我们俗称 “哈希”！ 以上过程是通过把关键码值 key（编号）映射到表中一个位置(数组的下标)来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。 哈希表 - 散列表，它是基于快速存取的角度设计的，也是一种典型的 “空间换时间” 的做法 键(key)： 组员的编号 如， 1 、 5 、 19 。 。 。 值(value)： 组员的其它信息（包含 性别、年龄和战斗力等） 索引: 数组的下标(0,1,2,3,4) ，用以快速定位和检索数据 哈希桶: 保存索引的数组(链表或数组)，数组成员为每一个索引值相同的多个元素 哈希函数: 将组员编号映射到索引上，采用求余法 ，如： 组员编号 19 hash_table.h hash_table.c 数据结构与算法——哈希表 标签：const 计算 其它 数据 system 哈希表 方便 main lse 原文地址：https://www.cnblogs.com/CooCoChoco/p/14058200.html1. 什么是哈希表
2. 哈希表的算法实现
2.1 哈希表数据结构的定义
1 #define DEFAULT_SIZE 16
2
3 typedef struct _ListNode
4 {
5 struct _ListNode *next;
6 int key;
7 void *data;
8 }ListNode;
9
10 typedef ListNode *List;
11 typedef ListNode *Element;
12
13 typedef struct _HashTable
14 {
15 int TableSize;
16 List *Thelists;
17 }HashTable;
2.2 哈希函数
1 /*根据 key 计算索引，定位 Hash 桶的位置*/
2 int Hash(int key, int TableSize)
3 {
4 return (key%TableSize);
5 }
2.3 哈希链表初始化
1 /*初始化哈希表*/
2 HashTable *InitHash(int TableSize)
3 {
4 int i = 0;
5 HashTable *hTable = NULL;
6 if (TableSize 0)
7 {
8 TableSize = DEFAULT_SIZE;
9 }
10 hTable = (HashTable *)malloc(sizeof(HashTable));
11
12 if (NULL == hTable)
13 {
14 printf("HashTable malloc error.\n");
15 return NULL;
16 }
17 hTable->TableSize = TableSize;
18
19 //为 Hash 桶分配内存空间，其为一个指针数组
20 hTable->Thelists = (List *)malloc(sizeof(List)*TableSize);
21 if (NULL == hTable->Thelists)
22 {
23 printf("HashTable malloc error\n");
24 free(hTable);
25 return NULL;
26 }
27
28 //为 Hash 桶对应的指针数组初始化链表节点
29 for (i = 0; i )
30 {
31 hTable->Thelists[i] = (ListNode *)malloc(sizeof(ListNode));
32 if (NULL == hTable->Thelists[i])
33 {
34 printf("HashTable malloc error\n");
35 free(hTable->Thelists);
36 free(hTable);
37 return NULL;
38 }
39 else
40 {
41 memset(hTable->Thelists[i], 0, sizeof(ListNode));
42 }
43 }
44 return hTable;
45 }
2.4 哈希链表插入元素
1 /*哈希表插入元素，元素为键值对*/
2 void Insert(HashTable *HashTable, int key, void *value )
3 {
4 Element e=NULL, tmp=NULL;
5 List L=NULL;
6 e = Find(HashTable, key);
7 if (NULL == e)
8 {
9 tmp = (Element)malloc(sizeof(ListNode));
10 if (NULL == tmp)
11 {
12 printf("malloc error\n");
13 return;
14 }
15 L = HashTable->Thelists[Hash(key, HashTable->TableSize)];
16 tmp->data = value;
17 tmp->key = key;
18 tmp->next = L->next;
19 L->next = tmp;
20 }
21 else
22 printf("the key already exist\n");
23 }
2.5 哈希链表查找元素
1 /*从哈希表中根据键值查找元素*/
2 Element Find(HashTable *HashTable, int key)
3 {
4 int i = 0;
5 List L = NULL;
6 Element e = NULL;
7 i = Hash(key, HashTable->TableSize);
8 L = HashTable->Thelists[i];
9 e = L->next;
10 while (e != NULL && e->key != key)
11 e = e->next;
12 return e;
13 }
2.6 哈希链表删除元素
1 /*哈希表删除元素，元素为键值对*/
2 void Delete(HashTable *HashTable, int key )
3 {
4 Element e=NULL, last=NULL;
5 List L=NULL;
6 int i = Hash(key, HashTable->TableSize);
7 L = HashTable->Thelists[i];
8 last = L;
9 e = L->next;
10
11 while (e != NULL && e->key != key)
12 {
13 last = e;
14 e = e->next;
15 }
16 if(e) //如果键值对存在
17 {
18 last->next = e->next;
19 delete(e);
20 }
21 }
3. 完整源码实现
1 #pragma once
2
3 #define DEFAULT_SIZE 16
4
5 /*哈希表元素定义*/
6 typedef struct _ListNode
7 {
8 struct _ListNode *next;
9 int key;
10 void *data;
11 }ListNode;
12
13 typedef ListNode *List;
14 typedef ListNode *Element;
15
16 /*哈希表结构定义*/
17 typedef struct _HashTable
18 {
19 int TableSize;
20 List *Thelists;
21 }HashTable;
22
23 /*哈希函数*/
24 int Hash( void *key, int TableSize );
25
26 /*初始化哈希表*/
27 HashTable *InitHash( int TableSize );
28
29 /*哈希表插入*/
30 void Insert(HashTable *HashTable, int key, void *value);
31
32 /*哈希表查找*/
33 Element Find( HashTable *HashTable, int key);
34
35 /*哈希表销毁*/
36 void Destory( HashTable *HashTable );
37
38 /*哈希表元素中提取数据*/
39 void *Retrieve( Element e );
1 #include