【数据结构】哈希表(C++)

哈希表

概念

哈希表-散列表， 它是基于快速存储的角度设计的，也是一种典型的“空间换时间”的做法。

(键值(编号)就代表了这个数据。)

链式存储实现

#include<iostream>
using namespace std;

#define DEFAULT_SIZE 16

typedef struct	_ListNode
{
	struct _ListNode* next;
	int key;
	void* data;
}ListNode;


//提高可读性和可维护性
typedef ListNode* List;
typedef ListNode* Element;


typedef struct _HashTable
{
	int TableSize;//哈希桶的大小
	List* ThisList;
}HashTable;

//根据key,计算索引，定位Hash桶的位置
int Hash(int key, int TableSize)
{
	return (key % TableSize);
}

//初始化哈希表
HashTable* initHash(int TableSize)
{

	HashTable* hTable = NULL;
	if (TableSize <= 0)
	{
		TableSize = DEFAULT_SIZE;
	}
	hTable = new HashTable;
	hTable->TableSize = TableSize;
	hTable->ThisList = new List[TableSize];//哈希桶	
	if (!hTable->ThisList)	
	{
		return NULL;
	}
	
	//为Hash桶的对应指针数组初始化链表结点	
	for (int i = 0; i < TableSize; i++)
	{
		hTable->ThisList[i] = new ListNode;
		if (!hTable->ThisList[i])
		{
			return NULL;
		}
		else
		{
			memset(hTable->ThisList[i], 0, sizeof(ListNode));
		}
	}

	return hTable;
}

//哈希表中查找元素
Element findHash(HashTable* hashtable, int key)
{
	int i = 0;
	List L = NULL;
	Element e = NULL;
	i = Hash(key, hashtable->TableSize);
	L = hashtable->ThisList[i];
	e = L->next;
	while (e && e->key != key)
	{
		e = e->next;
	}
	return e;
}

//哈希表插入元素
void insertHash(HashTable* hashtable, int key, void* value)
{
	Element e = NULL, tmp = NULL;
	List L = NULL;
	e = findHash(hashtable, key);

	if (!e) 
	{
		tmp = new ListNode;
		if (!tmp)
		{
			return;
		}
		L = hashtable->ThisList[Hash(key, hashtable->TableSize)];//前插法 
		tmp->data = value;
		tmp->key = key;
		tmp->next = L->next;
		L->next = tmp;
	}
	else
	{
		cout << "这个键已经存在" << endl;
	}
}

//哈希表删除元素
void DeleteHash(HashTable* hashtable, int key)
{
	Element e = NULL, last = NULL;
	List L = NULL;
	int i = Hash(key, hashtable->TableSize);
	L = hashtable->ThisList[i];
	last = L;
	e = L->next;
	//key是所对应数据的数字代号，这个每个元素是不同的，i是对应数据所在的hash桶，也就是key % tablesize,多个元素可以是同一个
	while (e && e->key != key)
	{
		last = e;
		e = e->next;
	}
	if (e)
	{
		last->next = e->next;
		delete e;
	}
	else
	{
		cout << "该key不存在" << endl;
	}
}

//找到对应的ListNode提取元素
void* extract(Element e)
{
	return  e ? e->data : NULL;
}
int main(void)
{
	  char *elems1 ="王小花";
	  char *elems2 ="李小华";
	  char *elems3 ="张富贵";


	 HashTable* hashtable = NULL;
	 hashtable = initHash(31);
	 insertHash(hashtable, 1, elems1);
	 insertHash(hashtable, 2, elems2);
	 insertHash(hashtable, 3, elems3);
		

	 //查找方式1
	 Element findky = findHash(hashtable, 2);
	 if (findky)
	 {
		 cout << (const char*)findky->data << endl;//强转
	 }
	 else
	 {
		 cout << "Not Find this Key!" << endl;
	 }


	//查找方式2	
	Element e = findHash(hashtable, 1);
	if (e)
	{
		cout << (const char*)extract(e) << endl;
	}
	else
	{
		cout << "Not Find this Key!" << endl;
	}


	return 0;
}

顺序存储实现

#include<iostream>
using namespace	 std;

#define Hash_Size 50
#define Hash_Bucket 128

typedef struct _HashMem//哈希表存储的数据类型
{
	int key;
	void* data;
}HashMember;

typedef struct _hash
{
	HashMember Hash_Table[Hash_Bucket][Hash_Size];
	int _HashSize;//哈希桶的索引
}Hash_Table;


//多个计数器不能指向同一个计数器变量，并且不能是局部变量，所以在这里创建一个全局的计数器变量数组
int CountArry[Hash_Bucket];


//初始化
bool initHashtable(Hash_Table*	hashtable)
{
	if (!hashtable)
	{
		return false;
	}

	hashtable->_HashSize = Hash_Bucket;//哈希桶
	
	if (!hashtable->Hash_Table)
	{
		return false;
	}
	
	//为每个哈希桶在第[0]位置添加一个记录当前桶中元素个数的计数器

	for (int i = 0; i < Hash_Bucket; i++)
	{
		HashMember Count;
		int* count = &(CountArry[i]);
		Count.data = count;
		Count.key = -(i + 1);
		hashtable->Hash_Table[i][0] = Count;
	}
	return true;
}

//计算要存储元素的哈希桶索引
int Hash(int key,int hash_bucket)
{
	return (key % Hash_Bucket);
}
//查找元素
bool findHashtable(Hash_Table* hashtable, int key)
{
	//先找到对应的哈希桶
	int index = Hash(key, Hash_Bucket);
	int count = *((int*)(hashtable->Hash_Table[index][0].data));//对应桶中的元素个数
	for (int i = 1; i < count + 1; i++)
	{
		if (hashtable->Hash_Table[index][i].key == key)
		{
			return true;
		}
	}
	return false;
}

//插入元素
void insertHashtable(Hash_Table* hashtable, int key, void* data)
{
	if (!hashtable)
	{
		return;
	}
 
	int index = Hash(key, hashtable->_HashSize);

	HashMember newHashMember;
	newHashMember.data = data;
	newHashMember.key = key;
	
	bool isExistence = findHashtable(hashtable,key);//先找一下，如果没有就往对应的哈希桶中塞。


	if (!isExistence)
	{
		//找到每个哈希桶的计数器，在当前计数器数量所指向的位置的下一个位置放入元素，然后自增计数器。
		hashtable->Hash_Table[index][*((int*)(hashtable->Hash_Table[index][0].data))+1] = newHashMember;
		(*((int*)(hashtable->Hash_Table[index][0].data)))++;
	}
	else
	{
		cout << "该key已经存在了" << endl;
	}
}

//删除元素
bool deleteHashtable(Hash_Table* hashtable,int key)
{
	if (!hashtable)
	{
		return false;
	}
	
	if (findHashtable(hashtable, key))//找到了才能删除
	{
		//找到了，去那拿对应的哈希桶
		int index = Hash(key, hashtable->_HashSize);
		//拿到桶中的元素个数	
		int count = *((int*)hashtable->Hash_Table[index][0].data);
		int i = 1;
		for (i; i < count + 1; i++)
		{
			if (hashtable->Hash_Table[index][i].key == key)
			{
				break;
			}
		}
		//此时的i的位置就是对应key的位置
		for (int j = i; j < count - 1; j++)
		{
			hashtable->Hash_Table[index][j] = hashtable->Hash_Table[index][j + 1];
		}
		//计数器--
		(*((int*)hashtable->Hash_Table[index][0].data))--;
		return true;
	}
	else
	{
		return false;
	}

}

//清理哈希表
bool cleanHashtable(Hash_Table* hashtable)
{
	if (!hashtable)
	{
		return false;
	}	
	//将每个哈希桶的计数器置为0 
	for (int i = 0; i < Hash_Bucket; i++)
	{
		*((int*)hashtable->Hash_Table[i][0].data) = 0;
	}

	return true;
}

int main(void)
{
	Hash_Table* hashtable = new Hash_Table;
	//初始化
	initHashtable(hashtable);
	char elem1[] = "李小花";
	char elem2[] = "赵铁柱";
	char elem3[] = "张全蛋";
	char elem4[] = "新二";
	char elem5[] = "小明";
	//插入
	insertHashtable(hashtable, 1,elem1);
	insertHashtable(hashtable, 2,elem2);
	insertHashtable(hashtable, 3,elem3);
	insertHashtable(hashtable, 4,elem4);
	insertHashtable(hashtable, 5,elem5);	
	//删除
	bool ret1 = deleteHashtable(hashtable, 1);
	//查找
	bool ret = findHashtable(hashtable, 1);
	if (ret)
	{
		cout << "存在" << endl;
	}
	else
	{
		cout << "不存在" << endl;
	}
	
	//清理
	cleanHashtable(hashtable);
	//销毁
	delete hashtable;
	hashtable = NULL;

	return 0;
}

实际应用

字串匹配

给定几个字符串，判断一个字符串从第2位到第4位的的字符是否在这几个字符串中。

重点在于，这个哈希表的key和对应的value是同一个。

key是由value转化过去的。

hash_table.h

#include<iostream>
using namespace std;

#define BUCKET_SIZE 1024
#define compare(a,b) strcmp((const char*)a,(const char*) b)

#define hash_func SDBMHash


typedef struct	_ListNode
{
	struct _ListNode* next;
	void* key;
	void* data;
}ListNode;

//提高可读性和可维护性
typedef ListNode* List;
typedef ListNode* Element;


typedef struct _HashTable
{
	int TableSize;//哈希桶的大小
	List* ThisList;
}HashTable;



//把字符串对应内容转化为整数类型的key(不改变原来内容)
unsigned int SDBMHash(void* key)
{
	unsigned int hash = 0;
	char* str = (char*)key;
	while (*str)
	{
		hash = (*str++) + (hash << 6) + (hash << 16) - hash;//让映射到的整数尽可能均匀，不出现重叠。

	}
	return (hash & 0x7FFFFFFF);
}


//根据key,计算索引，定位Hash桶的位置
int Hash(void* key, int TableSize)
{
	return hash_func(key) % TableSize;
}



//初始化哈希表
HashTable* initHash(int TableSize)
{

	HashTable* hTable = NULL;
	if (TableSize <= 0)
	{
		TableSize = BUCKET_SIZE;
	}
	hTable = new HashTable;
	hTable->TableSize = TableSize;
	hTable->ThisList = new List[TableSize];//哈希桶	
	if (!hTable->ThisList)
	{
		return NULL;
	}

	//为Hash桶的对应指针数组初始化链表结点	
	for (int i = 0; i < TableSize; i++)
	{
		hTable->ThisList[i] = new ListNode;
		if (!hTable->ThisList[i])
		{
			return NULL;
		}
		else
		{
			memset(hTable->ThisList[i], 0, sizeof(ListNode));
		}
	}

	return hTable;
}

//哈希表中查找元素
Element findHash(HashTable* hashtable, void* key)
{
	int i = 0;
	List L = NULL;
	Element e = NULL;

	i = Hash(key, hashtable->TableSize);//将这个字符串类型的key转化为哈希桶索引，找到该元素要放置的桶


	L = hashtable->ThisList[i];//对应的哈希桶

	e = L->next;

	while (e && compare(e->key, key) != 0)
	{
		e = e->next;
	}
	return e;
}

/*
	不要被类型限制了，本质上和key是int类型的哈希表是一样的。
*/


//哈希表插入元素
void insertHash(HashTable* hashtable, void* key, void* value)
{
	Element e = NULL, tmp = NULL;
	List L = NULL;
	e = findHash(hashtable, key);

	if (!e)
	{
		tmp = new ListNode;
		if (!tmp)
		{
			return;
		}
        //L为其对应位置的哈希桶
        //将新插入的结点与桶链接起来
		L = hashtable->ThisList[Hash(key, hashtable->TableSize)];//前插法 
		tmp->data = value;
		tmp->key = key;
		tmp->next = L->next;
		L->next = tmp;
	}
	else
	{
		cout << "这个键已经存在" << endl;
	}
}

//哈希表删除元素
void DeleteHash(HashTable* hashtable, void* key)
{
	Element e = NULL, last = NULL;
	List L = NULL;
	int i = Hash(key, hashtable->TableSize);//找到对应的哈希桶,然后在对应的哈希桶里面一个一个地遍历
	L = hashtable->ThisList[i];
	last = L;
	e = L->next;
	//key是所对应数据的数字代号，这个每个元素是不同的，i是对应数据所在的hash桶，也就是key % tablesize,多个元素可以是同一个
	while (e && !compare(e->key, key))
	{
		last = e;
		e = e->next;
	}
	if (e)
	{
		last->next = e->next;
		delete e;
	}
	else
	{
		cout << "该key不存在" << endl;
	}
}

//找到对应的ListNode提取元素
void* extract(Element e)
{
	return  e ? e->data : NULL;
}

//销毁哈希表
void destoryHash(HashTable* hashtable)
{
	List L = NULL;
	Element cur = NULL, next = NULL;
	for (int i = 0; i < hashtable->TableSize; i++)
	{
		L = hashtable->ThisList[i];
		cur = L->next;
		while (cur)
		{
			next = cur->next;
            delete cur;
			cur = next;
		}

		delete(L);
	}
	delete (hashtable->ThisList);
	delete (hashtable);
}

test.cpp

#include<iostream>
#include"hash_table.h"
using namespace std;

int main(void)
{
	char elems1[] = "ADBB";
	char elems2[] = "BDDC";
	char elems3[] = "CDBC";
	char elems4[] = "BDBB";

	const char* tester = "ABDBBAC";
	char cur[5] = { '\0' };

	int i = 0;


	HashTable* hashtable = NULL;
	hashtable = initHash(BUCKET_SIZE);

	insertHash(hashtable, elems1, elems1);
	insertHash(hashtable, elems2, elems2);
	insertHash(hashtable, elems3, elems2);
	insertHash(hashtable, elems4, elems4);


	//将要进行检查的字符串的2-4个字符拿过来进行对比
	strncpy_s(cur, tester + 1, 4);

	Element e = findHash(hashtable, cur);
	if (e)
	{
		cout << "找到了" << endl;
	}
	else
	{
		cout << "没找到" << endl;
	}
	destoryHash(hashtable);
	return 0;
}