- 正确答案：使用位图（Bitmap）或布隆过滤器（Bloom Filter）进行去重；但针对IPv4地址的精确去重，最优解是使用512MB大小的位图（bit array），因为IPv4地址总数为2^32 = 4,294,967,296个，每个地址映射为1 bit，总空间 = 2^32 / 8 = 536,870,912 字节 ≈ 512MB。9亿个IP（9×10^8）远小于全量空间，可一次性加载到位图中，时间复杂度O(n)，空间固定且最小，支持O(1)查重与插入，且结果100%精确。 - 解答思路：第一步：明确IPv4地址本质是32位无符号整数（0 ~ 2^32−1），共约42.9亿个可能值，因此天然适合用位图索引——将每个IP视为数组下标，用1 bit标记“是否出现过”。第二步：估算空间开销：2^32 bits = 2^32 ÷ 8 = 536,870,912 bytes ≈ 512MB，现代服务器内存完全可承载（远低于单机16GB/32GB常见配置）。第三步：逐个解析输入的9亿个IPv4字符串（如"192.168.1.1"），通过inet_aton()或手动解析转为uint32_t整数，作为bit index，设置对应bit为1；若该bit已为1，则为重复项，跳过或计数。第四步：遍历完成后，所有置1的bit位置即为去重后的唯一IP集合（如需输出，可扫描位图并逆向转换为点分十进制字符串）。 - 深度知识讲解： 1. 底层数据结构原理：位图本质是连续内存块（如char数组），每个字节存储8个标志位。访问第i个IP需计算 byte_index = i >> 3（即 i / 8），bit_offset = i & 7（即 i % 8），再用位运算操作：set: bits[byte_index] |= (1 << bit_offset)；test: (bits[byte_index] >> bit_offset) & 1。该操作是CPU级原子指令，无锁、零分支、极致高效。 2. 为什么不用哈希表？std::unordered_set虽逻辑简洁，但每个元素至少需8字节（key+指针），9亿个去重后最坏仍达7.2GB内存，且存在哈希冲突、动态扩容、内存碎片、缓存不友好等问题；而位图无哈希计算、无指针跳转、全顺序访存，L1/L2 cache命中率极高。 3. 为什么不用布隆过滤器？布隆过滤器空间更小（如用3哈希+0.1%误判率仅需≈1.5GB），但它是概率性数据结构，存在假阳性（把未出现IP判为已存在），无法保证精确去重；本题要求“去重”即必须100%准确，故布隆过滤器仅适用于前置快速过滤（如配合磁盘去重场景），不能单独使用。 4. 扩展优化点： - 若内存受限（如仅1GB可用），可采用分段位图（如按高8位分256个桶，每桶管理2^24=1677万IP，占2MB，共256×2MB=512MB），仍保持全局唯一性； - 若需流式处理且内存极小，可用外部排序+归并去重（先分块排序写磁盘，再k路归并时去重），但I/O开销大，时间复杂度升至O(n log n)； - IPv4地址分布实际稀疏（如公网IP仅约37亿，私有网段10.0.0.0/8等约1677万不对外），位图中大量连续0，可考虑Roaring Bitmap压缩（对连续区间用range encoding），在保持O(1)查询的同时将空间压缩至100~300MB，但增加实现复杂度。 - 代码示例（C++核心逻辑，含位图封装与IP解析）： ``` #include #include #include #include #include // for inet_pton class IPv4Bitmap { private: std::vector bits; static constexpr uint64_t TOTAL_IPV4 = 1ULL << 32; static constexpr size_t BITMAP_SIZE = TOTAL_IPV4 / 8; // 536870912 public: IPv4Bitmap() : bits(BITMAP_SIZE, 0) {} // 将点分十进制IP转为uint32_t（网络字节序） static uint32_t ipStrToUint32(const std::string& ip) { in_addr addr; if (inet_pton(AF_INET, ip.c_str(), &addr) == 1) { return ntohl(addr.s_addr); // 转主机字节序便于索引 } throw std::invalid_argument("Invalid IPv4 format: " + ip); } // 设置IP对应bit为1 void set(uint32_t ip) { size_t idx = ip / 8; uint8_t bit = 1 << (ip % 8); bits[idx] |= bit; } // 检查IP是否已存在 bool test(uint32_t ip) const { size_t idx = ip / 8; uint8_t bit = 1 << (ip % 8); return (bits[idx] & bit) != 0; } // 去重主流程：返回去重后IP数量 size_t deduplicate(const std::vector& ips) { size_t uniqueCount = 0; for (const auto& ipStr : ips) { try { uint32_t ip = ipStrToUint32(ipStr); if (!test(ip)) { set(ip); uniqueCount++; } } catch (...) { continue; } } return uniqueCount; } }; // 示例用法： // std::vector input = {"192.168.1.1", "10.0.0.1", "192.168.1.1"}; // IPv4Bitmap bm; // size_t uniq = bm.deduplicate(input); // returns 2 ```

虾皮实习 agent开发二面分享

全站热榜

创作者周榜