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。

相关文章

SpringBoot集成redisson实现延时队列教程

SpringBoot集成redisson实现延时队列教程

《SpringBoot集成redisson实现延时队列教程》文章介绍了使用Redisson实现延迟队列的完整步骤,包括依赖导入、Redis配置、工具类封装、业务枚举定义、执行器实现、Bean创建、消费... 目录1、先给项目导入Redisson依赖2、配置redis3、创建 RedissonConfig 配
阅读更多...
Python的Darts库实现时间序列预测

Python的Darts库实现时间序列预测

《Python的Darts库实现时间序列预测》Darts一个集统计、机器学习与深度学习模型于一体的Python时间序列预测库,本文主要介绍了Python的Darts库实现时间序列预测,感兴趣的可以了解... 目录目录一、什么是 Darts？二、安装与基本配置安装 Darts导入基础模块三、时间序列数据结构与
阅读更多...
Python使用FastAPI实现大文件分片上传与断点续传功能

Python使用FastAPI实现大文件分片上传与断点续传功能

《Python使用FastAPI实现大文件分片上传与断点续传功能》大文件直传常遇到超时、网络抖动失败、失败后只能重传的问题,分片上传+断点续传可以把大文件拆成若干小块逐个上传,并在中断后从已完成分片继... 目录一、接口设计二、服务端实现（FastAPI）2.1 运行环境2.2 目录结构建议2.3 serv
阅读更多...
C#实现千万数据秒级导入的代码

C#实现千万数据秒级导入的代码

《C#实现千万数据秒级导入的代码》在实际开发中excel导入很常见,现代社会中很容易遇到大数据处理业务,所以本文我就给大家分享一下千万数据秒级导入怎么实现,文中有详细的代码示例供大家参考,需要的朋友可... 目录前言一、数据存储二、处理逻辑优化前代码处理逻辑优化后的代码总结前言在实际开发中excel导入很
阅读更多...
SpringBoot+RustFS 实现文件切片极速上传的实例代码

SpringBoot+RustFS 实现文件切片极速上传的实例代码

《SpringBoot+RustFS实现文件切片极速上传的实例代码》本文介绍利用SpringBoot和RustFS构建高性能文件切片上传系统,实现大文件秒传、断点续传和分片上传等功能,具有一定的参考... 目录一、为什么选择 RustFS + SpringBoot？二、环境准备与部署2.1 安装 RustF
阅读更多...
Nginx部署HTTP/3的实现步骤

Nginx部署HTTP/3的实现步骤

《Nginx部署HTTP/3的实现步骤》本文介绍了在Nginx中部署HTTP/3的详细步骤,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录前提条件第一步：安装必要的依赖库第二步：获取并构建 BoringSSL第三步：获取 Nginx
阅读更多...
MyBatis Plus实现时间字段自动填充的完整方案

MyBatis Plus实现时间字段自动填充的完整方案

《MyBatisPlus实现时间字段自动填充的完整方案》在日常开发中,我们经常需要记录数据的创建时间和更新时间,传统的做法是在每次插入或更新操作时手动设置这些时间字段,这种方式不仅繁琐,还容易遗漏,... 目录前言解决目标技术栈实现步骤1. 实体类注解配置2. 创建元数据处理器3. 服务层代码优化填充机制详
阅读更多...
Python实现Excel批量样式修改器(附完整代码)

Python实现Excel批量样式修改器(附完整代码)

《Python实现Excel批量样式修改器(附完整代码)》这篇文章主要为大家详细介绍了如何使用Python实现一个Excel批量样式修改器,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一... 目录前言功能特性核心功能界面特性系统要求安装说明使用指南基本操作流程高级功能技术实现核心技术栈关键函
阅读更多...
Java实现字节字符转bcd编码

Java实现字节字符转bcd编码

《Java实现字节字符转bcd编码》BCD是一种将十进制数字编码为二进制的表示方式,常用于数字显示和存储,本文将介绍如何在Java中实现字节字符转BCD码的过程,需要的小伙伴可以了解下... 目录前言BCD码是什么Java实现字节转bcd编码方法补充总结前言BCD码（Binary-Coded Decima
阅读更多...
SpringBoot全局域名替换的实现

SpringBoot全局域名替换的实现

《SpringBoot全局域名替换的实现》本文主要介绍了SpringBoot全局域名替换的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录 项目结构⚙️ 配置文件application.yml️ 配置类AppProperties.Ja
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2