文章 2024-08-12 来自:开发者社区

【C++航海王:追寻罗杰的编程之路】哈希的应用——位图 | 布隆过滤器

1 -> 位图 1.1 -> 位图的概念 位图的概念:所谓位图,就是用每一位来存放某种状态,适用于海量数据,数据无重复的场景。通常是用来判断某个数据是否存在的。 下面是一道面试题: 给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。 遍历,时间复杂度O(N)。 排序(O(Nlog...

【C++航海王:追寻罗杰的编程之路】哈希的应用——位图 | 布隆过滤器
文章 2024-05-29 来自:开发者社区

从C语言到C++_32(哈希的应用)位图bitset+布隆过滤器+哈希切割(下)

从C语言到C++_32(哈希的应用)位图bitset+布隆过滤器+哈希切割(中):https://developer.aliyun.com/article/1522346 完整 BloomFilter.h 和测试 #pragma once #include <iost...

从C语言到C++_32(哈希的应用)位图bitset+布隆过滤器+哈希切割(下)
文章 2024-05-29 来自:开发者社区

从C语言到C++_32(哈希的应用)位图bitset+布隆过滤器+哈希切割(中)

从C语言到C++_32(哈希的应用)位图bitset+布隆过滤器+哈希切割(上):https://developer.aliyun.com/article/1522341 1.3 位图解决海量数据面试题 下面是一些海量数据面试题: 1. 给定100亿个整数,如何设计算法找到只出现一次的整数? 2. 给两个文件,分别有100亿个整数,我们只有1G内存,如何...

从C语言到C++_32(哈希的应用)位图bitset+布隆过滤器+哈希切割(中)
文章 2024-05-29 来自:开发者社区

从C语言到C++_32(哈希的应用)位图bitset+布隆过滤器+哈希切割(上)

1. 位图 腾讯面试题:给40亿个不重复的无符号整数,没排过序。给一个无符号整数, 如何快速判断一个数是否在这40亿个数中。 根据我们现有的知识,该如何处理上面的问题呢? 1. 遍历,时间复杂度O(N) 2. 排序(O(NlogN)),利用二分查找: logN 3. 红黑树 / 哈希表。 还有很多其他的方式...

从C语言到C++_32(哈希的应用)位图bitset+布隆过滤器+哈希切割(上)
文章 2024-05-22 来自:开发者社区

【C++】哈希(位图、布隆过滤器)

一、哈希的应用(位图和布隆过滤器) 1、位图(bitset) (1)位图概念 【题目】 给 40亿 个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这 40亿 个数中。 遍历 40亿 个数,时间复杂度为:O(N)。 先排序,快排:O(NlogN),再利用二分查找:O(logN)。 ...

【C++】哈希(位图、布隆过滤器)
文章 2024-04-23 来自:开发者社区

【C++高阶(六)】哈希的应用--位图&布隆过滤器

1. 前言 哈希最常用的应用是unordered 系列的容器,但是当面对海量数据 如100亿个数据中找有没有100这 个数时,使用无序容器的话内存放不下 所以哈希思想还有别的更重要的应用! 本章重点: 本篇文章着重讲解哈希的应用的两个容器,一个是位图,一个是布隆过滤器,并且模拟实现它们.最后会讲解如何使用这两个容器来解决一些海量...

【C++高阶(六)】哈希的应用--位图&布隆过滤器
文章 2023-11-01 来自:开发者社区

【C++杂货铺】再谈哈希算法:位图 | 布隆过滤器 | 哈希切分

一、位图1.1 一道面试题给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。解决方案:遍历:遍历这40亿个整数,去判断该数是否在这40亿个整数中。时间复杂度是 O ( N ) O(N)O(N)。set:用 set 将这40亿个整数存起来,然后去判断这个数是否在 set 中。时间复杂度是 O ( l o g 2 N ) O(log2^N)O(log2....

【C++杂货铺】再谈哈希算法:位图 | 布隆过滤器 | 哈希切分
文章 2023-06-29 来自:开发者社区

【C++】哈希(位图,布隆过滤器)(一)

一、位图1.位图概念今天的内容从一道面试题开始引入:给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。首先我们对40亿个无符号整数改变一下,它到底是多少G呢?40亿个整数大概是  40亿*4个字节=160亿个字节4G=2^32byte,大概为42亿九千万字节,所以1G大概就是10亿字节 ,所以40亿个整数大概就是16G,那这么大数据放到内....

【C++】哈希(位图,布隆过滤器)(一)
文章 2023-06-29 来自:开发者社区

【C++】哈希(位图,布隆过滤器)(二)

最大的缺点就是:1.开空间得看数据范围,一般要求范围集中,分散的话空间消耗就会上升                             2.只能针对整型如果给了一堆字符串,可不可以使用位图判断是否存在呢?当然可以,可以使用哈希函数,将字符串转化为整型,再....

【C++】哈希(位图,布隆过滤器)(二)
文章 2023-05-22 来自:开发者社区

【C++】哈希应用:位图 哈希切分 布隆过滤器

我走后,他们会给你们加班费,会给你们调休,这并不是他们变好了,而是因为我来过。------龙哥一、位图1.位图概念1.大厂经典的面试题,给你40亿个不重复的无符号整数,让你快速判断一个数是否在这40亿个数中,最直接的思路就是遍历这40亿个整数,逐一进行比对,当然这种方式可以倒是可以,但是效率未免太低了。另一种方式就是排序+二分的查找,因为二分查找的效率还是比较高的,logN的时间复杂度,但是磁盘....

【C++】哈希应用:位图 哈希切分 布隆过滤器

本页面内关键词为智能算法引擎基于机器学习所生成,如有任何问题,可在页面下方点击"联系我们"与我们沟通。

开发与运维

集结各类场景实战经验,助你开发运维畅行无忧

+关注
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等