前言
大家好吖,欢迎来到 YY 滴 数据结构 系列 ,热烈欢迎! 本章主要内容面向接触过C++的老铁
主要内容含:文章来源:https://www.toymoban.com/news/detail-764640.html
欢迎订阅 YY滴C++专栏!更多干货持续更新!以下是传送门!文章来源地址https://www.toymoban.com/news/detail-764640.html
- YY的《C++》专栏
- YY的《C++11》专栏
- YY的《Linux》专栏
- YY的《数据结构》专栏
- YY的《C语言基础》专栏
- YY的《初学者易错点》专栏
- YY的《小小知识点》专栏
一.哈希切割
- 哈希切分的基本概念: 是将一个大文件,利用哈希的原理, 将其分为若干个小文件。
【1】给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址?
- 根据 哈希切分的原理:相同的ip一定会进入同一个小文件中,用 map 统计每个小文件中相同ip出现的次数
二.位图应用
【1】给定100亿个整数,设计算法找到只出现一次的整数?
- 分析:我们可以用两个位图来控制,我们可以这样设计
![]()
- 代码展示设计思路如图所示:
template<size_t N>
class twobitset
{
public:
void set(size_t x)
{
// 00 -> 01
if (!_bs1.test(x) && !_bs2.test(x))
{
_bs2.set(x);
} // 01 -> 10
else if (!_bs1.test(x) && _bs2.test(x))
{
_bs1.set(x);
_bs2.reset(x);
}
// 本身10代表出现2次及以上,就不变了
}
bool is_once(size_t x)
{
return !_bs1.test(x) && _bs2.test(x);
}
private:
bitset<N> _bs1;
bitset<N> _bs2;
};
【2】位图应用变形:1个文件有100亿个int,1G内存,设计算法找到出现次数不超过2次的所有整数
- 此题的设计思路与上面的【1】基本一致,设计上要稍作改动:
![]()
- 代码展示设计思路如图所示:
template<size_t N>
class twobitset
{
public:
void set(size_t x)
{
// 00 -> 01
if (!_bs1.test(x) && !_bs2.test(x))
{
_bs2.set(x); //出现一次
} // 01 -> 10
else if (!_bs1.test(x) && _bs2.test(x))
{
_bs1.set(x);
_bs2.reset(x); //出现两次
}// 10 -> 11
else if (_bs1.test(x) && !_bs2.test(x))
{
_bs2.set(x); //出现三次
}
// 此外代表出现3次及以上,就不变了
}
bool max_two(size_t x)
{
return (_bs1.test(x) && !_bs2.test(x))||(!_bs1.test(x) && _bs2.test(x)); //10 或者 01
}
private:
bitset<N> _bs1;
bitset<N> _bs2;
};
【3】给两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件交集?
- 分析:
- 第一种思路是:把其中一个文件存入位图,遍历另一个文件元素,将问题转变成"在不在"问题
- 问题缺陷: 这种问题存在去重问题,即多次重复(下图中,交集明明只有一个3,但是会出现多个重复的3交集)
![]()
- 分析:
- 第二种思路是:将两个文件映射到两个位图中去(实现去重)
- 如果相对应的位置都是1(满足相&为1),则此元素就在交集中
三.布隆过滤器
【1】给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?分别给出精确算法和近似算法————(哈希切分)
- 我们先有一个内存大小基本概念:1G约为10亿byte,假设一个query平均为30byte,那么100亿query就约为3000亿byte,约为300G
- 哈希切分的基本概念: 是将一个大文件,利用哈希的原理, 将其分为若干个小文件。
- 相同的数据都被分到同一个文件里
- 在此题中,如下图所示,即:A和B中相同的query就会进入相同的小文件中
![]()
【2】如何扩展BloomFilter使得它支持删除元素的操作
- 多个位标识同一个值,使用 引用计数
到了这里,关于【数据结构】盘点那些经典的 [哈希面试题]【哈希切割】【位图应用】【布隆过滤器】(10)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!