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++数据结构详解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
MATLAB 中 A(7)=[];什么意思？-icode9专业技术文章分享11-26
-
UniApp 中如何实现使用输入法时保持页面列表不动的效果？-icode9专业技术文章分享11-26
-
在 UniApp 中怎么实现输入法弹出时禁止页面向上滚动？-icode9专业技术文章分享11-26
-
WebSocket是什么，怎么使用？-icode9专业技术文章分享11-26
-
页面有多个ref 要动态传入怎么实现？-icode9专业技术文章分享11-26
-
在 UniApp 中实现一个底部输入框的常见方法有哪些？-icode9专业技术文章分享11-26
-
RocketMQ入门指南：搭建与使用全流程详解11-26
-
RocketMQ入门教程：轻松搭建与使用指南11-26
-
手写RocketMQ：从入门到实践的简单教程11-26
-
【机器学习(二)】分类和回归任务-决策树(Decision Tree,DT)算法-Sentosa_DSML社区版11-25
-
增量更新怎么做？-icode9专业技术文章分享11-23
-
压缩包加密方案有哪些？-icode9专业技术文章分享11-23
-
用shell怎么写一个开机时自动同步远程仓库的代码？-icode9专业技术文章分享11-23
-
webman可以同步自己的仓库吗？-icode9专业技术文章分享11-23
-
在 Webman 中怎么判断是否有某命令进程正在运行？-icode9专业技术文章分享11-23
栏目导航
