哈希表
概念
哈希表-散列表， 它是基于快速存储的角度设计的，也是一种典型的“空间换时间”的做法。
(键值(编号)就代表了这个数据。)
链式存储实现
代码语言：javascript复制#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;
}顺序存储实现
代码语言：javascript复制#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
代码语言：javascript复制#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
代码语言：javascript复制#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] = { ' ' };
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;
}
