【数据结构与算法】哈希表

一.哈希表的原理

假设我们有24位成员,我们要进行分组,那么我们可以这样分:
首先对24位成员进行1~24的编号.
假如我们要分6组,那么我们用成员自己的编号 %6余数相同的分为一组.

那么我们就可以很快的得到如上的分组.
为什么要如此分?答案是我们可以很快的找到我们要的人,你只需要 %6就可以很快的知道在哪一组,可以一下子排除5组,比二分法还牛逼.
所以其查找效率是非常惊人的.

像这张表我们就可以称其为哈希表,又称为散列.
我们来看哈希表的几个重要的组成成分,编号我们称之为关键码(key),对关键码取模这是一种散列函数,当然不止取模.取模是最常见的.

二.哈希链表数据结构

哈希表的实现既可以用链式结构也可以用顺序结构.
这里我们采用链式结构.
哈希表的重点在于分组,那么我们就可以用余数来作为组数.

可以将其作为一个头节点存放在一个数组中,方便我们索引.

ListNode是节点,其中包含关键码,数据,和指向下一个节点的指针.
HashTable就是我们刚刚画的那个头结点数组,因为动态分配内存.
Thelists我们用的二级指针,里面放的是节点指针.
tableSize就是有多少组.

三.哈希链表的算法实现

1.哈希函数

就是为了将我们的关键码转换到对应的组中.

2.哈希链表初始化

对于哈希表的初始化,我们要传入一个组数.
如果组数为负,我们就用默认的宏.
对哈希表动态分配内存,不成功就直接返回.

接下来就对头结点数组动态分配内存.
注意这里就是分配的数组了哦,*TableSize

然后对数组内的节点动态分配内存.
分配完后,我们将数据都设置为空,就是作为该组头节点.

现在就相当于这样:

3.哈希链表查找元素

我们要查找一个元素,那么我们先要知道其组号.
用哈希函数就可以知道.
然后在组中比对即可.
因为组的第一个是头节点,我们从第二个进行对比.
找到之后,返回节点.

4.哈希链表插入元素

首先我们需要先进行查找,因为我们的编号是具有唯一性的.
如果已经存在就不能进行插入.
如果不存在,我们就动态分配一个节点,对其赋值,然后插入其中.
我们还是要用哈希函数来确定我们擦入那个组.
这里我们用的前插法.

5.哈希链表删除元素

先找到要删除位置的组,然后进行删除.
用last来指向要删除节点的上一个节点,这样就可以直接删除了.
如果为空说明没找到.

6.哈希链表获取数据

因为我们查找是得到的节点,所以我们用这个来获取节点的数据.
注意数据类型转换,因为我们数据用的void*

7.哈希链表的销毁

有动态分配内存的地方,我们就要释放,我们要对节点释放,对头结点释放,对头结点数组释放,对哈希表释放.

8.图释

就像这样.

四.完整代码

1.头文件

#pragma once
#define DEFAULT_SIZE 16typedef struct _ListNode
{int key;struct _ListNode* next;void* data;
}ListNode;typedef ListNode* List;
typedef ListNode* Element;typedef struct _HashTable
{int tableSize;List* Thelists;
}HashTable;int Hash(int key, int TableSize);HashTable* initHash(int tableSize);void insert(HashTable* HashTable, int key, void* value);Element Find(HashTable* HashTable, int key);void Destory(HashTable* HashTable);void* Retrieve(Element e);

2…c文件

#include<stdio.h>
#include <stdlib.h>
#include<string.h>
#include"hash_table.h"int Hash(int key, int TableSize)
{return key % TableSize;
}HashTable* initHash(int TableSize)
{HashTable* hTable = NULL;if (TableSize <= 0){TableSize = DEFAULT_SIZE;}hTable = (HashTable*)malloc(sizeof(HashTable));if (hTable == NULL){printf("HashTable malloc error.\n");return NULL;}hTable->tableSize = TableSize;hTable->Thelists = (List*)malloc(sizeof(List) * TableSize);if (hTable->Thelists == NULL){printf("HashTable malloc error.\n");free(hTable);return NULL;}for (int i = 0; i < TableSize; i++){hTable->Thelists[i] = (ListNode*)malloc(sizeof(ListNode));if (hTable->Thelists[i] == NULL){printf("HashTable malloc error.\n");free(hTable->Thelists);free(hTable);return NULL;}else{memset(hTable->Thelists[i], 0, sizeof(ListNode));}}return hTable;
}Element Find(HashTable* HashTable, int key)
{int i = 0;List L = NULL;Element e = NULL;i = Hash(key, HashTable->tableSize);//得到下标L = HashTable->Thelists[i];//得到组的头节点e = L->next;//从第一个真正的元素开始.while (e!=NULL&&e->key!=key){e = e->next;}return e;
}void insert(HashTable* HashTable, int key, void* value)
{Element e = NULL, tmp = NULL;List L = NULL;e = Find(HashTable, key);if (e==NULL){tmp = (Element)malloc(sizeof(ListNode));if (tmp == NULL){printf("malloc error\n");return;}int i = Hash(key, HashTable->tableSize);L = HashTable->Thelists[i];tmp->data = value;tmp->key = key;tmp->next = L->next;//前插法L->next = tmp;}else{printf("the key already exist\n");}
}void Delete(HashTable* HashTable, int key)
{Element e = NULL, last = NULL;List L = NULL;int i= Hash(key, HashTable->tableSize);L = HashTable->Thelists[i];last = L;e = L->next;while (e!=NULL&&e->key!=key){last = e;e = e->next;}if (e){last->next = e->next;free(e);}
}void* Retrieve(Element e)
{return e ? e->data : NULL;
}void Destory(HashTable* HashTable)
{int i = 0;List L = NULL;Element cur = NULL, next = NULL;for (i = 0; i < HashTable->tableSize; i++){L = HashTable->Thelists[i];cur = L->next;while (cur!=NULL){next = cur->next;free(cur);cur = next;}free(L);}free(HashTable->Thelists);free(HashTable);
}int main(void)
{char* elems[] = { "姚哥","小美","大美" };int i = 0;HashTable* HashTable;HashTable = initHash(31);insert(HashTable, 1, elems[0]);insert(HashTable, 2, elems[1]);insert(HashTable, 3, elems[2]);Delete(HashTable, 1);for (int i = 0; i < 4; i++){Element e = Find(HashTable, i);if (e){printf("%s\n", (const char* )Retrieve(e));}else{printf("not found [key:%d]\n", i);}}system("pause");return 0;
}

3.运行结果