7.3 哈希表与布隆过滤器（入门）—— C语言实现

2024-04-20 23:12
文章标签 语言 实现 入门 哈希 过滤器 布隆 表与 7.3

本文主要是介绍7.3 哈希表与布隆过滤器（入门）—— C语言实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 前言
  • 一、哈希表
    • 1.1 哈希函数
    • 1.2 哈希冲突
  • 二、布隆过滤器
      • 布隆过滤器的工作原理：
      • 存储空间与元素数量的关系：
      • 结论：
  • 三、哈希表的代码演示
    • 3.1 哈希表扩容
  • 四、总结
  • 参考文献

前言

本章内容参考海贼宝藏胡船长的数据结构与算法中的第七章——查找算法，侵权删。

哈希表的优点：

  1. 高效的操作时间：在最佳情况下，哈希表的查找、插入和删除操作的时间复杂度为 O(1)。这是因为哈希表通过哈希函数直接计算出数据应存储在哪个位置，从而快速定位数据。
  2. 直接访问：不需要像在树结构中那样进行多次比较或遍历。

一、哈希表

哈希表利用了数组的特性。当我们给出数组下标的时候，就能返回下标所对应的元素值，时间复杂度是O(1)，这个特性也很类似python的字典。说白了就是元素和下标（字典中的键值）完成映射。这个映射关系就叫做哈希函数。

1.1 哈希函数

所谓哈希本质上是高维空间到低维空间的一种映射（不一定是一一映射，可能会出现哈希冲突），映射规则就是哈希函数。

哈希函数（也就是映射规则）是根据具体场景去设计的，不是固定的。但有优化的空间：理想情况下，哈希函数应该均匀分布，这意味着每个可能的索引值都有相等的概率被映射到，以减少冲突。
在这里插入图片描述

1.2 哈希冲突

非一一映射

由于哈希表的大小通常远小于可能的键的数量，多个不同的键可能会被哈希到同一个索引值，这就造成了哈希冲突。
在这里插入图片描述在这里插入图片描述怎么处理哈希冲突呢？
在这里插入图片描述1. 开放定址法：在开放地址法中，所有的元素都存储在哈希表数组中。当发生冲突时，使用探测序列（例如线性探测、二次探测或双重哈希等）找到下一个空闲的槽位。
2. 再哈希法（双重哈希）：这是开放地址法的一种特殊情况，使用两个哈希函数来减少冲突。这种情况不常用，因为哈希函数比较难去创造。
3. 建立公共溢出区：额外建立缓冲区，把发生冲突的数据放入到缓冲区。缓冲区可能是其他数据结构，例如堆，二叉排序树，红黑树等。把它理解成为另外的用于查找的数据结构。（该缓存区的查找效率可能没有哈希表的查找效率高）。
4. 链式地址法：在这种方法中，哈希表的每个桶或槽位不仅存储单个元素，而是存储一个链表。当多个元素哈希到同一个桶时，它们会被添加到该桶的链表中。查找、插入和删除操作需要遍历链表以找到目标元素。
在这里插入图片描述

补充：每个位置存储链表的效率其实并不高，实际上在实际工程中，每个位置上实现一个红黑树！！！

哈希表没有具体设计规则可言（哈希函数没有标准答案），冲突处理方式也不太同意，他给开发者极大的发挥空间。

二、布隆过滤器

在这里插入图片描述举个使用布隆过滤器的应用场景的例子——搜索引擎的爬虫：
搜索引擎在收录网页信息的时候，为了避免重复爬取，它会把爬取过的地址记录下来。所以爬虫在每次爬取的时候，它都会判断一下，当前爬取的网页是否爬取过。记录地址需要一种数据结构，如果用传统哈希表，那么数以千计的网址使得该记录的存储空间会变得巨大。

布隆过滤器的存储空间实际上与它设计时预期要存储的元素数量有关，但这种关系并不是直接存储每个元素的细节，而是通过一组固定大小的位数组来实现，这些位用于代表集合中元素的可能存在。布隆过滤器提供了一种非常空间效率高的方法来测试一个元素是否属于一个集合，但这种方法允许存在一定的错误率（误判率，或者说概率性），即它能判断该元素大概率出现过，但它判断一个元素没有出现过的概率是1（那就真没出现过）。

布隆过滤器的工作原理：

  1. 位数组：布隆过滤器背后的数据结构是一个大的位数组，通常初始化时所有位都是0。
  2. 多个哈希函数：使用多个独立的哈希函数，每个函数都将元素映射到位数组中的一个位置。
  3. 添加元素：将某个元素添加到布隆过滤器时，该元素被每一个哈希函数映射，相应的位数组中的位被设置为1。
  4. 元素查询：查询一个元素是否存在于集合中时，使用相同的哈希函数对元素进行映射，然后检查所有对应的位是否为1。如果所有位都是1，那么元素可能存在于集合中；如果任何一位是0，则元素绝对不在集合中。

在这里插入图片描述
在这里插入图片描述在这里插入图片描述

存储空间与元素数量的关系：

  • 设计参数：布隆过滤器的大小（即位数组的长度）和使用的哈希函数数量直接影响其性能，包括误判率和查询速度。这些参数通常在创建过滤器时根据预期要处理的元素数量和可接受的误判率来选择。
  • 空间效率：布隆过滤器不存储元素本身，只记录元素可能存在的信息。这使得它比存储实际元素的传统数据结构（如哈希表或集合）更加空间效率。
  • 误判率：增加位数组的大小和使用更多的哈希函数可以降低误判率，但这会增加空间使用和计算开销。适当选择这些参数是设计布隆过滤器时的一个关键考虑。

结论：

虽然布隆过滤器的存储空间不直接存储每个元素的详细信息，但其设计和效能确实依赖于预期要处理的元素数量和可接受的误判率。布隆过滤器是一种权衡存储空间和准确性的高效方法，特别适用于那些可以容忍一定误报率的应用场景，如网络数据处理、数据库查询优化等。

三、哈希表的代码演示

冲突处理方式选择拉链法
哈希表中存储的数据类型是字符串

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>typedef struct Node{char *s;struct Node *next;
} Node;typedef struct HashTable{Node *data; //哈希表底层有个数组空间 int cnt, size;
} HashTable;//节点Node初始化方法
Node *getNewNode(const char *s){Node *p = (Node *)malloc(sizeof(Node));p->s = strdup(s);p->next = NULL;return p;
}//初始化哈希表
HashTable *getNewHashTable(int n){HashTable *h = (HashTable *)malloc(sizeof(HashTable));h->data = (Node *)malloc(sizeof(Node) * n);h->size = n;h->cnt = 0;return h;
}//哈希函数：经典的字符串哈希算法
int hash_func(const char *s){int seed = 131, h = 0;for (int i = 0; s[i]; i++){h = h * seed + s[i];}return h & 0x7fffffff; //这里去掉最高位（符号位）强制变成正数
}bool find(HashTable *h, const char *s){int hcode = hash_func(s), ind = hcode % h->size;Node *p = h->data[ind].next;while (p){if (strcmp(p->s, s) == 0) return true;p = p->next;}return false;
}bool insert(HashTable *h, const char *s){int hcode = hash_func(s), ind = hcode % h->size; //哈希值转换成为数组下标//放在链表的头部，效率更高：链表头插法,这里采用虚拟头节点！！！Node *p = getNewNode(s);p->next = h->data[ind].next;h->data[ind].next = p;h->cnt += 1;return true;
}void clearNode(Node *p){if (p == NULL) return;if (p->s)  free(p->s);free(p);return;
}void clearHashTable(HashTable *h){if (h == NULL) return;for (int i = 0; i < h->size; i++){Node *p = h->data[i].next, *q;while (p){q = p->next;clearNode(p);p = q;}}free(h->data);free(h);return;
}void output(HashTable *h){printf("\n\nHash Table(%d / %d) : \n", h->cnt, h->size);for (int i = 0; i < h->size; i++){printf("%d : ", i);Node *p = h->data[i].next;while (p){printf("%s -> ", p->s);p = p->next;}printf("\n");}return;
}int main(){srand(time(0));char s[100];#define MAX_N 2HashTable *h = getNewHashTable(MAX_N);while (~scanf("%s", s)){if (strcmp(s, "end") == 0) break;insert(h, s);}output(h);while (~scanf("%s", s)){printf("find(%s) = %d\n", s, find(h, s));}#undef MAX_Nreturn 0;
}

输出结果：

在这里插入图片描述

3.1 哈希表扩容

扩容操作：初始化一个大小为原来哈希表大小的两倍，再将原来哈希表的数据通通插入到新的哈希表中来。这样就完成了扩容。

思考：这样的扩容操作，会把原来小的数据全插入到大的中，这会不会太慢了？？？

均摊时间复杂度
最终哈希表大小为n，意味着，之前是 n 2 \frac{n}{2} 2n​，之前的之前是 n 4 \frac{n}{4} 4n​。一次类推，把这个大的哈希表整个生命周期的时间复杂度加在一起：
n 2 + n 4 + n 8 + . . . . . . ≈ n \frac{n}{2} + \frac{n}{4} + \frac{n}{8} + ... ... \approx n 2n​+4n​+8n​+......≈n
所以上述算式代表的是一个大小为n的哈希表历史上所有的由于扩容产生的操作加在一起也是n，平摊到每一个元素上也是O(1)的量级
均摊时间复杂度：不要看某一次的操作耗时，其实应该观察该数据结构整个声明周期耗时多少。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>#define swap(a, b){ \__typeof(a) __c = a; \a = b, b = __c;  \
}typedef struct Node{char *s;struct Node *next;
} Node;typedef struct HashTable{Node *data; //哈希表底层有个数组空间 int cnt, size;
} HashTable;//节点Node初始化方法
Node *getNewNode(const char *s){Node *p = (Node *)malloc(sizeof(Node));p->s = strdup(s);p->next = NULL;return p;
}//初始化哈希表
HashTable *getNewHashTable(int n){HashTable *h = (HashTable *)malloc(sizeof(HashTable));h->data = (Node *)malloc(sizeof(Node) * n);h->size = n;h->cnt = 0;return h;
}//哈希函数：经典的字符串哈希算法
int hash_func(const char *s){int seed = 131, h = 0;for (int i = 0; s[i]; i++){h = h * seed + s[i];}return h & 0x7fffffff; //这里去掉最高位（符号位）强制变成正数
}bool find(HashTable *h, const char *s){int hcode = hash_func(s), ind = hcode % h->size;Node *p = h->data[ind].next;while (p){if (strcmp(p->s, s) == 0) return true;p = p->next;}return false;
}void swapHashTable(HashTable *h1, HashTable *h2){swap(h1->data, h2->data);swap(h1->cnt, h2->cnt);swap(h1->size, h2->size);return;
}bool insert(HashTable *, const char *);
void clearHashTable(HashTable *);void expand(HashTable *h){printf("expand Hash Table %d -> %d\n", h->size, h->size * 2);HashTable *new_h = getNewHashTable(h->size * 2); //新哈希表的大小是原哈希表的两倍for (int i = 0; i < h->size; i++){Node *p = h->data[i].next;while (p){insert(new_h, p->s);p = p->next;}} //至此，将原来哈希表中所有的元素插入到了新哈希表中swapHashTable(h, new_h);clearHashTable(new_h);return;
}bool insert(HashTable *h, const char *s){if (h->cnt >= h->size * 2){expand(h);}int hcode = hash_func(s), ind = hcode % h->size; //哈希值转换成为数组下标//放在链表的头部，效率更高：链表头插法,这里采用虚拟头节点！！！Node *p = getNewNode(s);p->next = h->data[ind].next;h->data[ind].next = p;h->cnt += 1;return true;
}//实现见上一段代码
void clearNode(Node *p);
void clearHashTable(HashTable *h);
void output(HashTable *h);// 测试代码用上一个例子的

输出结果：
在这里插入图片描述
注意：代码中用swap(h1->data, h2->data)交换两个用malloc函数申请的内存地址，就是将地址交换，而不是将地址里面的数据进行交换！！！

四、总结

  1. 哈希表，哈希冲突及冲突处理
  2. 简单介绍了布隆过滤器

参考文献

  1. 数据结构与算法中的第七章——查找算法

这篇关于7.3 哈希表与布隆过滤器（入门）—— C语言实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/921573。

相关文章

Vue中动态权限到按钮的完整实现方案详解

Vue中动态权限到按钮的完整实现方案详解

《Vue中动态权限到按钮的完整实现方案详解》这篇文章主要为大家详细介绍了Vue如何在现有方案的基础上加入对路由的增、删、改、查权限控制,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、数据库设计扩展1.1 修改路由表（routes）1.2 修改角色与路由权限表（role_routes）二、后端接口设计
阅读更多...
C#集成DeepSeek模型实现AI私有化的流程步骤(本地部署与API调用教程)

C#集成DeepSeek模型实现AI私有化的流程步骤(本地部署与API调用教程)

《C#集成DeepSeek模型实现AI私有化的流程步骤(本地部署与API调用教程)》本文主要介绍了C#集成DeepSeek模型实现AI私有化的方法,包括搭建基础环境,如安装Ollama和下载DeepS... 目录前言搭建基础环境1、安装 Ollama2、下载 DeepSeek R1 模型客户端 ChatBo
阅读更多...
Qt实现发送HTTP请求的示例详解

Qt实现发送HTTP请求的示例详解

《Qt实现发送HTTP请求的示例详解》这篇文章主要为大家详细介绍了如何通过Qt实现发送HTTP请求,文中的示例代码讲解详细,具有一定的借鉴价值,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1、添加network模块2、包含改头文件3、创建网络访问管理器4、创建接口5、创建网络请求对象6、创建一个回复对
阅读更多...
C++实现回文串判断的两种高效方法

C++实现回文串判断的两种高效方法

《C++实现回文串判断的两种高效方法》文章介绍了两种判断回文串的方法：解法一通过创建新字符串来处理,解法二在原字符串上直接筛选判断,两种方法都使用了双指针法,文中通过代码示例讲解的非常详细,需要的朋友... 目录一、问题描述示例二、解法一：将字母数字连接到新的 string思路代码实现代码解释复杂度分析三、
阅读更多...
grom设置全局日志实现执行并打印sql语句

grom设置全局日志实现执行并打印sql语句

《grom设置全局日志实现执行并打印sql语句》本文主要介绍了grom设置全局日志实现执行并打印sql语句,包括设置日志级别、实现自定义Logger接口以及如何使用GORM的默认logger,通过这些... 目录gorm中的自定义日志gorm中日志的其他操作日志级别Debug自定义 Loggergorm中的
阅读更多...
Spring Boot整合消息队列RabbitMQ的实现示例

Spring Boot整合消息队列RabbitMQ的实现示例

《SpringBoot整合消息队列RabbitMQ的实现示例》本文主要介绍了SpringBoot整合消息队列RabbitMQ的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的... 目录RabbitMQ 简介与安装1. RabbitMQ 简介2. RabbitMQ 安装Spring
阅读更多...
Gin框架中的GET和POST表单处理的实现

Gin框架中的GET和POST表单处理的实现

《Gin框架中的GET和POST表单处理的实现》Gin框架提供了简单而强大的机制来处理GET和POST表单提交的数据,通过c.Query、c.PostForm、c.Bind和c.Request.For... 目录一、GET表单处理二、POST表单处理1. 使用c.PostForm获取表单字段：2. 绑定到结
阅读更多...
springMVC返回Http响应的实现

springMVC返回Http响应的实现

《springMVC返回Http响应的实现》本文主要介绍了在SpringBoot中使用@Controller、@ResponseBody和@RestController注解进行HTTP响应返回的方法,... 目录一、返回页面二、@Controller和@ResponseBody与RestController
阅读更多...
nginx中重定向的实现

nginx中重定向的实现

《nginx中重定向的实现》本文主要介绍了Nginx中location匹配和rewrite重定向的规则与应用,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下... 目录一、location1、 location匹配2、 location匹配的分类2.1 精确匹配2
阅读更多...
Nginx之upstream被动式重试机制的实现

Nginx之upstream被动式重试机制的实现

《Nginx之upstream被动式重试机制的实现》本文主要介绍了Nginx之upstream被动式重试机制的实现,可以通过proxy_next_upstream来自定义配置,具有一定的参考价值,感兴... 目录默认错误选择定义错误指令配置proxy_next_upstreamproxy_next_upst
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2