💓博主CSDN主页:杭电码农-NEO💓 ⏩专栏分类:C++从入门到精通⏪ 🚚代码仓库:NEO的学习日记🚚 🌹关注我🫵带你学习C++ 🔝🔝哈希的应用1.前言2.位图的概念以及定义3.位图的模拟实现4.布隆过滤器的概念以及定义5.布隆过滤器模拟实现(一)6.布隆过滤器模拟实现(二)7.处理海量数据的面试题8.总结1.前言哈希最常用的应用是unordered系列的容器,但是当面对海量数据如100亿个数据中找有没有100这个数时,使用无序容器的话内存放不下所以哈希思想还有别的更重要的应用!本章重点:本篇文章着重讲解哈希的应用的两个容器,一个是位图,一个是布隆过滤器,并且模拟实现它们.最后会讲解如何使用
哈希的应用——布隆过滤器文章目录哈希的应用——布隆过滤器一、布隆过滤器的概念与性质1.布隆过滤器的引出2.布隆过滤器的概念3.布隆过滤器的误判4.布隆过滤器的应用场景5.布隆过滤器优缺点6.如何选择哈希函数个数和布隆过滤器长度二、布隆过滤器的实现1.布隆过滤器基本框架2.布隆过滤器的Set插入3.布隆过滤器的Test查找4.布隆过滤器的删除一、布隆过滤器的概念与性质1.布隆过滤器的引出我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会
一、哈希的应用（位图和布隆过滤器）1、位图（bitset）（1）位图概念【题目】给 40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。遍历40亿个数，时间复杂度为：O(N)。先排序，快排：O(NlogN)，再利用二分查找：O(logN)。将40亿个数放进set/unordered_set中，然后再查找key在不在。位图解决。前面三种解法看似可行，实际上有很大的问题：内存消耗太大。40亿个整数要占用多少空间？大约是16GB。1GB=1024*1024*1024=210*210*210=230（大约是10亿byte）4GB=4*230=232byte（
前言： 在如今的开发中，使用缓存中间件Redis已经成为一项很广泛的技术，Redis的高性能大大优化了我们的服务器性能，缓解了在高并发的情况下服务器的压力。它基于缓存的形式，在内存中保存数据，减少对磁盘的IO操作。然而尽管Redis有着很多的优点，但仍然有三朵乌云漂浮在Redis的上空：穿透，击穿，雪崩。而我们今天就把焦点聚焦于Redis的穿透问题。目录前言：什么是Redis的穿透问题：布隆过滤器：基于SpringBoot实现布隆过滤器：总结：什么是Redis的穿透问题： Redis的穿透问题是指当应用程序查询一个不存在于缓存中的数据时，请求会直接穿透到后端存储系统（如数
布隆过滤器（BloomFilter）和布谷鸟过滤器（CuckooFilter）是两种概率型数据结构，用于快速而高效地检查一个元素是否属于一个集合。尽管它们都能够用于这一目的，但在实现细节、性能特点和使用场景上存在不同。布隆过滤器(BloomFilter)布隆过滤器由一个位数组和几个哈希函数组成。添加元素时，会使用这些哈希函数计算多个位置，并将位数组中对应的位置设为1。检查元素是否存在时，如果所有哈希函数计算出来的位置都是1，则认为该元素可能存在；如果任何一个位置是0，则肯定不存在。布隆过滤器存在一定的假阳性率（false-positiverate），即有可能错误地判断一个不存在的元素为存在，但
一、前言在实际开发中，会遇到很多要判断一个元素是否在某个集合中的业务场景，类似于垃圾邮件的识别，恶意ip地址的访问，缓存穿透等情况。类似于缓存穿透这种情况，有许多的解决方法，如：redis存储null值等，而对于垃圾邮件的识别，恶意ip地址的访问，我们也可以直接用HashMap去存储恶意ip地址以及垃圾邮件，然后每次访问时去检索一下对应集合中是否有相同数据。这种思路对于数据量小的项目来说是没有问题的，但是对于大数据量的项目，如，垃圾邮件出现有十几二十万，恶意ip地址出现有上百万，或者从几十亿电话中检索出指定的电话是否在等操作，那么这十几亿的数据就会占据大几G的空间，这个时候就可以考虑一下布隆过
hash原理与应用一、背景知识二、散列表2.1、散列表的构成2.2、hash函数2.3、散列表的操作流程2.4、hash冲突2.5、hash冲突的处理2.6、STLunordered_*散列表的实现2.7、小结三、布隆过滤器(BloomFilter)3.1、背景3.2、布隆过滤器的构成3.3、布隆过滤器原理3.4、应用场景3.5、应用分析3.6、布隆过滤器的实际使用3.7、小结四、分布式一致性hash4.1、背景4.2、一致性hash原理4.3、应用场景4.4、hash偏移4.5、hash迁移4.6、虚拟结点4.7、思维导图五、思考总结一、背景知识在了解hash算法之前，先思考如下问题：使用w
我想在Redis数据库之上为分布式爬虫系统实现URL过滤(例如，不要访问同一个URL两次，所以我需要以某种方式以最小的内存指纹来跟踪所有这些，没有必要要存储完整的URL，只需检查是否访问过某些特定的URL)。Bloom过滤器在这种情况下听起来不错，我看到了一个用于Redis的本地模块来实现Bloom过滤器。但它也有内置的HyperLogLog数据结构，所以我想知道在我的场景中哪个是更好的选择。 最佳答案 布隆过滤器与HyperLogLog完全不同。布隆过滤器用于检查是否有重复项，而HyperLogLog用于不同的计数。在您的情况下，
文章目录一、位图1.1一道面试题1.2位图的概念1.3位图的模拟实现1.4位图的应用1.4.1给定100亿个整数，设计算法找到只出现一次的整数1.4.2给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？1.4.31个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数二、布隆过滤器2.1布隆过滤器的提出2.2布隆过滤器的概念2.3布隆过滤器的插入2.4布隆过滤器的查找2.5布隆过滤器的删除2.6布隆过滤器的优点2.7布隆过滤器的缺陷2.8布隆过滤器的实际应用场景三、哈希切分四、结语一、位图1.1一道面试题给40亿个不重复的无符号整数，没排过序。给一
本文已收录至GitHub，推荐阅读👉Java随想录微信公众号：Java随想录原创不易，注重版权。转载请注明原作者和原文链接目录布隆过滤器简介fpp布隆过滤器原理布隆过滤器的特点布隆过滤器使用布隆过滤器中的数据可不可以删除布隆过滤器应该设计为多大布隆过滤器应该使用多少个哈希函数布隆过滤器的时间复杂度和空间复杂度布隆过滤器实现Guava的布隆过滤器的实现BitMap（位图）在日常生活和工作中，我们经常需要处理海量的数据，筛选出有用的信息。这个时候，布隆过滤器（BloomFilter）就派上了用场。作为一种空间高效的概率型数据结构，布隆过滤器能够快速有效地检测一个元素是否属于一个集合。其应用广泛，从
