devbox
小小林熬夜学编程
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

哈希表（散列表）——C++数据结构详解_哈希表数据结构代码c++

作者：小小林熬夜学编程 | 2024-05-16 13:01:48

赞

踩

哈希表数据结构代码c++

目录

 1.哈希表原理精讲

​2.哈希链表算法实现

 2.1哈希表数据结构定义

 2.2哈希函数

2.3哈希链表初始化

2.4哈希链表查找函数

2.5哈希链表插入函数

2.6哈希链表删除元素

3.哈希表完整代码

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

 假设：给24个人依次给予编号，从1到24

编号除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

  这样，当我们给出一个编号时，根据除6的余数，可以直接排除20个数据 ，从而更快速的找到他。

 1.哈希表原理精讲

键（key) ： 组员的编号        如，1、5、19.....

值（value）：组员的其他信息（包含  性别、年龄、薪水等）

索引： 数组的下标（0，1，2，3，4），用以快速定位和检索数据

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

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

2.哈希链表算法实现

 2.1哈希表数据结构定义

  1. #define DEFAULT_SIZE 16   //索引数组范围，或者说哈希桶的个数
  2.  
  3. typedef struct _ListNode {
  4. 	int key;		//键值
  5. 	void* data;		//数据
  6. 	struct _ListNode* next;
  7. }ListNode;
  8.  
  9.  
  10. typedef ListNode* List;
  11. typedef ListNode* Element;
  12.  
  13. typedef struct _HashTable {
  14. 	int TableSize;			///索引数组范围，或者说哈希桶的个数
  15. 	List* Thelists;
  16. }HashTable;

 2.2哈希函数

  1. //这里采用求余法做Hash函数
  2. int Hash(int key, int TableSize) {
  3. 	return(key % TableSize);
  4. }

2.3哈希链表初始化

  1. //哈希表初始化	TableSize决定哈希桶的数量或者说索引范围
  2. HashTable* InitHash(int TableSize) {
  3. 	int i = 0;
  4. 	HashTable* hTable = NULL;
  5. 	if (TableSize <= 0) {
  6. 		TableSize = DEFAULT_SIZE;   //如果传入值小于0，就给予默认值
  7. 	}
  8.  
  9. 	hTable = (HashTable*)malloc(sizeof(HashTable));
  10. 	if (NULL == hTable) {
  11. 		printf("HashTable malloc error\n");
  12. 		return NULL;
  13. 	}
  14.  
  15. 	hTable->TableSize = TableSize;
  16. 	hTable->Thelists = NULL;
  17. 	//指针数组，指针的数组需要拿指针的指针接收
  18. 	hTable->Thelists = (List*)malloc(sizeof(List) * TableSize);
  19. 	if (NULL == hTable) {
  20. 		printf("HashTable malloc error\n");
  21. 		free(hTable);
  22. 		return NULL;
  23. 	}
  24. 	//为Hash桶对应的指针数组初始换链表节点
  25. 	for (int i = 0; i < TableSize; i++) {
  26. 		hTable->Thelists[i] = (ListNode*)malloc(sizeof(ListNode));
  27. 		if (NULL == hTable->Thelists[i]) {
  28. 			printf("HashTable malloc error\n");
  29. 			free(hTable->Thelists[i]);
  30. 			free(hTable);
  31. 		}
  32. 		else {
  33. 			//key赋值为0，值域（void*）和下一个指针赋为空
  34. 			memset(hTable->Thelists[i], 0, sizeof(ListNode));
  35. 		}
  36. 	}
  37. 	return hTable;
  38. }

2.4哈希链表查找函数

  1. Element findHash(HashTable** hashTable,const int key)  {
  2. 	int index = 0;
  3. 	index = Hash(key, (*hashTable)->TableSize);
  4. 	List L = NULL;	//	L为对应哈希桶的指针
  5. 	L = (*hashTable)->Thelists[index];
  6. 	Element e = NULL;
  7. 	e = L->next;   //e为对应值指针
  8. 	while (e!=NULL&&e->key!=key) {
  9. 		e = e->next;
  10. 	}
  11. 	return e;
  12. }

2.5哈希链表插入函数

  1. void insertHash(HashTable** hashTable, const int key, void* value) {
  2. 	Element insertElement = NULL;
  3. 	insertElement = findHash(hashTable, key);
  4. 	if (insertElement == NULL) {
  5. 		Element temp = NULL;
  6. 		temp=(Element)malloc(sizeof(ListNode));
  7. 		if (temp == NULL) {
  8. 			printf("malloc error\n");
  9. 			return;
  10. 		}
  11. 		temp->next = NULL;
  12. 		List L = (*hashTable)->Thelists[Hash(key, (*hashTable)->TableSize)];
  13. 		temp->data = value;
  14. 		temp->key = key;
  15. 		temp->next = L->next;
  16. 		L->next = temp;
  17. 	}
  18. 	else {
  19. 		printf("The key alerdy exist\n");
  20. 	}
  21. }

2.6哈希链表删除元素

  1. void deleteHash(HashTable* &hashtable, int key) {
  2. 	int index = Hash(key, hashtable->TableSize);
  3. 	List L = NULL;
  4. 	L = hashtable->Thelists[index];
  5. 	Element last = L;
  6. 	Element compareHash = NULL;
  7. 	compareHash = L->next;
  8. 	while (compareHash != NULL && compareHash->key != key) {
  9. 		last = compareHash;
  10. 		compareHash = compareHash->next;
  11. 	}
  12. 	if (compareHash != NULL) {
  13. 		last->next = compareHash->next;
  14. 		free(compareHash);
  15. 	}
  16. }

测试程序：

  1. int main() {
  2. 	 char* a1 = (char*)"f张三";
  3. 	 char* a2 = (char*)"李四";
  4. 	 char* a3 = (char*)"王五";
  5. 	 char* a4 = (char*)"赵六";
  6. 	 char* arr[] = {a1,a2,a3,a4};
  7. 	 HashTable* hashtable;
  8. 	 hashtable = InitHash(17);
  9.  
  10. 	insertHash(&hashtable, 1, arr[0]);
  11. 	insertHash(&hashtable, 2, arr[1]);
  12. 	insertHash(&hashtable, 3, arr[2]);
  13. 	insertHash(&hashtable, 4, arr[3]);
  14. 	deleteHash(hashtable, 1);
  15.  
  16. 	for (int i = 0; i < 6; i++) {
  17. 		Element e = findHash(&hashtable, i);
  18. 		if (e) {
  19. 			printf("%s\n", (const char*)Retrieve(e));
  20. 		}
  21. 		else {
  22. 			printf("Not found [key:%d]\n", i);
  23. 		}
  24. 	}
  25. 	system("pause");
  26. 	return 0;
  27. }

运行结果：

程序图示：

3.哈希表完整代码

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. #define DEFAULT_SIZE 16   //索引数组范围，或者说哈希桶的个数
  5.  
  6. typedef struct _ListNode {
  7. 	int key;		//键值
  8. 	void* data;		//数据
  9. 	struct _ListNode* next;
  10. }ListNode;
  11.  
  12.  
  13. typedef ListNode* List;
  14. typedef ListNode* Element;
  15.  
  16. typedef struct _HashTable {
  17. 	int TableSize;			///索引数组范围，或者说哈希桶的个数
  18. 	List* Thelists;
  19. }HashTable;
  20.  
  21. //这里采用求余法做Hash函数
  22. int Hash(int key, int TableSize) {
  23. 	return(key % TableSize);
  24. }
  25.  
  26. //哈希表初始化	TableSize决定哈希桶的数量或者说索引范围
  27. HashTable* InitHash(int TableSize) {
  28. 	int i = 0;
  29. 	HashTable* hTable = NULL;
  30. 	if (TableSize <= 0) {
  31. 		TableSize = DEFAULT_SIZE;   //如果传入值小于0，就给予默认值
  32. 	}
  33.  
  34. 	hTable = (HashTable*)malloc(sizeof(HashTable));
  35. 	if (NULL == hTable) {
  36. 		printf("HashTable malloc error\n");
  37. 		return NULL;
  38. 	}
  39.  
  40. 	hTable->TableSize = TableSize;
  41. 	hTable->Thelists = NULL;
  42. 	//指针数组，指针的数组需要拿指针的指针接收
  43. 	hTable->Thelists = (List*)malloc(sizeof(List) * TableSize);
  44. 	if (NULL == hTable) {
  45. 		printf("HashTable malloc error\n");
  46. 		free(hTable);
  47. 		return NULL;
  48. 	}
  49. 	//为Hash桶对应的指针数组初始换链表节点
  50. 	for (int i = 0; i < TableSize; i++) {
  51. 		hTable->Thelists[i] = (ListNode*)malloc(sizeof(ListNode));
  52. 		if (NULL == hTable->Thelists[i]) {
  53. 			printf("HashTable malloc error\n");
  54. 			free(hTable->Thelists[i]);
  55. 			free(hTable);
  56. 		}
  57. 		else {
  58. 			//key赋值为0，值域（void*）和下一个指针赋为空
  59. 			memset(hTable->Thelists[i], 0, sizeof(ListNode));
  60. 		}
  61. 	}
  62. 	return hTable;
  63. }
  64.  
  65. Element findHash(HashTable** hashTable,const int key)  {
  66. 	int index = 0;
  67. 	index = Hash(key, (*hashTable)->TableSize);
  68. 	List L = NULL;	//	L为对应哈希桶的指针
  69. 	L = (*hashTable)->Thelists[index];
  70. 	Element e = NULL;
  71. 	e = L->next;   //e为对应值指针
  72. 	while (e!=NULL&&e->key!=key) {
  73. 		e = e->next;
  74. 	}
  75. 	return e;
  76. }
  77.  
  78.  
  79.  
  80. void deleteHash(HashTable* &hashtable, int key) {
  81. 	int index = Hash(key, hashtable->TableSize);
  82. 	List L = NULL;
  83. 	L = hashtable->Thelists[index];
  84. 	Element last = L;
  85. 	Element compareHash = NULL;
  86. 	compareHash = L->next;
  87. 	while (compareHash != NULL && compareHash->key != key) {
  88. 		last = compareHash;
  89. 		compareHash = compareHash->next;
  90. 	}
  91. 	if (compareHash != NULL) {
  92. 		last->next = compareHash->next;
  93. 		free(compareHash);
  94. 	}
  95. }
  96.  
  97.  
  98.  
  99. void insertHash(HashTable** hashTable, const int key, void* value) {
  100. 	Element insertElement = NULL;
  101. 	insertElement = findHash(hashTable, key);
  102. 	if (insertElement == NULL) {
  103. 		Element temp = NULL;
  104. 		temp=(Element)malloc(sizeof(ListNode));
  105. 		if (temp == NULL) {
  106. 			printf("malloc error\n");
  107. 			return;
  108. 		}
  109. 		temp->next = NULL;
  110. 		List L = (*hashTable)->Thelists[Hash(key, (*hashTable)->TableSize)];
  111. 		temp->data = value;
  112. 		temp->key = key;
  113. 		temp->next = L->next;
  114. 		L->next = temp;
  115. 	}
  116. 	else {
  117. 		printf("The key alerdy exist\n");
  118. 	}
  119. }
  120.  
  121. void* Retrieve(Element e) {
  122. 	return e ? e->data : NULL;
  123. }
  124. int main() {
  125. 	 char* a1 = (char*)"f张三";
  126. 	 char* a2 = (char*)"李四";
  127. 	 char* a3 = (char*)"王五";
  128. 	 char* a4 = (char*)"赵六";
  129. 	 char* arr[] = {a1,a2,a3,a4};
  130. 	 HashTable* hashtable;
  131. 	 hashtable = InitHash(17);
  132.  
  133. 	insertHash(&hashtable, 1, arr[0]);
  134. 	insertHash(&hashtable, 2, arr[1]);
  135. 	insertHash(&hashtable, 3, arr[2]);
  136. 	insertHash(&hashtable, 4, arr[3]);
  137. 	deleteHash(hashtable, 1);
  138.  
  139. 	for (int i = 0; i < 6; i++) {
  140. 		Element e = findHash(&hashtable, i);
  141. 		if (e) {
  142. 			printf("%s\n", (const char*)Retrieve(e));
  143. 		}
  144. 		else {
  145. 			printf("Not found [key:%d]\n", i);
  146. 		}
  147. 	}
  148. 	system("pause");
  149. 	return 0;
  150. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/578852
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号