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。

相关文章

C语言小项目实战之通讯录功能

C语言小项目实战之通讯录功能

《C语言小项目实战之通讯录功能》：本文主要介绍如何设计和实现一个简单的通讯录管理系统,包括联系人信息的存储、增加、删除、查找、修改和排序等功能,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录功能介绍：添加联系人模块显示联系人模块删除联系人模块查找联系人模块修改联系人模块排序联系人模块源代码如下
阅读更多...
Java中使用Java Mail实现邮件服务功能示例

Java中使用Java Mail实现邮件服务功能示例

《Java中使用JavaMail实现邮件服务功能示例》：本文主要介绍Java中使用JavaMail实现邮件服务功能的相关资料,文章还提供了一个发送邮件的示例代码,包括创建参数类、邮件类和执行结... 目录前言一、历史背景二编程、pom依赖三、API说明（一）Session （会话）（二）Message编程客
阅读更多...
Java中List转Map的几种具体实现方式和特点

Java中List转Map的几种具体实现方式和特点

《Java中List转Map的几种具体实现方式和特点》：本文主要介绍几种常用的List转Map的方式,包括使用for循环遍历、Java8StreamAPI、ApacheCommonsCollect... 目录前言1、使用for循环遍历：2、Java8 Stream API：3、Apache Commons
阅读更多...
C#提取PDF表单数据的实现流程

C#提取PDF表单数据的实现流程

《C#提取PDF表单数据的实现流程》PDF表单是一种常见的数据收集工具,广泛应用于调查问卷、业务合同等场景,凭借出色的跨平台兼容性和标准化特点,PDF表单在各行各业中得到了广泛应用,本文将探讨如何使用... 目录引言使用工具C# 提取多个PDF表单域的数据C# 提取特定PDF表单域的数据引言PDF表单是一
阅读更多...
使用Python实现高效的端口扫描器

使用Python实现高效的端口扫描器

《使用Python实现高效的端口扫描器》在网络安全领域,端口扫描是一项基本而重要的技能,通过端口扫描,可以发现目标主机上开放的服务和端口,这对于安全评估、渗透测试等有着不可忽视的作用,本文将介绍如何使... 目录1. 端口扫描的基本原理2. 使用python实现端口扫描2.1 安装必要的库2.2 编写端口扫
阅读更多...
PyCharm接入DeepSeek实现AI编程的操作流程

PyCharm接入DeepSeek实现AI编程的操作流程

《PyCharm接入DeepSeek实现AI编程的操作流程》DeepSeek是一家专注于人工智能技术研发的公司,致力于开发高性能、低成本的AI模型,接下来,我们把DeepSeek接入到PyCharm中... 目录引言效果演示创建API key在PyCharm中下载Continue插件配置Continue引言
阅读更多...
MySQL分表自动化创建的实现方案

MySQL分表自动化创建的实现方案

《MySQL分表自动化创建的实现方案》在数据库应用场景中,随着数据量的不断增长,单表存储数据可能会面临性能瓶颈,例如查询、插入、更新等操作的效率会逐渐降低,分表是一种有效的优化策略,它将数据分散存储在... 目录一、项目目的二、实现过程（一）mysql 事件调度器结合存储过程方式1. 开启事件调度器2. 创
阅读更多...
使用Python实现操作mongodb详解

使用Python实现操作mongodb详解

《使用Python实现操作mongodb详解》这篇文章主要为大家详细介绍了使用Python实现操作mongodb的相关知识,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、示例二、常用指令三、遇到的问题一、示例from pymongo import MongoClientf
阅读更多...
SQL Server使用SELECT INTO实现表备份的代码示例

SQL Server使用SELECT INTO实现表备份的代码示例

《SQLServer使用SELECTINTO实现表备份的代码示例》在数据库管理过程中,有时我们需要对表进行备份,以防数据丢失或修改错误,在SQLServer中,可以使用SELECTINT... 在数据库管理过程中，有时我们需要对表进行备份，以防数据丢失或修改错误。在 SQL Server 中，可以使用 SE
阅读更多...
基于Go语言实现一个压测工具

基于Go语言实现一个压测工具

《基于Go语言实现一个压测工具》这篇文章主要为大家详细介绍了基于Go语言实现一个简单的压测工具,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录整体架构通用数据处理模块Http请求响应数据处理Curl参数解析处理客户端模块Http客户端处理Grpc客户端处理Websocket客户端
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2