百度面试题，如何快速找出文件(大文件无法一次性读取)中的重复项？

Question

百度面试题，大致意思是说，有个文件，文件很大不能一次性读取（可能是不能一次性加载到内存中），文件中存放的是IP地址，如何快速找出重复的IP地址？求指点思路。

文件很大，可以逐行读取，append到list中，取set，再取差集，不知是否可行？

Answer 1

不可行。

1. append 到 list中，，跟直接一次性读取没差，都是要占用所有数据的内存；
2. 取差集只能set - list，不能 list - set

Answer 2

条件不充分阿。如果有1000万条记录地址，只有几个重复，目前想到的可以先排序，然后map-reduce。如果有1000万条记录，其中900万是重复的，用hashTable就解决了。

Answer 3

IPv4么…… 一共才 4Gi 个地址，到内存里挖好坑，等着IP来跳。浪费点，用int8来存也就是4GB内存，节省点，用bit存的话只要500MB。思路可以活点，其实我觉得给出IP地址这个限制条件就是在降低难度。

IPv6的话，可能就得分治。基本思路就是先按内存能承受的长度去检查地址的前几位，碰撞了的丢同一个bucket里，然后再一个一个bucket地去看里面有没有重的，往下也可以再分。其实DBMS整天干这事……

Answer 4

首先把ip转成int(网上一堆算法请百度)
然后做一个大的数组
比如192.168.3.4转换后为3232236292
对应的数组为 int array[3232236292-1]做计数即可
再简化一下，由于数组要预先分配，这里用map就行

Answer 5

先生成一个包含所有ip的map 如map<ip,1>，也就1000万条。（这个可以优化下）然后一条一条从文件读，读之后从 map里面取v=map.get(ip) 如果 v=1,map.put(ip,0),如果 v=0 说明已经有重复的了，console.log(ip)