- 正确答案：9亿个IPv4地址去重，本质是海量整数（0~2^32-1，共约42.9亿个可能值）的集合去重与查询问题。最优解是使用位图（Bitmap）或布隆过滤器（Bloom Filter）+外部排序/分块哈希等组合策略；但严格去重且支持精确查询时，位图是最优选择——仅需512MB内存（2^32 bits = 536,870,912 bytes ≈ 512MB），可实现O(1)插入与查询、零误判、零漏判；若内存受限（如仅100MB），则采用分片位图+磁盘映射（mmap）、或基数树（Radix Tree）压缩存储、或Roaring Bitmap（对稀疏IPv4地址分布更省内存）；查询时直接按IP转为uint32后查bit位即可。 - 解答思路：第一步：理解IPv4地址本质——32位无符号整数，范围[0, 2^32) = [0, 4294967296)，共42.9亿个唯一可能值；9亿个输入远小于全空间，但远超常规哈希表内存开销（如Java HashSet存9亿Integer对象，每个至少16~24字节，需14~21GB）。因此必须放弃“存原始字符串或对象”思路，转向数值化+紧凑位表示。第二步：评估位图可行性——2^32 bits = 536,870,912 bytes = 512MB，现代服务器完全可承载，且支持原子级去重（set bit）和O(1)查询（test bit）。这是理论最优解。第三步：考虑边界与优化——若实际IPv4分布高度稀疏（如只集中在某些网段），可用Roaring Bitmap将连续区间压缩为range container，内存可降至100~300MB；若需支持删除操作，则改用Cuckoo Filter或扩展位图（如counting bitmap，但IPv4无需计数）；若单机内存仍不足，可按高8位分256桶（0.0.0.0/8 ~ 255.0.0.0/8），每桶独立位图（2^24 bits ≈ 2MB × 256 = 512MB，不变），但便于并行加载与分布式扩展。第四步：查询实现——将点分十进制IP（如"192.168.1.1"）解析为uint32：(a<<24)+(b<<16)+(c<<8)+d，再检查bitmap[(ip>>3) & mask] 的第 (ip & 7) 位是否为1。 - 深度知识讲解： ▶ 底层数据结构原理： - 位图本质是byte数组+位运算。每个bit代表一个IP是否存在。内存布局连续，CPU缓存友好（cache line利用率高）。set操作：bitmap[index >> 3] |= (1 << (index & 7))；test操作：(bitmap[index >> 3] >> (index & 7)) & 1。无指针、无哈希冲突、无内存碎片。 - Roaring Bitmap：将32位IP拆为高16位（container key）和低16位（value）。对每个key，若低16位密集（>4096个），用bitmap container（2^16 bits=8KB）；若稀疏，用array container（存实际short值，每个2B）。IPv4实际分布常呈网段聚集性（如大量10.x.x.x、192.168.x.x），Roaring可比原生位图节省50%+内存，且支持快速交并差运算。 - 基数树（Radix Tree / PATRICIA）：以IP二进制位为路径建树，共享前缀节点。适合动态增删、内存按实际数据量增长（非固定512MB），但最坏查询O(32)=O(1)，平均更快；Linux内核路由表即用此结构。但实现复杂，缓存不友好。 ▶ 内存问题本质分析： - 字符串存储陷阱：9亿个"xxx.xxx.xxx.xxx"字符串，平均15字节/个 + Java对象头+引用+String内部char[]开销 → 实测Java中约20~25字节/IP → 至少18GB内存，OOM风险极高。 - 普通HashSet陷阱：底层HashMap需负载因子<0.75，9亿entry需至少12亿桶，每个桶含Node对象（next+hash+key+value指针），64位JVM下每个Node约32字节 → 再加数组本身，总内存>40GB。 - 位图无此问题：纯数据，无元数据，无GC压力，内存占用严格确定（512MB），且可mmap到文件实现持久化与冷热分离。 ▶ 可扩展优化方向： - 内存映射（mmap）：将位图文件mmap到进程虚拟地址空间，OS按需分页加载，启动快、支持超大位图（如未来处理IPv6需2^128 bits，此时必须分片+磁盘索引）。 - SIMD加速：批量解析IP字符串时，用AVX2指令并行转换4个IP为uint32（Intel Intrinsics _mm256_shuffle_epi8 + _mm256_maddubs_epi16），吞吐提升3~5倍。 - 分布式去重：若数据分散在多台机器，先本地位图去重，再用HyperLogLog估算全局基数（误差<0.8%），或用Redis Cluster的BITOP OR聚合各节点位图（需统一IP→bit index映射规则）。 - 伪代码（核心位图实现）： ``` // 初始化位图：512MB = 2^32 bits byte[] bitmap = new byte[1 << 29]; // 2^29 bytes = 512MB // IP字符串转uint32（安全版，含校验） uint32 parseIP(String ip) { String[] parts = ip.split("\\."); if (parts.length != 4) throw invalid; uint32 res = 0; for (int i = 0; i < 4; i++) { int v = Integer.parseInt(parts[i]); if (v < 0 || v > 255) throw invalid; res = (res << 8) | v; } return res; } // 设置IP存在 void addIP(uint32 ip) { int byteIndex = ip >> 3; int bitIndex = ip & 7; bitmap[byteIndex] |= (1 << bitIndex); } // 查询IP是否存在 boolean containsIP(uint32 ip) { int byteIndex = ip >> 3; int bitIndex = ip & 7; return (bitmap[byteIndex] & (1 << bitIndex)) != 0; } // 批量去重主流程 void deduplicate(List ips) { for (String ip : ips) { try { uint32 u = parseIP(ip); addIP(u); } catch (Exception e) { /* 忽略非法IP */ } } } ``` - 补充说明：若题目隐含“无法预知全部IP，需流式处理”，则位图仍适用（动态add）；若要求“返回去重后IP列表”，只需遍历bitmap，对每个置位bit反算IP（i*8 + j → 四字节拆解），时间O(2^32)，但实际只需遍历9亿个有效位——可通过游程编码（RLE）或Roaring的迭代器加速。真正瓶颈从来不是算法，而是IO和解析——建议用内存映射文件读取原始日志，并用零拷贝Netty或JNI调用C库（如inet_pton）加速IP解析。

4.14虾皮后端实习二面

全站热榜

创作者周榜