哈希表的原理及其演算法實作(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");
}