从零开始学习数据结构_哈希表.md

• 一、哈希表
• 二、哈希函数
• 三、解决冲突
  • 3.1 线性探测法
  • 3.2 二次探测法
  • 3.3 双散列法
  • 3.4 链地址法
• 四、除留余数法+开链法
  • 4.1 数据前插
  • 4.2 数据展示
  • 4.3 数据后插
  • 4.4 查找函数
  • 4.5 删除函数
• 五、完整代码
  • 5.1 完整代码
  • 5.2 测试代码
  • 5.3 运行结果
• 六、说明

哈希表的本质就是 K-V 结构，V 可以是链表、数组、数组链表等形式，需要灵活掌握这些数据结构，在代码实现，才能真正的掌握。

一、哈希表

理想情况是不希望经过任何比较，一次存取，便可以直接定位，这是需要一种映射关系，我们把这个映射关系就叫为哈希函数。

哈希表在对大数据的处理查找上，有明显优势。

若数据有序 --> 我们一般会想到二分查找；但是哈希查找更加犀利；

针对哈希查找，我们主要学习：

1. 如何构造哈希函数；
2. 怎么解决冲突问题；

二、哈希函数

这个哈希函数的构造方法比较多：

1. 直接定址法；
2. 数字分析法；
3. 平方取中法；
4. 折叠法；
5. 除留余数法；
6. 随机数法；

简单说一下，直接定址法，用的少，且需要空间过大；

以上的哈希函数，最常用的是除留余数法，那么什么是除留余数法？

在哈希表中，总空间大小为m，选一个 p，p 满足两个条件：

1. p <= m(越接近 m 越好)；
2. p 必须是质数;则哈希函数为：hash(key) = kep % p; (p<=m)；

p 为什么一定要选质数呢？

经过数学的理论推导，p 为质数时，可以保证模之后概率均等，均匀分布；p 要不是质数，则不满足随机、均匀这些条件，就不能保证每个数字均等存储。

三、解决冲突

3.1 线性探测法

线性探测法存储，此时存放的位置如下图，因为在下标为 1 处已经存放数字了，此时其后的数据也要存放到这个位置，产生冲突；按照线性探测法的解决方案：有冲突一直往后探测，直到有空间可以放数据时，就存储在那个位置。

模型图：

3.2 二次探测法

二次探测法存储，此时存放的位置如下图，因为在下标为 1 处已经存放数字了，此时其后的数据也要存放到这个位置，产生冲突；按照二次探测法的解决方案：有冲突先向左探测，若没有空间，再向右探测，来回左右探测，直到有空间可以放数据时，就存储在那个位置。

模型图：

以上的两种解决冲突的方案不是很好，缺点：定位准确度不高，查找起来效率较低。

3.3 双散列法

需要两个哈希函数，第一个元素直接就是记哈希表的下标，第二个记到达该数字的移位量，从而达到直接定位。

模型图：

3.4 链地址法

哈希表中存放的是指针(指向结点的指针)，在冲突处，通过指针连接起来。

模型图：

关于链表的连接问题：

• 头插 --> 效率比较高；
• 尾插 --> 效率相对来说比较低，(因为的一个一个的查找最后一个结点)；

解决尾插效率低的方案：以空间换时间，就是在哈希表中存放的是一个结构体类型，成员如下：

typedef struct HASH_TABLE{//哈希表也就是线性表结构，表中每个数据的类型;
    HASH_NODE *first;  //指向哈希结点(链表结点)的指针;first始终指向第一个结点;
    HASH_NODE *last;   //last始终指向最后一个结点;
    int size;   //size记录其上挂了多少数据;可有可无,看实际需求;
}HASH_TABLE;

四、除留余数法+开链法

此次全部代码均用 C 语言实现，与 C++ 不牵扯。

我把函数声明和定义放到了一个 .h 文件中，只是为了方便实现，本应该分开存放；

除留余数法的重点是：hash() 函数；开链法的重点是：链表的操作。

哈希表上应有的操作函数(其实主要是链表的操作)

void initHashTable(HashTable ht);  //初始化哈希表
void prevInsert(HashTable ht, ElemType value);  //数据的前插
void showHashTable(HashTable ht);  //显示数据
void endInsert(HashTable ht, ElemType value); //数据的后插
HASH_NODE* find(HashTable ht, ElemType value); //查找函数
boolean remove_(HashTable ht, ElemType value); //删除哈希表中的数据
void destoryHashTable(HashTable ht);  //销毁哈希表
void clearHashTable(HASH_NODE *p);    //真正的销毁函数

4.1 数据前插

void prevInsert(HashTable ht, ElemType value){
    int index = Hash(value);
    HASH_NODE *p = (HASH_NODE *)malloc(sizeof(HASH_NODE));
    p->data = value;
    p->next = NULL;  //前插，这条语句可以不写;

    p->next = ht[index];
    ht[index] = p;
}

4.2 数据展示

void showHashTable(HashTable ht){
    int i;
    HASH_NODE *p;

    for(i = 0; i < P; i++){
        printf("%d : ", i);
        if(ht[i]){
            p = ht[i];
            while(p){
                printf("%d-->", p->data);
                p = p->next;
            }
        }    
        printf("NULL\n");
    }
}

4.3 数据后插

void endInsert(HashTable ht, ElemType value){
    int index = Hash(value);
    HASH_NODE *p = (HASH_NODE *)malloc(sizeof(HASH_NODE));
    HASH_NODE *q;

    p->data = value;
    p->next = NULL;

    if(ht[index] == NULL){ //判断是不是第一个结点;
        ht[index] = p;
    }else{
        q = ht[index];
        while(q->next){
            q = q->next;
        }
        q->next = p;
    }
}

4.4 查找函数

HASH_NODE* find(HashTable ht, ElemType value){
    int index = Hash(value);
    HASH_NODE *p = ht[index];

    while(p && p->data != value){ //没找完并且没找到，特别注意，已免发生内存非法访问！
        p = p->next;
    }
    
    return p;  //直接返回p;p为空就是没找到，否则就是找到了;
/*    
    if(p){
        return p;
    }else{
        return NULL;
    }
*/    
}

4.5 删除函数

boolean remove_(HashTable ht, ElemType value){
    int index = Hash(value);
    HASH_NODE *q;
    HASH_NODE *p = find(ht, value); //利用找到函数，求得要找值得地址

    if(p == NULL){ //为空，就是没找到，直接退出
        return FALSE;
    }
    q = ht[index];
    if(ht[index] == p){  //是第一个结点
        ht[index] = p->next;
    }else{
        while(q->next != p){ //其后结点的删除，也就是再找前驱节点；
            q = q->next;
        }
        q->next = p->next;
        free(p);
    }

    return TRUE;
}

五、完整代码

5.1 完整代码

#ifndef _HASH_TABLE_H_
#define _HASH_TABLE_H_

typedef unsigned char boolean;

#define TRUE    1
#define FALSE    0

#define P    7

#include<malloc.h>

//链表中的数据类型
typedef struct HASH_NODE{
    ElemType data;
    struct HASH_NODE *next;
}HASH_NODE;

//哈希表中的每个元素是指针类型，但是哈希表又是数组；所以为指针数组类型；
typedef HASH_NODE *HashTable[P];

int Hash(ElemType key){
    return key % P;
}

void initHashTable(HashTable ht);
void prevInsert(HashTable ht, ElemType value);
void showHashTable(HashTable ht);
void endInsert(HashTable ht, ElemType value);
HASH_NODE* find(HashTable ht, ElemType value);
boolean remove_(HashTable ht, ElemType value);
void destoryHashTable(HashTable ht);
void clearHashTable(HASH_NODE *p);

void clearHashTable(HASH_NODE *p){
    HASH_NODE *q;

    while(p){
        q = p->next;
        free(p);
        p = q;
    }
}
void destoryHashTable(HashTable ht){
    int i;

    for(i = 0; i < P; i++){
        clearHashTable(ht[i]);
        ht[i] = NULL;
    }
}
boolean remove_(HashTable ht, ElemType value){
    int index = Hash(value);
    HASH_NODE *q;
    HASH_NODE *p = find(ht, value); //利用找到函数，求得要找值得地址

    if(p == NULL){ //为空，就是没找到，直接退出
        return FALSE;
    }
    q = ht[index];
    if(ht[index] == p){  //是第一个结点
        ht[index] = p->next;
    }else{
        while(q->next != p){ //其后结点，也就是再找前驱节点；
            q = q->next;
        }
        q->next = p->next;
        free(p);
    }

    return TRUE;
}
HASH_NODE* find(HashTable ht, ElemType value){
    int index = Hash(value);
    HASH_NODE *p = ht[index];

    while(p && p->data != value){ //没找完并且没找到，特别注意,已免发生内存非法访问！
        p = p->next;
    }

    return p;
/*    
    if(p){
        return p;
    }else{
        return NULL;
    }
*/
}
void endInsert(HashTable ht, ElemType value){
    int index = Hash(value);
    HASH_NODE *p = (HASH_NODE *)malloc(sizeof(HASH_NODE));
    HASH_NODE *q;

    p->data = value;
    p->next = NULL;

    if(ht[index] == NULL){ //判断是不是第一个结点;
        ht[index] = p;
    }else{
        q = ht[index];
        while(q->next){
            q = q->next;
        }
        q->next = p;
    }
}
void showHashTable(HashTable ht){
    int i;
    HASH_NODE *p;

    for(i = 0; i < P; i++){
        printf("%d : ", i);
        if(ht[i]){
            p = ht[i];
            while(p){
                printf("%d-->", p->data);
                p = p->next;
            }
        }    
        printf("NULL\n");
    }
}
void prevInsert(HashTable ht, ElemType value){
    int index = Hash(value);
    HASH_NODE *p = (HASH_NODE *)malloc(sizeof(HASH_NODE));
    p->data = value;
    p->next = NULL;  //前插，这条语句可以不写;

    p->next = ht[index];
    ht[index] = p;
}
void initHashTable(HashTable ht){
    int i;

    for(i = 0; i < P; i++){
        ht[i] = NULL;
    }
}

#endif

5.2 测试代码

#include<stdio.h>

typedef int ElemType;

#include"hashTable.h"

void main(void){
    HashTable ht;
    int ar[] = {1, 8, 15, 3, 6, 2, 8, 9, 22, 31,};
    int n = sizeof(ar) / sizeof(int);
    int i;
    HASH_NODE *p; //C语言只能在所有的有效语句之前定义变量；
    boolean k;

    initHashTable(ht);//数组名称的传递退化为指针
    for(i = 0; i < n; i++){
        //prevInsert(ht, ar[i]);
        endInsert(ht, ar[i]);
    }
    showHashTable(ht);
    p = find(ht, 10);
    if(p){
        printf("找到了,地址为：%p\n", p);
    }else{
        printf("输入的数据不存在，没找到\n");
    }
    k = remove_(ht, 99);
    if(k){
        printf("删除成功\n");
    }else{
        printf("删除失败\n");
    }

    destoryHashTable(ht); //表空间在栈，数据存放在堆！随着程序结束，堆空间释放。   
}

5.3 运行结果

六、说明

原创文章链接：从零开始学习数据结构-->哈希表