C/C++教程
哈希表（散列表）——C++数据结构详解
本文主要是介绍哈希表（散列表）——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哈希表数据结构定义
#define DEFAULT_SIZE 16 //索引数组范围，或者说哈希桶的个数
typedef struct _ListNode {
int key; //键值
void* data; //数据
struct _ListNode* next;
}ListNode;
typedef ListNode* List;
typedef ListNode* Element;
typedef struct _HashTable {
int TableSize; ///索引数组范围，或者说哈希桶的个数
List* Thelists;
}HashTable;
2.2哈希函数
//这里采用求余法做Hash函数
int Hash(int key, int TableSize) {
return(key % TableSize);
}
2.3哈希链表初始化
//哈希表初始化 TableSize决定哈希桶的数量或者说索引范围
HashTable* InitHash(int TableSize) {
int i = 0;
HashTable* hTable = NULL;
if (TableSize <= 0) {
TableSize = DEFAULT_SIZE; //如果传入值小于0，就给予默认值
}
hTable = (HashTable*)malloc(sizeof(HashTable));
if (NULL == hTable) {
printf("HashTable malloc error\n");
return NULL;
}
hTable->TableSize = TableSize;
hTable->Thelists = NULL;
//指针数组，指针的数组需要拿指针的指针接收
hTable->Thelists = (List*)malloc(sizeof(List) * TableSize);
if (NULL == hTable) {
printf("HashTable malloc error\n");
free(hTable);
return NULL;
}
//为Hash桶对应的指针数组初始换链表节点
for (int i = 0; i < TableSize; i++) {
hTable->Thelists[i] = (ListNode*)malloc(sizeof(ListNode));
if (NULL == hTable->Thelists[i]) {
printf("HashTable malloc error\n");
free(hTable->Thelists[i]);
free(hTable);
}
else {
//key赋值为0，值域（void*）和下一个指针赋为空
memset(hTable->Thelists[i], 0, sizeof(ListNode));
}
}
return hTable;
}
2.4哈希链表查找函数
Element findHash(HashTable** hashTable,const int key) {
int index = 0;
index = Hash(key, (*hashTable)->TableSize);
List L = NULL; // L为对应哈希桶的指针
L = (*hashTable)->Thelists[index];
Element e = NULL;
e = L->next; //e为对应值指针
while (e!=NULL&&e->key!=key) {
e = e->next;
}
return e;
}
2.5哈希链表插入函数
void insertHash(HashTable** hashTable, const int key, void* value) {
Element insertElement = NULL;
insertElement = findHash(hashTable, key);
if (insertElement == NULL) {
Element temp = NULL;
temp=(Element)malloc(sizeof(ListNode));
if (temp == NULL) {
printf("malloc error\n");
return;
}
temp->next = NULL;
List L = (*hashTable)->Thelists[Hash(key, (*hashTable)->TableSize)];
temp->data = value;
temp->key = key;
temp->next = L->next;
L->next = temp;
}
else {
printf("The key alerdy exist\n");
}
}
2.6哈希链表删除元素
void deleteHash(HashTable* &hashtable, int key) {
int index = Hash(key, hashtable->TableSize);
List L = NULL;
L = hashtable->Thelists[index];
Element last = L;
Element compareHash = NULL;
compareHash = L->next;
while (compareHash != NULL && compareHash->key != key) {
last = compareHash;
compareHash = compareHash->next;
}
if (compareHash != NULL) {
last->next = compareHash->next;
free(compareHash);
}
}
测试程序：
int main() {
char* a1 = (char*)"f张三";
char* a2 = (char*)"李四";
char* a3 = (char*)"王五";
char* a4 = (char*)"赵六";
char* arr[] = {a1,a2,a3,a4};
HashTable* hashtable;
hashtable = InitHash(17);
insertHash(&hashtable, 1, arr[0]);
insertHash(&hashtable, 2, arr[1]);
insertHash(&hashtable, 3, arr[2]);
insertHash(&hashtable, 4, arr[3]);
deleteHash(hashtable, 1);
for (int i = 0; i < 6; i++) {
Element e = findHash(&hashtable, i);
if (e) {
printf("%s\n", (const char*)Retrieve(e));
}
else {
printf("Not found [key:%d]\n", i);
}
}
system("pause");
return 0;
}
运行结果：
程序图示：
3.哈希表完整代码
#include<iostream>
using namespace std;
#define DEFAULT_SIZE 16 //索引数组范围，或者说哈希桶的个数
typedef struct _ListNode {
int key; //键值
void* data; //数据
struct _ListNode* next;
}ListNode;
typedef ListNode* List;
typedef ListNode* Element;
typedef struct _HashTable {
int TableSize; ///索引数组范围，或者说哈希桶的个数
List* Thelists;
}HashTable;
//这里采用求余法做Hash函数
int Hash(int key, int TableSize) {
return(key % TableSize);
}
//哈希表初始化 TableSize决定哈希桶的数量或者说索引范围
HashTable* InitHash(int TableSize) {
int i = 0;
HashTable* hTable = NULL;
if (TableSize <= 0) {
TableSize = DEFAULT_SIZE; //如果传入值小于0，就给予默认值
}
hTable = (HashTable*)malloc(sizeof(HashTable));
if (NULL == hTable) {
printf("HashTable malloc error\n");
return NULL;
}
hTable->TableSize = TableSize;
hTable->Thelists = NULL;
//指针数组，指针的数组需要拿指针的指针接收
hTable->Thelists = (List*)malloc(sizeof(List) * TableSize);
if (NULL == hTable) {
printf("HashTable malloc error\n");
free(hTable);
return NULL;
}
//为Hash桶对应的指针数组初始换链表节点
for (int i = 0; i < TableSize; i++) {
hTable->Thelists[i] = (ListNode*)malloc(sizeof(ListNode));
if (NULL == hTable->Thelists[i]) {
printf("HashTable malloc error\n");
free(hTable->Thelists[i]);
free(hTable);
}
else {
//key赋值为0，值域（void*）和下一个指针赋为空
memset(hTable->Thelists[i], 0, sizeof(ListNode));
}
}
return hTable;
}
Element findHash(HashTable** hashTable,const int key) {
int index = 0;
index = Hash(key, (*hashTable)->TableSize);
List L = NULL; // L为对应哈希桶的指针
L = (*hashTable)->Thelists[index];
Element e = NULL;
e = L->next; //e为对应值指针
while (e!=NULL&&e->key!=key) {
e = e->next;
}
return e;
}
void deleteHash(HashTable* &hashtable, int key) {
int index = Hash(key, hashtable->TableSize);
List L = NULL;
L = hashtable->Thelists[index];
Element last = L;
Element compareHash = NULL;
compareHash = L->next;
while (compareHash != NULL && compareHash->key != key) {
last = compareHash;
compareHash = compareHash->next;
}
if (compareHash != NULL) {
last->next = compareHash->next;
free(compareHash);
}
}
void insertHash(HashTable** hashTable, const int key, void* value) {
Element insertElement = NULL;
insertElement = findHash(hashTable, key);
if (insertElement == NULL) {
Element temp = NULL;
temp=(Element)malloc(sizeof(ListNode));
if (temp == NULL) {
printf("malloc error\n");
return;
}
temp->next = NULL;
List L = (*hashTable)->Thelists[Hash(key, (*hashTable)->TableSize)];
temp->data = value;
temp->key = key;
temp->next = L->next;
L->next = temp;
}
else {
printf("The key alerdy exist\n");
}
}
void* Retrieve(Element e) {
return e ? e->data : NULL;
}
int main() {
char* a1 = (char*)"f张三";
char* a2 = (char*)"李四";
char* a3 = (char*)"王五";
char* a4 = (char*)"赵六";
char* arr[] = {a1,a2,a3,a4};
HashTable* hashtable;
hashtable = InitHash(17);
insertHash(&hashtable, 1, arr[0]);
insertHash(&hashtable, 2, arr[1]);
insertHash(&hashtable, 3, arr[2]);
insertHash(&hashtable, 4, arr[3]);
deleteHash(hashtable, 1);
for (int i = 0; i < 6; i++) {
Element e = findHash(&hashtable, i);
if (e) {
printf("%s\n", (const char*)Retrieve(e));
}
else {
printf("Not found [key:%d]\n", i);
}
}
system("pause");
return 0;
}
这篇关于哈希表（散列表）——C++数据结构详解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
测试人员在 Scrum 中的角色是什么？07-08
-
Dify + TiDB Vector，快速构建你的AI Agent07-07
-
有没有什么开源的py项目可以对图像进行分类-icode9专业技术文章分享07-06
-
feign默认connecttimeout和readtimeout是多少-icode9专业技术文章分享07-05
-
idea控制台，日志太多，导致部分想看得日志被刷走 搜不到-icode9专业技术文章分享07-05
-
The server selected protocol version Tls10 is not accepted by client preferences [TLs12]-icode9专业技术文章分享07-05
-
怎么清理项目缓存-icode9专业技术文章分享07-05
-
安装 Eyoucms详细图文教程-icode9专业技术文章分享07-04
-
ueditor 复制文章时，图片的链接是一个下载图片地址，该如何处理？-icode9专业技术文章分享07-04
-
怎样判断host有没有对wordpress有缓存呢-icode9专业技术文章分享07-04
-
具有编译功能的系统make后，无法ssh连接-icode9专业技术文章分享07-04
-
make后如何升级ssh-icode9专业技术文章分享07-04
-
微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享07-03
-
微信支付提示订单号重复-icode9专业技术文章分享07-03
-
微服务启动nacos注册上去了，但是一直没有收到请求-icode9专业技术文章分享07-02
栏目导航
