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。

相关文章

golang版本升级如何实现

golang版本升级如何实现

《golang版本升级如何实现》：本文主要介绍golang版本升级如何实现问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录golanwww.chinasem.cng版本升级linux上golang版本升级删除golang旧版本安装golang最新版本总结gola
阅读更多...
Go语言中make和new的区别及说明

Go语言中make和new的区别及说明

《Go语言中make和new的区别及说明》：本文主要介绍Go语言中make和new的区别及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1 概述2 new 函数2.1 功能2.2 语法2.3 初始化案例3 make 函数3.1 功能3.2 语法3.3 初始化
阅读更多...
SpringBoot中SM2公钥加密、私钥解密的实现示例详解

SpringBoot中SM2公钥加密、私钥解密的实现示例详解

《SpringBoot中SM2公钥加密、私钥解密的实现示例详解》本文介绍了如何在SpringBoot项目中实现SM2公钥加密和私钥解密的功能,通过使用Hutool库和BouncyCastle依赖,简化... 目录一、前言1、加密信息(示例)2、加密结果(示例)二、实现代码1、yml文件配置2、创建SM2工具
阅读更多...
Mysql实现范围分区表(新增、删除、重组、查看)

Mysql实现范围分区表(新增、删除、重组、查看)

《Mysql实现范围分区表(新增、删除、重组、查看)》MySQL分区表的四种类型（范围、哈希、列表、键值）,主要介绍了范围分区的创建、查询、添加、删除及重组织操作,具有一定的参考价值,感兴趣的可以了解... 目录一、mysql分区表分类二、范围分区（Range Partitioning1、新建分区表：2、分
阅读更多...
MySQL 定时新增分区的实现示例

MySQL 定时新增分区的实现示例

《MySQL定时新增分区的实现示例》本文主要介绍了通过存储过程和定时任务实现MySQL分区的自动创建,解决大数据量下手动维护的繁琐问题,具有一定的参考价值,感兴趣的可以了解一下... mysql创建好分区之后，有时候会需要自动创建分区。比如，一些表数据量非常大，有些数据是热点数据，按照日期分区MululbU
阅读更多...
MySQL中查找重复值的实现

MySQL中查找重复值的实现

《MySQL中查找重复值的实现》查找重复值是一项常见需求,比如在数据清理、数据分析、数据质量检查等场景下,我们常常需要找出表中某列或多列的重复值,具有一定的参考价值,感兴趣的可以了解一下... 目录技术背景实现步骤方法一：使用GROUP BY和HAVING子句方法二：仅返回重复值方法三：返回完整记录方法四：
阅读更多...
IDEA中新建/切换Git分支的实现步骤

IDEA中新建/切换Git分支的实现步骤

《IDEA中新建/切换Git分支的实现步骤》本文主要介绍了IDEA中新建/切换Git分支的实现步骤,通过菜单创建新分支并选择是否切换,创建后在Git详情或右键Checkout中切换分支,感兴趣的可以了... 前提：项目已被Git托管1、点击上方栏Git->NewBrancjsh...2、输入新的分支的
阅读更多...
从入门到精通MySQL联合查询

从入门到精通MySQL联合查询

《从入门到精通MySQL联合查询》：本文主要介绍从入门到精通MySQL联合查询,本文通过实例代码给大家介绍的非常详细,需要的朋友可以参考下... 目录摘要1. 多表联合查询时mysql内部原理2. 内连接3. 外连接4. 自连接5. 子查询6. 合并查询7. 插入查询结果摘要前面我们学习了数据库设计时要满
阅读更多...
Python实现对阿里云OSS对象存储的操作详解

Python实现对阿里云OSS对象存储的操作详解

《Python实现对阿里云OSS对象存储的操作详解》这篇文章主要为大家详细介绍了Python实现对阿里云OSS对象存储的操作相关知识,包括连接,上传,下载,列举等功能,感兴趣的小伙伴可以了解下... 目录一、直接使用代码二、详细使用1. 环境准备2. 初始化配置3. bucket配置创建4. 文件上传到os
阅读更多...
关于集合与数组转换实现方法

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》：本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2