[数据结构与算法] 哈希表-数据结构(C语言)

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 哈希表-数据结构(C语言) -> 正文阅读

[数据结构与算法]哈希表-数据结构(C语言)

哈希表

什么是哈希表

我们在网站上注册账号时，当填好用户名后，系统都会判断用户名是否已被使用，如果已被使用，系统就会提示该用户名已被注册。那么系统是如何检测用户名是否被使用的呢？我们能想到的最简单的方法就是逐个比较，但是如果用户名有很多，查找效率就显得很低。还有一种方法就是把用户名按字典序排序进行二分查找，这个方法的效率的确是高了很多，可是前提是用户名是有序的，而有些时候我们并不能将用户名进行排序。那么还有没有更好的方法呢？

我们可以用 哈希表 来解决这个问题。哈希表又叫散列表，关键值通过哈希函数映射到数组上，查找时通过关键值直接访问数组。在上面的例子里，我们将用户名通过哈希函数映射成一个整数，也就是数组的存储位置，在检测时用同样方法计算出存储位置，如果位置上已有元素则表示用户名已经被注册。
哈希函数指的是关键值和存储位置建立的对应关系，查找时只要根据这个关系就能找到目标位置。一般我们只要通过一次查找就能找到目标位置，但有些关键字需要多次比较和查找才能找到，这是为什么呢？因为哈希表里，可能存在关键字不同但是哈希地址相同的情况，也就是产生了冲突。一般情况下，冲突是不可避免的，因为关键字集合往往比哈希地址集合大很多。
在这里插入图片描述
要提高哈希表的查找效率，关键在于合理的构造哈希函数和优秀的解决冲突的方法。哈希函数的构造方法有很多种，我们应该如何构造优秀的哈希函数来减少冲突呢？如果发生了冲突，我们该如何处理冲突，减少比较次数提高查找效率呢？

创建哈希表

这一课我们来学习如何创建哈希表。首先我们来定义哈希表结构体HashTable
接下来我们来定义两个变量，一个是char 类型的二维指针变量 elem, 用来存储前面问题里的用户名，还有一个是int 类型的变量 size, size 表示哈希表的容量。
接下来我们来实现结构体 HashTable 的初始化函数init ，函数只有一个HashTable 类型的参数h.

void init(HashTable *h) {
	
}

我们先把函数定义写好，稍后再来实现。
4. 我们在初始化函数里完成以下两个步骤：将哈希表 h 的 size 设置为 1000，表示哈希表的长度，然后给二维指针变量 elem 动态分配 size 个 char * 乐星的内存。
5. 接下来我们给每个元素动态分配 100 个char 类型的内存，之后赋上初值。
由于元素都是字符串，这里我们写个for 循环，用变量i 从 0 循环到不小于哈希表 h 的 size 时退出，把每个元素都赋为空。在后面哈希表的查找中，我们需要判断该位置上是否已有字符串。
6. 这样我们就把结构体HashTable 的初始化函数写完了，那么现在我们在主函数里创建一个HashTable 的指针变量hashtable, 并给它分配HashTable 类型的内存。然后调用初始化函数 init 完成对哈希表的初始化。
7. 同样，我们还需要构造一个函数 clear 来释放程序运行过程中占用的内存空间。
我们先在主函数之前把函数定义写好，函数没有返回值，参数为一个 HashTable 类型的指针变量h.
8. 在clear 函数中，我们同样使用for 循环，用变量 i 从 0 循环到不小于哈希表 h 的size 时退出来遍历所有元素。这一步我们先把循环的条件写好。
9. 在循环中，如果哈希表中某一个元素不为空，则使用free 将它释放。
10. 循环结束后，我们还要释放 h->elem 和指针 h 所指向的内存空间。
11. 最后，在程序结束后前吗，我们在主函数中调用 clear 函数。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 请在下面实现哈希表结构体 HashTable

typedef struct HashTable {
    char **elem;
    int  size;
} HashTable;


// 请在下面实现初始化函数 init
void init(HashTable  *h) {
    h->size = 1000;
    h->elem =  (char **)malloc(sizeof(char *) * h->size);
    for (int i = 0; i < h->size; i++) {
        h->elem[i] = NULL;
    }
}

void clear (HashTable *h) {
    //   变量i 从 0 循环到不小于哈希表h 的 size 时 退出遍历所有的元素 
    for(int i = 0; i < h->size; ++i) {
        if(h->elem[i] != NULL){
            free(h->elem[i]);
        }
    }
    free(h->elem);
    free(h);
}

int main() {
    // 创建一盒HashTable 的指针变量 hashtable  并分配HashTable  累心的内存，  
    
    HashTable  *hashtable = (HashTable *)malloc(sizeof(HashTable));
    init(hashtable);
    clear(hashtable);
    return 0;
}

哈希函数的构造方法

通过哈希表的阅读课，我们了解到哈希函数的优劣直接影响到哈希表查找效率，优秀的哈希函数可以减少冲突的发生。哈希表里的元素可以是不同类型的，也可以是不同规律的，所以不同情况下哈希函数的设计也是不同的。常见的哈希函数构造方法有哪些呢？

直接寻址法

即取关键字的值或者关键字的某个函数变换值，线性的映射到存储地址上。如果关键字的数量和跨度不是很大，直接寻址法是最简单最有效的构造方法了，并且还可以避免冲突。但是如果关键字的数量和跨度很大的话，这种方法就用不了了，例如有 n 个关键字，值最小的为 0，最大的为 \ $10^{10}$ ，这种情况下就不能用直接寻址法了，因为没有足够的空间可用来存储。

除留余数法

我们将关键字对整数 \ p p 取的余数直接做为存储地址，整数 p 一般取小于等于哈希表长度 \ size size 的最大质数，如果关键字不是整数，比如是一个字符串，可以先将其做个转换，然后再对 p 取余。选择优秀的 p 可以减少冲突的发生。
其他的构造方法还有分析数字法，随机数法等等。

设计哈希函数没有统一的方法，同一个哈希函数不一定能适用所有问题，其产生的影响也是不一样的。但哈希函数的设计又是至关重要的，那么我们该如何设计呢？一般来说，设计哈希函数时要达到两个要求：计算简单，计算复杂的哈希函数会增加查询的时间；关键字尽可能地均分到存储地址上，这样可以减少冲突。

构造哈希函数

这一课我们来学习构造哈希函数，通过之前的课程学习，我们了解到构造哈希函数的两个要求：计算方便快捷，映射的存储地址可能均匀。
这里我们的元素是字符串，我们先来看看经典的字符串哈希函数都有那些。
经典的字符串哈希函数有很多，例如BKDRHash、APHash、DJBHash, JSHash、RSHash等等。未来方便理解，我们先介绍一种简单的字符串哈希函数。
首先，我们来定义一个返回值为 int 类型的哈希函数 hash , 函数有两个参数, 一个是 HashTable 类型的指针变量h, 另一个参数是char 类型的数组value , 这咯我们定义好哈希函数 hash 即可，稍后再来实现。
接下来我们定义一个int 类型的变量code, 并赋初始值为0。变量code 用来记录字符串value 哈希值，也就是对应的存储位置。
接下来我们循环一遍字符串 value, 这里我们用size _t 类型的变量i 从 0 开始循环到不小于字符串时退出。
我们可以使用strlen 函数来求字符串长度。需要注意的是，这里的变量i 不能用 int 类型，而应该用 size_t 类型，因为字符串是char[] 类型，如果用int 会有警告。for 循环记得带上花括号。
接下来我们来计算 code .
我们知道有符号的字符范围是从 - 128 到 127 ，也就一共有 256 种。为了减少冲突，我们可以使用这种构造方法；先让当前的code 值乘以 256，然后加上
第 i 个字符的值，因为字符可能会出现负值，所以我们最后再加上128. 为了防止数据过大导致的数据溢出，我们把相加的结果再对哈希表的长度size 取余，这样我们就得到了新的哈希值 code.
这样的构造方法可以减少冲突的发生，但这不是唯一的构造方法。
这样我们计算出了字符串 value 的哈希值，找到了字符串 value 对应的存储位置。在函数最后，我们把结果 code 做为返回值返回。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct HashTable {
   char **elem;
   int size;
} HashTable;

void init(HashTable *h);
int hash(HashTable *h, char value[]);

void init(HashTable *h) {
   h->size = 2000;
   h->elem = (char **)malloc(sizeof(char *) * h->size);
   for (int i = 0; i < h->size; i++) {
       h->elem[i] = NULL;
   }
}

// 请在下面实现构造哈希函数函数 hash
// 接下来 我们来定义一个 int 类型的变量 code,  并赋初始值为 0. 变量code  用来记录字符串 value 的哈希值，也就是对应的存储位置。

int hash(HashTable *h, char value[]) {
   int code  = 0;
   //  接下来我们循环一遍 字符串 value,  这里 我们用 size_t  类型的变量 i  从 0 开始 循环 到不小于字符串 长度时 退出.
   // 
   for(size_t  i = 0;  i < strlen(value); i++) {
       code = (code * 256 + value[i] + 128)  % h ->size;
   }
   
   return code;
}

void clear(HashTable *h) {
   for (int i = 0; i < h->size; ++i) {
       if (h->elem[i] != NULL) {
           free(h->elem[i]);
       }
   }
   free(h->elem);
   free(h);
}

int main() {
   HashTable *hashtable = (HashTable*)malloc(sizeof(HashTable));
   init(hashtable);
   clear(hashtable);
   return 0;
}

处理冲突的方法

通过前面的课程，我们了解到可以通过构造优秀的哈希函数来减少冲突，但是一般情况下冲突是不可避免的，那么我们该怎么处理冲突呢？前面的课程提到了解决冲突的方法也会影响哈希表的查找效率，因此选择一个优秀的方法来处理冲突显得尤为重要，那么常见的处理冲突的方法有哪些呢？

开放地址法 ，如果发生冲突，那么就使用某种策略寻找下一存储地址，直到找到一个不冲突的地址或者找到关键字，否则一直按这种策略继续寻找。如果冲突次数达到了上限则终止程序，表示关键字不存在哈希表里。一般常见的策略有这么几种：

1. 线性探测法，如果当前的冲突位置为 $d$，那么接下来几个探测地址为 $d + 1$，$d + 2$，$d + 3$ 等，也就是从冲突地址往后面一个一个探测；
2. 线性补偿探测法，它形成的探测地址为 $d + m$，$d + 2 \times m$，$d + 3 \times m$ 等，与线性探测法不同，这里的查找单位不是 $1$，而是 $m$，为了能遍历到哈希表里所有位置，我们设置 $m$ 和表长 $size$ 互质；
3. 随机探测法，这种方法和前两种方法类似，这里的查找单位不是一个固定值，而是一个随机序列。
4. 二次探测法，它形成的探测地址为 $d + 1^2$，$d - 1^2$，$d + 2^2$，$d - 2^2$ 等，这种方法在冲突位置左右跳跃着寻找探测地址。
     开放地址法计算简单快捷，处理起来方便，但是也存在不少缺点。线性探测法容易形成“堆聚”的情况，即很多记录就连在一块，而且一旦形成“堆聚”，记录会越聚越多。另外，开放地址法都有一个缺点，删除操作显得十分复杂，我们不能直接删除关键字所在的记录，否则在查找删除位置后面的元素时，可能会出现找不到的情况，因为删除位置上已经成了空地址，查找到这里时会终止查找。

链地址法 ，该方法将所有哈希地址相同的结点构成一个单链表，单链表的头结点存在哈希数组里。链地址法常出现在经常插入和删除的情况下。
相比开放地址法，链地址法有以下优点：不会出现“堆聚”现象，哈希地址不同的关键字不会发生冲突；不需要重建哈希表，在开放地址法中，如果哈希表里存满关键字了就需要扩充哈希表然后重建哈希表，而在链地址法里，因为结点都是动态申请的，所以不会出现哈希表里存满关键字的情况；相比开放地址法，关键字删除更方便，只需要找到指定结点，删除该结点即可。

开放地址法和链地址法各有千秋，适用于不同情况。当关键字规模少的时候，开放地址法比链地址法更节省空间，因为用链地址法可能会存在哈希数组出现大量空地址的情况，而在关键字规模大的情况下，链地址法就比开放地址法更节省空间，链表产生的指针域可以忽略不计，关键字多，哈希数组里产生的空地址就少了。

冲突的解决

我们知道在哈希表中，冲突是不可避免的，通过前面的学习我们了解到了几个处理冲突的方法。在接下来的课程里，我们学习在代码中实现开放地址法，然后向哈希表中插入一些元素。在此之前，我们还是先了解一下相关操作的算法流程。
通过前面的学习，我们了解了开放地址法有线性探测法、线性补偿探测法、随机探测法、二次探测法等等策略，他们的区别在于发生冲突时寻找下一个地址的方法不同。我们将实现的是用线性探测法来解决冲突。
线性探测法查找哈希冲突的算法流程如下：

1. 用哈希函数找到字符串 S 的初始位置，初始化冲突次数。
2. 从当前位置往后查找，找到第一个未发生冲突的位置 K（当前位置上如果存储的字符串不是 S 即视为发生冲突）。查找过程中记录发生冲突的次数 T，如果 T 大于等于表长，则结束算法，表示查找失败。
3. 如果位置 K 上的元素就是所查找的字符串，表示查找成功，否则表示查找失败。

现在我们已经设计了一个线性探测法来查找冲突，我们可以在元素插入哈希表中时调用这个方法去获知冲突情况。
程序执行时，如果当前的元素已经存在哈希表中了，就直接返回一个值结束这次插入操作。除此之外，我们规定，当冲突次数小于表长的一半时，我们就可以把字符串插入到哈希表中。而如果发生冲突次数大于表长的一半时，就需要调用重建函数去重建哈希表了，因为我们认为哈希表已经发生了“堆聚”现象，这种情况下我们要扩大哈希表的容量，提高查找和插入的效率。
同学们可能还记得我们在顺序表中曾经使用过的扩容操作，事实上，哈希表的重建操作和顺序表的扩容很类似。
哈希表重建操作的算法流程如下：

1. 开辟一段和当前哈希表等大的临时存储空间。
2. 将原哈希表里的关键字一一复制到临时数组里。
3. 申请一个大小是现在两倍的新的存储空间，释放原空间。
4. 将新空间里的存储地址初始化。
5. 将关键字从临时数组复制到新的空间，释放临时空间。

这样我们就完成了查找冲突，插入关键字，重建哈希表这一系列的操作，真正实现了一个完整的哈希表。

开放地址法

为了帮助同学理解哈希冲突，这一课我们来开放地址发的线性探测法解决哈希冲突，也就是哈希的查到函数。
一开始我们先在主函数前定义下哈希查找函数search , search 是一个返回值为 int 类型，分别有以下四个参数的函数；第一个是HashTable 类型的指针参数h; 第二个参数是char 数组 value; 第三个是 int 类型的指针参数 pos; 第四个是int 类型的指针参数 times. 后两个是因为我们需要记录函数执行结束后pos 和 times 的值。
value 表示要查找的字符串，pos 表示哈希表里可以插入 value 的位置， times 记录冲突的次数。z
接下来我们就一步步写全search 函数。首先我们要给指针变量pos 和 times 赋个初始值。pos 记录的是待插入的位置，那么初始值就等value 的哈希值，我们前面已经把哈希函数 hash 写好了，这里就可以调用 hash 求得哈希值。times 记录得是冲突次数，那么初始没有发生冲突，结果为0.
接下来我们就要循环查找 value 可以插入得位置
我们来分析下，考虑这几种情况: 如果当前位置pos 为空地址则表示我们可以把value 插入到这里；如果pos 上已有关键字，并且关键字就是value, 说明value 已经插入到哈希表里了；如果pos 上已有关键字，并且关键字不是value, 说明发生冲突了需要找一下地址。
我们可以看到前两种情况都是终止条件，第三种情况是循环条件，所以我们可以用第三种情况下写while 循环，循环需要满足两个条件；当前位置上不为空，且不能和关键字value 相等。
如果当前位置上已经有元素，并且又不是关键字value , 则说明已经发生了冲突，那么首先我们让记录冲突次数得指针变量 times 加 1. 这一步我们只要完成这样一个操作。
发生冲突后，我们需要找一下存储地址，首先我们要满足冲突次数 *times 要小于哈希表 h 的长度 size, 否则我们认为哈希表已经填满关键字了，没有空余的地址可以i存储。这一步我们只要把条件写好即可，if 语句记得协商花括号。
当满足存储条件后，我们就用开发地址法的线性探测法来找一个地址。线性探测法就是从当前位置 *pos 开始，一个一个往后找。那么 *pos 就等于 *ops + 1, 加完后记得对哈希表h 的 size 取余，因此结果可能会超出数组长度，如果超了就该从数组第 0 位开始继续寻找。
这样我们就让 pos 等于其下一个地址了。现在我们来考虑一个问题，如果time 不小于哈希表 h 的size 怎么办》也就是说哈希表数组里已经没有多余的存储地址栏，那么就返回0 来结束函数，表示查找失败。
这里我们跟着 if 条件写上 else 即可，还是一样，记得写上花括号。
这样我们就把 whle 循环写完了，也就是我们已经找到了value 可以插入的位置或者我们已经在哈希表里找到了 value.
如果当前位置不为空，则关键字是value, 那我们返回1，表示我们已经找到value.
我们刚刚已经写了如果当前位置的关键字是 value 的情况，如果不是的话，那么就返回0，表示哈希表里没有关键字value, 而当前位置上正是 value 可以插入的位置。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct HashTable {
    char **elem;
    int size;
} HashTable;

void init(HashTable *h);
int hash(HashTable *h, char value[]);
int search(HashTable *h, char value[], int *pos, int *times);

void init(HashTable *h) {
    h->size = 2000;
    h->elem = (char **)malloc(sizeof(char *) * h->size);
    for (int i = 0; i < h->size; i++) {
        h->elem[i] = NULL;
    }
}

int hash(HashTable *h, char value[]) {
    int code = 0;
    for (size_t i = 0; i < strlen(value); i++) {
        code = (code * 256 + value[i] + 128) % h->size;
    }
    return code;
}

// 请在下面实现查找函数 search
int search(HashTable *h, char value[], int *pos, int  *times){
    //  给指针变量pos 和 times  赋个初始值 
    *pos =  hash(h, value);
    *times = 0;
    //  循环条件 需要满足两个条件， 但钱位置上不为空， 且不能和关键字value   相等 
    while (h->elem[*pos] != NULL && strcmp(h->elem[*pos], value)  != 0) {
         // 指针变量加 1 的情况 
        (*times)++;
        if (*times < h->size) {
            
            *pos  = (*pos + 1) % h->size;
            
        } else {
            
            return 0;
        }
    
        
    }
    
     //  如果当前位置不为空， 且关键字是value, 则我们就返回1， 表示我们已经找到value了。
    if(h->elem[*pos] != NULL && strcmp(h->elem[*pos], value) == 0) {
            return 1;
     } else {
        return 0;
    }
    
}


void clear(HashTable *h) {
    for (int i = 0; i < h->size; ++i) {
        if (h->elem[i] != NULL) {
            free(h->elem[i]);
        }
    }
    free(h->elem);
    free(h);
}

int main() {
    HashTable *hashtable = (HashTable*)malloc(sizeof(HashTable));
    init(hashtable);
    clear(hashtable);
    return 0;
}