如何快速判断虚拟地址是否已访问？程序运行统计性能优化咨询

1. 使用无序哈希集合（std::unordered_set） #

直接替换原有的vector，用std::unordered_set<uint64_t>存储已访问的block_number。它的查找操作平均时间复杂度为O(1)，相比vector的O(n)会带来数量级的速度提升，完全能解决当前的性能瓶颈。

示例代码：

#include <unordered_set>

std::unordered_set<uint64_t> accessed_blocks;

// 记录访问过的地址块
accessed_blocks.insert(block_number);

// 判断是否已访问
bool has_access = (accessed_blocks.find(block_number) != accessed_blocks.end());
// C++20及以上可用更简洁写法：
// bool has_access = accessed_blocks.contains(block_number);

这种方式只会存储实际被访问过的块号，内存开销远小于直接开辟48位地址的数组，适合绝大多数场景。

2. 布隆过滤器（Bloom Filter） #

如果内存资源极度紧张，且能接受极小概率的假阳性误判（即误判为已访问，但实际未访问），布隆过滤器是最优选择。它通过位数组+多个独立哈希函数实现，空间效率比哈希表高一个数量级以上。

核心逻辑：

• 初始化一个足够大的位数组（可使用std::bitset或动态分配的字节数组）
• 记录block_number时，用多个哈希函数计算出数组中的多个位，将这些位设为1
• 查询时，检查对应位是否全为1：若有任意一位为0，说明肯定未访问；若全为1，说明大概率已访问（存在小概率误判）

这种方案适合对内存要求极高，且误判影响可接受的场景。

3. 分层哈希/稀疏存储 #

如果访问地址存在局部性，或可按高位分段，可采用嵌套哈希结构，比如std::unordered_map<uint32_t, std::unordered_set<uint32_t>>，把48位地址拆分为高32位和低16位，仅当高位对应的哈希表存在时才存储低位，进一步压缩内存开销。不过这种实现复杂度稍高，性能略逊于纯std::unordered_set，适合内存特别紧张且地址分布有规律的场景。

内容的提问来源于stack exchange，提问作者Gerrie