位图(Bitset)是一种数据结构,用于表示一组布尔值,其中每个元素通常对应于一个位或一个二进制值,可以存储0或1。位图在计算机科学和计算机工程中经常用于各种应用,特别是在位级别的标志、掩码和快速查找中。以下是位图的一些关键特点:
应用领域包括:
某大厂给过这样一道面试题,具体如下:
给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中
你可能最开始想遍历?那肯定是不行的,因为40亿个无符号数占用将近15G内存。
那使用散列表呢?那这里使用的空间能在内存上吗?显然不可以,就算可以
又会遇到各种各样的问题
那么这里就可以用到我们上面提到的位图概念
位图(Bitset)方法:
优点:
这里我们只需要不到500M就很好的解决了这个问题,听起来挺理想的,那么应该如何来实现它呢?
代码如下:
template<size_t N>
class bitset
{
public:
bitset()
{
_bits.resize(N/8+1, 0);
}
void set(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
_bits[i] |= (1 << j);
}
void reset(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
_bits[i] &= ~(1 << j);
}
bool test(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
return _bits[i] & (1 << j);
}
private:
vector<char> _bits;
};
模板的作用就是用来传需要查询数的范围,比如我们这里有40亿怎么传值呢?
因为是无符号数,而无符号数范围是0-42亿左右,那我们不妨传入最大值,即-1
bitset<-1> bs1;
你可能会有疑问,多了两亿不会多很多内存吗?
答案是不会,占满其实也就512M,具体我们看下面的实现
我们先看成员变量的建立,由于在编程语言中,我们没有按位存储的存储类型(至少C/C++是没有的)
所以这里我们采用最小存储类型char,char占1个字节,可是我们需要的是1bit,那么我们该如何做呢?
接下来我们看位图的构造函数,我们用模板参数/8,初始化每个字节为全0,多+1是由于数组的索引从0开始,所以需要额外的一个元素来确保能够容纳最高索引 N-1
的位,这样我们的空间开辟完毕,也初始化完毕
接下来我们看set函数(此函数用于入位图)
void set(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
_bits[i] |= (1 << j);
}
用于将指定索引 x
处的位设置为1:
size_t i = x / 8;
:这一行代码计算索引 x
对应的字节(byte)索引。因为 _bits
是一个 vector
,每个元素代表一个字节(8位),所以我们用索引 x
除以8来得到字节索引。size_t j = x % 8;
:这一行代码计算索引 x
对应的位在字节中的位置。它使用取模运算来获得余数,表示在字节中的位偏移。_bits[i] |= (1 << j);
:这一行代码使用位操作将位图中索引 x
处的位设置为1。具体来说:
(1 << j)
会创建一个只有第 j
位为1的整数。例如,如果 j
是3,那么 (1 << 3)
将得到二进制 00001000
。_bits[i] |= (1 << j)
利用位或运算符将 _bits[i]
中对应的位和上面的整数进行“或”操作,将指定位设置为1。这个函数的目的是在位图中设置指定索引 x
处的位为1,从而表示该位置存在某种标记或状态。
reset函数(此函数用于出位图)
void reset(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
_bits[i] &= ~(1 << j);
}
用于将指定索引 x
处的位重置为0:
size_t i = x / 8;
:这一行代码计算索引 x
对应的字节(byte)索引,以确定所在的字节。size_t j = x % 8;
:这一行代码计算索引 x
对应的位在字节中的位置,以确定位的偏移。_bits[i] &= ~(1 << j);
:这一行代码使用位操作将位图中索引 x
处的位重置为0。具体来说:
(1 << j)
会创建一个只有第 j
位为1的整数。例如,如果 j
是3,那么 (1 << 3)
将得到二进制 00001000
。~(1 << j)
会创建一个只有第 j
位为0、其余位为1的整数,以便将第 j
位重置为0。_bits[i] &= ~(1 << j)
利用位与运算符将 _bits[i]
中对应的位和上面的整数进行“与”操作,将指定位设置为0。这个函数的目的是在位图中重置指定索引 x
处的位为0,从而表示该位置不存在某种标记或状态。
test函数(此函数用于查询数是否在位图中)
bool test(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
return _bits[i] & (1 << j);
}
用于检查指定索引 x
处的位是否为1:
size_t i = x / 8;
:这一行代码计算索引 x
对应的字节(byte)索引,以确定所在的字节。size_t j = x % 8;
:这一行代码计算索引 x
对应的位在字节中的位置,以确定位的偏移。_bits[i] & (1 << j)
:这一行代码使用位操作检查位图中索引 x
处的位是否为1。具体来说:
(1 << j)
会创建一个只有第 j
位为1的整数。例如,如果 j
是3,那么 (1 << 3)
将得到二进制 00001000
。_bits[i] & (1 << j)
利用位与运算符将 _bits[i]
中对应的位和上面的整数进行“与”操作,以检查该位是否为1。如果结果为0,表示该位为0;如果结果为非0,表示该位为1。这个函数的目的是检查位图中指定索引 x
处的位是否为1,以判断某种标记或状态是否存在。如果该位为1,函数返回true
,表示存在;如果该位为0,函数返回false
,表示不存在。
实际上在C++中是加入了位图这个容器的,名称和我这一样,这里我们模拟实现是为了更好的理解这个概念
库中的bitset
功能更多,但主要函数也是这几个
其实这种问题和我们上面的示例的题目类似,解决方式只需略作改动。
我们可以使用两个位图分别标记存在次数,也就类似key value型,这里我们只需要标记3种情况
代码如下:
template<size_t N>
class twobitset
{
public:
void set(size_t x)
{
bool inset1 = _bs1.test(x);
bool inset2 = _bs2.test(x);
// 00
if (inset1 == false && inset2 == false)
{
// -> 01
_bs2.set(x);
}
else if (inset1 == false && inset2 == true)
{
// ->10
_bs1.set(x);
_bs2.reset(x);
}
else if (inset1 == true && inset2 == false)
{
// ->11
_bs1.set(x);
_bs2.set(x);
}
}
void print_once_num()
{
for (size_t i = 0; i < N; ++i)
{
if (_bs1.test(i) == false && _bs2.test(i) == true)
{
cout << i << endl;
}
}
}
private:
bitset<N> _bs1;
bitset<N> _bs2;
};
这里我们需要实现一个双位图(Two-Bitset)数据结构。双位图是一种在每个索引上存储两个位的数据结构,通常用于表示每个索引的两种状态。代码解析如下:
set(size_t x)
函数:
_bs1
和 _bs2
位图中索引 x
处的状态。_bs1
中索引 x
处的位为0,而 _bs2
中索引 x
处的位也为0(00状态),则将 _bs2
中索引 x
处的位设置为1,将其状态变为01。_bs1
中索引 x
处的位为0,而 _bs2
中索引 x
处的位为1(01状态),则将 _bs1
中索引 x
处的位设置为1,将 _bs2
中索引 x
处的位重置为0,将其状态变为10。_bs1
中索引 x
处的位为1,而 _bs2
中索引 x
处的位为0(10状态),则将 _bs1
和 _bs2
中索引 x
处的位都设置为1,将其状态变为11。print_once_num()
函数:
_bs2
中为1而在 _bs1
中为0的索引。这些索引被认为在双位图中只出现一次。两个题目其实相似,无非就是多一种状态,原理同上
在上面我们用位图很好的解决了多重整数高效查询的问题,那么我们在面对字符串时,该如何解决呢?
布隆过滤器(Bloom Filter)是由布隆在1970年提出的,它是一种空间效率高、查询速度快的数据结构,主要用于判断一个元素是否属于一个集合。布隆过滤器的提出解决了在大规模数据集中进行高效查找的问题,特别是当内存或存储有限的情况下。
以下是布隆过滤器的提出背景和主要原理:
提出背景: 在计算机科学中,一些常见的问题包括查找元素是否在某个集合中,如单词拼写检查、垃圾邮件过滤、URL检测等。传统的数据结构如散列表或树结构可以解决这些问题,但它们在存储和查询效率上存在一些限制,特别是在面对大规模数据集时。因此,布隆过滤器的提出是为了解决这些限制。
原理: 布隆过滤器的核心思想是使用一个位数组(Bit Array)和多个哈希函数。其主要工作步骤如下:
特点:
布隆过滤器的插入过程是其核心操作之一,用于将元素添加到布隆过滤器中,以便后续查询该元素是否存在于集合中。下面是布隆过滤器的插入过程的详细解释:
注意事项:
插入过程使布隆过滤器记录了元素的存在,使后续的查询操作成为可能。查询操作会利用相同的哈希函数,检查位数组中的位来确定元素是否在集合中。这使得布隆过滤器在查找元素是否存在时非常高效,尤其适用于大规模数据集和资源有限的环境。
还需要注意的是,哈希参数当然是越多误判率越低,但是面临的问题就是内存也会越来越大,所以我们需要找到最合适的哈希函数个数,关于这一点,我们可以参考知乎大佬的一篇文章
具体总结为
布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中,因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找:分别计算每个哈希值对应的比特位置存储的是否为零,只要有一个为零,代表该元素一定不在哈希表中,否则可能在哈希表中
注意:布隆过滤器如果说某个元素不存在时,该元素一定不存在,如果该元素存在时,该元素可能存在,因为有些哈希函数存在一定的误判
比如:在布隆过滤器中查找"alibaba"
时,假设3个哈希函数计算的哈希值为:1、3、7
,刚好和其他元素的比特位重叠,此时布隆过滤器告诉该元素存在,但实该元素是不存在的,存在可能存在误判,但是不存在不会存在误判
布隆过滤器不能直接支持删除工作,因为在删除一个元素时,可能会影响其他元素
比如:删除其中一个元素,如果直接将该元素所对应的二进制比特位置0,另一元素也被删除了,因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠
一种支持删除的方法:将布隆过滤器中的每个比特位扩展成一个小的计数器,插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一,删除元素时,给k个计数器减一,通过多占用几倍存储空间的代价来增加删除操作
在这里我们先实现3个哈希函数
struct HashBKDR
{
// BKDR
size_t operator()(const string& key)
{
size_t val = 0;
for (auto ch : key)
{
val *= 131;
val += ch;
}
return val;
}
};
struct HashAP
{
// BKDR
size_t operator()(const string& key)
{
size_t hash = 0;
for (size_t i = 0; i < key.size(); i++)
{
if ((i & 1) == 0)
{
hash ^= ((hash << 7) ^ key[i] ^ (hash >> 3));
}
else
{
hash ^= (~((hash << 11) ^ key[i] ^ (hash >> 5)));
}
}
return hash;
}
};
struct HashDJB
{
// BKDR
size_t operator()(const string& key)
{
size_t hash = 5381;
for (auto ch : key)
{
hash += (hash << 5) + ch;
}
return hash;
}
};
布隆过滤器代码
// N表示准备要映射N个值
template<size_t N,
class K = string, class Hash1 = HashBKDR, class Hash2 = HashAP, class Hash3 = HashDJB>
class BloomFilter
{
public:
void Set(const K& key)
{
size_t hash1 = Hash1()(key) % (_ratio*N);
//cout << hash1 << endl;
_bits->set(hash1);
size_t hash2 = Hash2()(key) % (_ratio*N);
//cout << hash2 << endl;
_bits->set(hash2);
size_t hash3 = Hash3()(key) % (_ratio*N);
//cout << hash3 << endl;
_bits->set(hash3);
}
bool Test(const K& key)
{
size_t hash1 = Hash1()(key) % (_ratio*N);
//cout << hash1 << endl;
if (!_bits->test(hash1))
return false; // 准确的
size_t hash2 = Hash2()(key) % (_ratio*N);
//cout << hash2 << endl;
if (!_bits->test(hash2))
return false; // 准确的
size_t hash3 = Hash3()(key) % (_ratio*N);
//cout << hash3 << endl;
if (!_bits->test(hash3))
return false; // 准确的
return true; // 可能存在误判
}
private:
const static size_t _ratio = 5;
std::bitset<_ratio*N>* _bits = new std::bitset<_ratio*N>;
};
Set
方法用于将元素插入布隆过滤器中。Test
方法用于测试元素是否存在于布隆过滤器中。false
。true
。这个布隆过滤器可以用于在快速查找集合中的元素是否存在,但需要注意,它存在误判的可能性,即可能会将不在集合中的元素判断为存在。_ratio
在这个布隆过滤器实现中是一个倍数,它决定了位数组的大小。位数组的大小是 _ratio * N
,其中 N
表示准备要映射的值的数量。具体来说,这个倍数 _ratio
用于控制位数组的大小以平衡误判率和内存使用。增加 _ratio
会增加位数组的大小,从而减小误判率,但也会增加内存占用。减小 _ratio
会减小位数组的大小,降低内存占用,但也会增加误判率。
- 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数,一般比较小),与数据量大小无关
- 哈希函数相互之间没有关系,方便硬件并行运算
- 布隆过滤器不需要存储元素本身,在某些对保密要求比较严格的场合有很大优势
- 在能够承受一定的误判时,布隆过滤器比其他数据结构有这很大的空间优势
- 数据量很大时,布隆过滤器可以表示全集,其他数据结构不能
- 使用同一组散列函数的布隆过滤器可以进行交、并、差运算
- 有误判率,即存在假阳性(False Position),即不能准确判断元素是否在集合中(补救方法:再建立一个白名单,存储可能会误判的数据)
- 不能获取元素本身
- 一般情况下不能从布隆过滤器中删除元素
- 如果采用计数方式删除,可能会存在计数回绕问题
给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址?与上题条件相同,如何找到top K的IP?如何直接用Linux系统命令实现?
使用布隆过滤器和哈希切割
Set
方法来实现。使用Linux系统命令
Linux系统提供了一些强大的命令行工具来处理文本文件,可以使用这些工具来解决问题:
- 使用
awk
命令或grep
命令提取日志文件中的IP地址。- 使用
sort
命令对提取的IP地址进行排序。- 使用
uniq -c
命令统计IP地址的出现次数。- 使用
sort -nr
命令按出现次数对IP地址进行逆序排序。- 使用
head
命令来获取top K的IP地址。
示例命令行操作:
cat log_file.log | grep -oE "\b([0-9]{1,3}\.){3}[0-9]{1,3}\b" | sort | uniq -c | sort -nr | head -n K
这将列出出现次数最多的top K个IP地址。
无论使用哪种方法,都需要根据实际需求和性能要求来选择。使用布隆过滤器和哈希切割的方法可能需要编写自定义代码,但可以处理非常大的数据集。使用Linux系统命令则更加简单,但可能受限于系统资源和性能。
给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?分别给出精确算法和近似算法
在这种情况下,由于内存有限,需要使用外部排序(external sorting)技术来处理这两个大型文件并找到它们的交集。外部排序是一种适用于大规模数据集的算法,其中数据无法完全加载到内存中。
精确算法:
- 分别对两个文件进行外部排序:首先,将两个文件分别划分为多个小文件块,每个小文件块可以适应内存的大小。然后,对每个小文件块进行内部排序,以确保每个块内的数据是有序的。
- 合并排序的块:对于每个文件,使用归并排序等合并算法,逐个合并排序后的小块,以创建一个完全有序的大文件。
- 查找交集:一旦两个文件都有序,可以使用合并算法来查找它们的交集。比较两个文件中的元素,将相同的元素输出到结果文件中。
这是一个精确的算法,它可以找到确切的交集,但需要大量的磁盘I/O和计算时间,因为数据需要多次读取和写入磁盘。
近似算法: 在内存有限的情况下,使用布隆过滤器可以实现近似的交集查找。以下是近似算法的步骤:
- 构建两个布隆过滤器:对于每个文件,构建一个布隆过滤器。这需要一小部分内存。在构建布隆过滤器时,需要选择合适的哈希函数和位数组大小,以平衡内存使用和误判率。
- 查询交集:对于第一个文件的每个查询,检查是否在第二个布隆过滤器中。如果布隆过滤器中存在该查询,将其添加到结果集中。
- 结果集:结果集中包含两个文件的近似交集。
近似算法的主要优点是节省了内存,但它会引入误判。如果某个查询在第一个布隆过滤器中存在,但实际上不存在于第二个文件中,它仍然会出现在结果集中。误判率取决于布隆过滤器的参数选择。
无论使用哪种算法,都需要在性能和准确性之间做权衡。精确算法提供准确的结果,但需要更多的时间和资源。近似算法可以在有限内存下快速处理,但可能会引入一定程度的误判。
如何扩展BloomFilter使得它支持删除元素的操作
Bloom过滤器是一种概率数据结构,通常不支持元素的删除操作。要扩展Bloom过滤器以支持元素的删除,可以考虑使用一些额外的技巧。以下是一种可能的方法:
使用计数型Bloom过滤器
一种支持删除操作的变体是计数型Bloom过滤器(Counting Bloom Filter)。与标准Bloom过滤器不同,计数型Bloom过滤器中的每个位不是简单的0或1,而是一个计数器。计数器可以表示一个元素被插入的次数。
以下是如何扩展Bloom过滤器以支持删除元素的步骤:
- 初始化计数型Bloom过滤器:创建一个计数型Bloom过滤器,其中每个位都初始化为0。计数型Bloom过滤器的大小通常与标准Bloom过滤器相同。
- 插入元素:当要插入元素时,不再将相应的位设置为1,而是增加相应的计数器。每次插入操作会增加计数器的值。
- 查询元素:在查询操作中,检查计数器是否大于零。如果计数器大于零,则表示元素存在。这是因为每次插入操作都会增加计数器的值。
- 删除元素:要删除元素,可以递减相应的计数器。如果计数器变为零,元素就被标记为不存在。
注意:在计数型Bloom过滤器中,可能存在溢出问题。因此,在删除元素时,需要小心确保计数器不会变为负数。
这种方法允许支持删除操作,但会占用更多的内存。计数型Bloom过滤器在需要跟踪元素出现次数的应用中非常有用,但仍然需要注意误判和溢出问题
另请注意,标准Bloom过滤器无法实现可靠的删除操作,因为删除一个元素可能会影响其他元素的位状态,从而导致不可预测的行为。计数型Bloom过滤器是一种可以处理删除操作的变体,但它需要更多的内存和计算资源。
示一个元素被插入的次数。
以下是如何扩展Bloom过滤器以支持删除元素的步骤:
- 初始化计数型Bloom过滤器:创建一个计数型Bloom过滤器,其中每个位都初始化为0。计数型Bloom过滤器的大小通常与标准Bloom过滤器相同。
- 插入元素:当要插入元素时,不再将相应的位设置为1,而是增加相应的计数器。每次插入操作会增加计数器的值。
- 查询元素:在查询操作中,检查计数器是否大于零。如果计数器大于零,则表示元素存在。这是因为每次插入操作都会增加计数器的值。
- 删除元素:要删除元素,可以递减相应的计数器。如果计数器变为零,元素就被标记为不存在。
注意:在计数型Bloom过滤器中,可能存在溢出问题。因此,在删除元素时,需要小心确保计数器不会变为负数。
这种方法允许支持删除操作,但会占用更多的内存。计数型Bloom过滤器在需要跟踪元素出现次数的应用中非常有用,但仍然需要注意误判和溢出问题
另请注意,标准Bloom过滤器无法实现可靠的删除操作,因为删除一个元素可能会影响其他元素的位状态,从而导致不可预测的行为。计数型Bloom过滤器是一种可以处理删除操作的变体,但它需要更多的内存和计算资源。