百万字符串检查是否重复有啥好办法不

[git00ll]

目前是利用 redis set 实现判断，但这么大的数据量与 redis 交互还是有点慢。

要求精准，不误判，不漏判

使用场景如下:

用户上传excel文件，需要解析文件并且禁止某一列的值存在相同的。还要查找出哪一行是重复的。

因为解析excel是个更加消耗资源的过程，且为了减少内存占用使用流式解析，即每次只能读取到一行记录。

并且文件可能很大，用java的set可能导致oom，现采用redis set，在内存中累计1000条，批量插入redis set中。 这是我能想到一定内存下的最好方式了。

布隆过滤器应该是不满足条件的，这里需要精准判断是否重复，不误判，漏判。

[ClarkAbe]

AC 自动机试试？不过感觉会更....

[lerry]

如果字符串比较长，可以先 hash 一下

[bagheer]

按行存为 txt, 然后 sort -u

[Mohanson]

前缀树

[wellsc]

又到了布隆过滤器时刻了

[wombat]

布隆，或者布谷鸟？

[Samuelcc]

可以描述一下使用场景。
例如是已经有一个词库，不断有新的输入和词库查重，还是就是固定的百万字符串里找重复的？
如果是前者，这个词库会有变化吗？

[sadfQED2]

要求精确的话布隆过滤器就别瞎掺和了吧。
建议
1.redis set，redis 根本不是你的瓶颈，读文件才是瓶颈
2.楼上的前缀树也可以，但是实现比 redis set 方案复杂太多了

[sadfQED2]

另外提醒一下，excel 我记得最多就 5 万多行吧，jvm 堆内存搞大点，set 也不会 oom 吧