• 哈希表— —链式实现

    哈希表的故事导入

    故事情节

            为了提高开发团队精神，缓解工作压力，某 IT 公司组织开发团队的 12 位男同事和测试团队 的 12 位女同事开展真人 CS 4vs4 野战联谊！面对性感的女同事，男同事们个个摩拳擦掌，跃跃欲 试！

            野战活动那天，根据男女搭配，干活不累的原则，带队的专业教练让男同事站成一排，女同 事站成一排，然后要求从女生这排开始从 1 开始报数，每个报数的队员都要记住自己的编号： 1， 2， 3，4。。。。。。林子里响起了百灵鸟般的报数声！

    报数时，教练发给每人一个白色的臂章贴在肩膀上，每个臂章上写着报数人自己报过的编号！

    当所有人都报完数后，教练发出命令将 24 人均分成 6 个组!

    编号除 6 能整除的为第一组： 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

    通过这种编号方式划分队列，无论队员归队，还是裁判确89认79队43员8身40份1，11都1非常方便，此后林 子里传来隆隆的笑声和枪炮声！ 这种编号的方式就是高效的散列，我们俗称“哈希”！ 以上过程是通过把关键码值 key（编号）映射到表中一个位置(数组的下标)来访问记录，以加 快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

    哈希表的原理精讲

    哈希表 - 散列表，它是基于快速存取的角度设计的，也是一种典型的“空间换时间”的做法

    键(key)： 组员的编号 如， 1 、 5 、 19 。 。 。

    值(value)： 组员的其它信息（包含 性别、年龄和战斗力等）

    索引: 数组的下标(0,1,2,3,4) ，用以快速定位和检索数据

    哈希桶: 保存索引的数组(链表或数组)，数组成员为每一个索引值相同的多个元素

    哈希函数: 将组员编号映射到索引上，采用求余法 ，如： 组员编号 19

     

    哈希链表的算法实现

    哈希链表数据结构的定义

    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;

    哈希函数

    1. /*根据 key 计算索引，定位 Hash 桶的位置*/
    2. int Hash(int key, int TableSize)
    3. {
    4.     return (key%TableSize);
    5. }

    哈希链表初始化

    1. /*初始化哈希表*/
    2. HashTable *InitHash(int TableSize)
    3. {
    4.     int i = 0;
    5.     HashTable *hTable = NULL;
    6.  
    7.     if (TableSize <= 0) {
    8.         TableSize = DEFAULT_SIZE;
    9.     }
    10.  
    11.     hTable = (HashTable *)malloc(sizeof(HashTable));
    12.     if (NULL == hTable)
    13.     {
    14.         printf("HashTable malloc error.\n");
    15.         return NULL;
    16.     }
    17.  
    18.     hTable->TableSize = TableSize;
    19.  
    20.     //为 Hash 桶分配内存空间，其为一个指针数组
    21.     hTable->Thelists = (List *)malloc(sizeof(List)*TableSize);
    22.     if (NULL == hTable->Thelists)
    23.     {    
    24.         printf("HashTable malloc error\n");
    25.         free(hTable);
    26.         return NULL;
    27.     }
    28.  
    29.     //为 Hash 桶对应的指针数组初始化链表节点
    30.     for (i = 0; i < TableSize; i++)
    31.     {
    32.         hTable->Thelists[i] = (ListNode *)malloc(sizeof(ListNode));
    33.         if (NULL == hTable->Thelists[i])
    34.         {
    35.             printf("HashTable malloc error\n");
    36.             free(hTable->Thelists);
    37.             free(hTable);
    38.             return NULL;
    39.         }
    40.         else
    41.         {
    42.             memset(hTable->Thelists[i], 0, sizeof(ListNode));
    43.         }
    44.     }
    45.  
    46.     return hTable;
    47. }

    哈希链表插入元素

    1. /*哈希表插入元素，元素为键值对*/
    2. void Insert(HashTable *HashTable, int key, void *value )
    3. {
    4.     Element e=NULL, tmp=NULL;
    5.     List L=NULL;
    6.  
    7.     e = Find(HashTable, key);
    8.     if (NULL == e)
    9.     {
    10.         tmp = (Element)malloc(sizeof(ListNode));
    11.  
    12.         if (NULL == tmp)
    13.         {
    14.             printf("malloc error\n");
    15.             return;
    16.         }
    17.  
    18.         L = HashTable->Thelists[Hash(key, HashTable->TableSize)];
    19.         tmp->data = value;
    20.         tmp->key = key;
    21.         tmp->next = L->next;
    22.         L->next = tmp;
    23.     }
    24.     else
    25.         printf("the key already exist\n");
    26. }

    哈希链表查找元素

    1. /*从哈希表中根据键值查找元素*/
    2. Element Find(HashTable *HashTable, int key)
    3. {
    4.     int i = 0;
    5.     List L = NULL;
    6.     Element e = NULL;
    7.  
    8.     i = Hash(key, HashTable->TableSize);
    9.     L = HashTable->Thelists[i];
    10.     e = L->next;
    11.  
    12.     while (e != NULL && e->key != key)
    13.         e = e->next;
    14.  
    15.     return e;
    16. }

    哈希链表删除元素

    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.     while (e != NULL && e->key != key)
    11.     {
    12.         last = e;
    13.         e = e->next;
    14.     }
    15.  
    16.     if(e)
    17.     {    //如果键值对存在
    18.         last->next = e->next;
    19.         delete(e);
    20.     }
    21. }

    源码实现：

    hash_table.h

    1. #pragma
    2.  
    3. #define DEFAULT_SIZE 16
    4.  
    5. typedef struct _ListNode
    6. {
    7. 	int key;
    8. 	void* data;
    9. 	struct _ListNode* next;
    10. }ListNode;
    11.  
    12. typedef ListNode* List;
    13. typedef ListNode* Element;
    14.  
    15. typedef struct _HashTable
    16. {
    17. 	int TableSize;
    18. 	List* Thelists;
    19. }HashTable;

    hash_table.cpp

    1. #include 
    2. #include 
    3. #include 
    4. #include "hash_table.h"
    5.  
    6. int Hash(int key, int TableSize)
    7. {
    8. 	return (key % TableSize);
    9. }
    10.  
    11. //初始化哈希表
    12. HashTable* InitHash(int TableSize)
    13. {
    14. 	HashTable* hTable = NULL;
    15. 	int i = 0;
    16. 	
    17. 	hTable = (HashTable*)malloc(sizeof(HashTable));
    18. 	if (hTable == NULL)
    19. 	{
    20. 		printf("分配哈希表失败！");
    21. 		return NULL;
    22. 	}
    23.  
    24. 	if (TableSize < 0)
    25. 	{
    26. 		TableSize = DEFAULT_SIZE;
    27. 	}
    28. 	hTable->TableSize = TableSize;
    29.  
    30. 	hTable->Thelists = (List *)malloc(sizeof(List) * TableSize);
    31. 	if (hTable->Thelists == NULL)
    32. 	{		
    33. 		printf("分配失败！");
    34. 		free(hTable);
    35. 		return NULL;
    36. 	}
    37.  
    38. 	for (int i = 0; i < TableSize; i++)
    39. 	{
    40. 		//if(sizeof(ListNode)
    41. 		hTable->Thelists[i] = (ListNode*)malloc(sizeof(ListNode));
    42.  
    43. 		if (hTable->Thelists[i] == NULL)
    44. 		{
    45. 			printf("分配失败！");
    46. 			free(hTable->Thelists);
    47. 			free(hTable);
    48. 			
    49. 			return NULL;
    50. 		}
    51. 		else
    52. 		{
    53. 			memset(hTable->Thelists[i], 0, sizeof(ListNode));
    54. 		}
    55. 	}
    56.  
    57. 	return hTable;
    58. }
    59.  
    60. //从哈希表中根据键值查找元素
    61. Element Find(HashTable* HashTable, int key)
    62. {
    63. 	int i = Hash(key, HashTable->TableSize);
    64. 	List L = NULL;
    65.  
    66. 	L= HashTable->Thelists[i];
    67.  
    68. 	Element e = NULL;
    69. 	e = L->next;
    70. 	while (e != NULL && e->key != key)
    71. 	{
    72. 		e = e->next;
    73. 	}
    74.  
    75. 	return e;
    76. }
    77.  
    78. void Insert(HashTable* HashTable, int key, void* value)
    79. {
    80. 	int i = 0;
    81. 	i = Hash(key, HashTable->TableSize);
    82. 	List L = NULL;
    83.  
    84. 	L = HashTable->Thelists[i];
    85.  
    86. 	Element tmp = Find(HashTable, key);
    87.  
    88. 	if (!tmp)
    89. 	{
    90. 		Element e = NULL;
    91. 		e = (Element)malloc(sizeof(ListNode));
    92. 		if (!e)
    93. 		{
    94. 			printf("分配失败！");
    95. 			return;
    96. 		}
    97.  
    98. 		e->data = value;
    99. 		e->key = key;
    100. 		e->next = L->next;
    101. 		L->next = e;
    102. 	}
    103. 	else
    104. 	{
    105. 		printf("表中有重复键值");
    106. 	}
    107. }
    108.  
    109. void Delete(HashTable* HashTable, int key)
    110. {
    111. 	int i = Hash(key, HashTable->TableSize);
    112. 	List L = NULL;
    113. 	L = HashTable->Thelists[i];
    114.  
    115. 	Element next = NULL, cur = NULL;
    116. 	next = L->next;
    117. 	cur = L;
    118. 	while (next != NULL && next->key != key)
    119. 	{
    120. 		cur = next;
    121. 		next = next->next;
    122. 	}
    123.  
    124. 	if (next)
    125. 	{
    126. 		cur->next = next->next;
    127. 		delete(next);
    128. 	}
    129. }
    130.  
    131. void* Retrieve(Element e)
    132. {
    133. 	return e ? e->data : NULL;
    134. }
    135.  
    136. void Destory(HashTable* HashTable)
    137. {
    138. 	int i = 0;
    139. 	List L = NULL;
    140. 	Element cur = NULL, next = NULL;
    141. 	
    142. 	for (int i = 0; i < HashTable->TableSize; i++)
    143. 	{
    144. 		L = HashTable->Thelists[i];
    145. 		cur = L->next;
    146. 		while (cur != NULL)
    147. 		{
    148. 			next = cur->next;
    149. 			free(cur);
    150. 			cur = next;
    151. 		}
    152. 		free(L);
    153. 	}
    154. 	free(HashTable->Thelists);
    155. 	free(HashTable);
    156. }
    157.  
    158. int main(void)
    159. {
    160. 	char *elems[] = { "翠花","小芳","老师" };
    161. 	int i = 0;
    162.  
    163. 	HashTable* HashTable;
    164. 	HashTable = InitHash(31);
    165. 	Insert(HashTable, 1, elems[0]);
    166. 	Insert(HashTable, 2, elems[1]);
    167. 	Insert(HashTable, 3, elems[2]);
    168. 	Delete(HashTable, 1);
    169.  
    170. 	for (i = 0; i < 4; i++)
    171. 	{
    172. 		Element e = Find(HashTable, i);
    173. 		if (e)
    174. 		{
    175. 			printf("%s\n", (const char*)Retrieve(e));
    176. 		}
    177. 		else
    178. 		{
    179. 			printf("Not found [key:%d]\n", i);
    180. 		}
    181. 	}
    182.  
    183. 	system("pause");
    184. 	return 0;
    185. }
  • 相关阅读:
    【基于能量的模型】
    安卓大作业 图书管理APP
    浅谈HTTP
    [数据分析与可视化] 基于Python绘制简单动图
    ESP8266开发环境搭建踩坑
    【Nano Framework ESP32篇】使用 LCD 屏幕
    Swift 5.9 有哪些新特性（二）
    IS-IS
    浏览器网络无法连接github的解决办法
    SQL的ROUND函数用法及其实例
  • 原文地址：https://blog.csdn.net/m0_65635427/article/details/127811134