哈希表的原理及其算法实现(C/C++描述)_c++哈希表的内部实现原理

目录

定义

相关属性

算法实现

1）数据结构

2）哈希函数

3）哈希链表初始化

4）哈希链表查找元素

5）哈希链表插入元素

6）哈希表删除元素

程序清单

---

定义

相关属性

算法实现

1）数据结构

#define DEFAULT_SIZE 3 //默认哈希表大小是3
 
typedef struct _ListNode
{
	int key;
	int data;
	struct _ListNode *next;
}ListNode,*List,*Element;//List作为每个哈希桶的头结点，不保存元素
 
typedef struct _HashTable
{
	List *Lists;//保存所有哈希桶头结点的数组
	int tableSize;//数组大小 也即哈希桶的个数
}HashTable;

2）哈希函数

//求余数法 根据key 定为桶的位置
int Hash(int key, int tableSize)
{
	return (key%tableSize);
}

 3）哈希链表初始化

//初始化哈希表
HashTable * InitHashTable(int tableSize)
{
	HashTable *ht=new HashTable;
	if (!ht) return NULL;
 
	tableSize <= 0 ? DEFAULT_SIZE : tableSize;//如果哈希表数组大小小于等于0 则取默认大小
	ht->tableSize = tableSize;
 
	ht->Lists = new List[tableSize];
	if (!ht->Lists)
	{
		delete ht;
		return NULL;
	}
 
	//为数组中每一个哈希桶的头结点初始化
	for (int i=0;i<tableSize;i++)
	{
		ht->Lists[i] = new ListNode;
		if (!ht->Lists[i])
		{
			delete ht->Lists;
			delete ht;
			return NULL;
		}
		
		//并将头结点置空
		memset(ht->Lists[i], 0, sizeof(ListNode));
	}
 
	return ht;
	
}

4）哈希链表查找元素

//根据key值查找哈希表中元素
Element Find(HashTable *ht,int key)
{
 
	int i = Hash(key, ht->tableSize);
	Element tmp = NULL;
    tmp = ht->Lists[i]->next; //取出key所在数据桶的第一个元素
 
	while (tmp!=NULL)
	{
		if (tmp->key == key) return tmp;//找到相同元素则将元素返回
		else tmp = tmp->next;//没有找到则继续找下一个
	}
 
	return tmp;
}

5）哈希链表插入元素

//插入元素
bool InsertHashTable(HashTable* &ht, int key, int value)
{
	
	if (Find(ht, key) != NULL)//如果找到了相对应的key的元素 则证明插入元素已经因为存在 因为键值key是惟一的
	{
		printf("Element has existed !");
		return false;
	}
	
	Element L = ht->Lists[Hash(key,ht->tableSize)];//找出 key所对应哈希桶的头结点
    
	//采用头插法插入元素
	Element q = new ListNode;
	if (!q) return false;
 
	q->data = value;
	q->key = key;
	q->next = L->next;
	L->next = q;
 
	return true;
 
}

6）哈希表删除元素

bool DeleteHashNode(HashTable* &ht, int key)
{
	int i = Hash(key, ht->tableSize);
 
	List L = ht->Lists[i];//找到key所在哈希桶的头结点
	Element e = L->next;//找到第一个元素
 
	while (e != NULL && e->key!=key)
	{
		L = e;
		e = e->next;
	}
 
	if (e == NULL)
		return false; //如果没有找到key所对应的元素 返回false
 
	//从桶链表中删除元素e
	L->next = e->next;
	delete e;
	return true;	
}

程序清单

// 哈希表Hash.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//Author：See QQ3492625357 
//代码为手写，程序通过简单测试，其中可能有误或不当之处欢迎指正
 
#include <iostream>
 
#define DEFAULT_SIZE 3 //默认哈希表大小是3
 
typedef struct _ListNode
{
	int key;
	int data;
	struct _ListNode *next;
}ListNode,*List,*Element;//List作为每个哈希桶的头结点，不保存元素
 
typedef struct _HashTable
{
	List *Lists;//保存所有哈希桶头结点的数组
	int tableSize;//数组大小 也即哈希桶的个数
}HashTable;
 
//求余数法 根据key 定为桶的位置
int Hash(int key, int tableSize)
{
	return (key%tableSize);
}
 
//初始化哈希表
HashTable * InitHashTable(int tableSize)
{
	HashTable *ht=new HashTable;
	if (!ht) return NULL;
 
	tableSize <= 0 ? DEFAULT_SIZE : tableSize;//如果哈希表数组大小小于等于0 则取默认大小
	ht->tableSize = tableSize;
 
	ht->Lists = new List[tableSize];
	if (!ht->Lists)
	{
		delete ht;
		return NULL;
	}
 
	//为数组中每一个哈希桶的头结点初始化
	for (int i=0;i<tableSize;i++)
	{
		ht->Lists[i] = new ListNode;
		if (!ht->Lists[i])
		{
			delete ht->Lists;
			delete ht;
			return NULL;
		}
		
		//并将头结点置空
		memset(ht->Lists[i], 0, sizeof(ListNode));
	}
 
	return ht;
	
}
 
//根据key值查找哈希表中元素
Element Find(HashTable *ht,int key)
{
 
	int i = Hash(key, ht->tableSize);
	Element tmp = NULL;
    tmp = ht->Lists[i]->next; //取出key所在数据桶的第一个元素
 
	while (tmp!=NULL)
	{
		if (tmp->key == key) return tmp;//找到相同元素则将元素返回
		else tmp = tmp->next;//没有找到则继续找下一个
	}
 
	return tmp;
}
 
//插入元素
bool InsertHashTable(HashTable* &ht, int key, int value)
{
	
	if (Find(ht, key) != NULL)//如果找到了相对应的key的元素 则证明插入元素已经因为存在 因为键值key是惟一的
	{
		printf("Element has existed !");
		return false;
	}
	
	Element L = ht->Lists[Hash(key,ht->tableSize)];//找出 key所对应哈希桶的头结点
    
	//采用头插法插入元素
	Element q = new ListNode;
	if (!q) return false;
 
	q->data = value;
	q->key = key;
	q->next = L->next;
	L->next = q;
 
	return true;
 
}
//删除元素
bool DeleteHashNode(HashTable* &ht, int key)
{
	int i = Hash(key, ht->tableSize);
 
	List L = ht->Lists[i];//找到key所在哈希桶的头结点
	Element e = L->next;//找到第一个元素
 
	while (e != NULL && e->key!=key)
	{
		L = e;
		e = e->next;
	}
 
	if (e == NULL)
		return false; //如果没有找到key所对应的元素 返回false
 
	//从桶链表中删除元素e
	L->next = e->next;
	delete e;
	return true;	
}
int main()
{
	int elem[] = { 100,200,300,400,500,600,700,800,900 };
 
	HashTable *HT = NULL;
	HT = InitHashTable(DEFAULT_SIZE);
	if (!HT) return -1; 
 
	for (int i=0;i< sizeof(elem) / sizeof(elem[0]);i++)
	{
		InsertHashTable(HT, i, elem[i]);
	}
	
	//输出测试
	for (int i = 0; i < sizeof(elem) / sizeof(elem[0]); i++)
	{
		Element tmp = Find(HT, i);
		if (tmp!=NULL)
		{
			std::cout << tmp->data << " ";
		}
		
	}
	std::cout << std::endl;
 
	//把key=3删除 测试输出结果
	DeleteHashNode(HT, 3);
	std::cout << "删除key=3 value=400 后 输出哈希表" << std::endl;
	for (int i = 0; i < sizeof(elem) / sizeof(elem[0]); i++)
	{
		Element tmp = Find(HT, i);
		if (tmp != NULL)
		{
			std::cout << tmp->data << " ";
		}
 
	}
	std::cout << std::endl;
 
	system("pause");
}