哈希表（散列表）——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;
}