Java高效去重

Question

假设您有一个大型文本文件。每一行都包含一个电子邮件ID和其他一些信息（例如某个产品ID）。假设文件中有数百万行数据。您需要将这些数据加载到数据库中。那么，您如何高效地去重数据（即消除重复项）？

- mnquasar

---

你的内存限制是什么？ - Edward Q. Bridges

假设它是2GB（32位机器）。 - mnquasar

你想对每一行上的其他信息做什么？ 你是想将数据规范化为主从表结构，还是只想为每个唯一电子邮件ID在单个表中保留一条记录？如果你只想做后者，那么每个唯一电子邮件ID的哪些行被放入数据库是否重要？ - ChrisH

@ChrisH：我猜你问的是<email1，prod1>和<email1，prod2>是否重复？我对这两种情况都很感兴趣。情况一：当<email1，prod1>和<email1，prod2>是重复时，即仅通过电子邮件ID检查重复项；情况二：当电子邮件ID和产品ID相同时，才算是重复。 - mnquasar

Answer 1

行数过多

• 使用Map&Reduce框架（例如Hadoop）。这是完整的分布式计算，除非您有TB级别的数据，否则这是一种过度设计。（开个玩笑：）

无法将所有行放入内存

• 即使结果也不适合：使用归并排序，将中间数据持久化到磁盘上。在合并时，您可以丢弃重复项（可能此示例会有所帮助）。如果需要，可以使用多线程。
• 结果适合：不要将所有内容读入内存，然后将其放入HashSet中（请参阅下文），而是可以使用行迭代器或其他方式，并继续添加到此HashSet中。您可以使用ConcurrentHashMap并使用多个线程读取文件并将其添加到此Map中。另一个多线程选项是使用ConcurrentSkipListSet。在这种情况下，您将实现compareTo()而不是equals()/hashCode()（compareTo()==0表示重复），并继续添加到此SortedSet中。

适合内存

• 设计一个包含您的数据的对象，实现良好的equals()/hashCode()方法，并将它们全部放入HashSet中。
• 或者使用上述方法（您可能不想持久化到磁盘中）。

如果我是您，我仍然会在数据库上放置唯一约束条件...

- Enno Shioji

---

我认为这几乎涵盖了所有内容。 - Gareth Davis

我喜欢基于文件的归并排序解决方案。谢谢Zwei。 - mnquasar

Answer 2

我会从显而易见的答案开始。创建一个哈希表，将电子邮件ID作为键，将其余信息放入值中（或创建一个对象来保存所有信息）。当您到达新行时，请检查键是否存在，如果存在，请移动到下一行。最后，使用HashMap编写出所有SQL语句。我同意eqbridges的观点，如果您有“无数”行，则内存限制将非常重要。

- TheSteve0

---

我更喜欢在数据库端处理完全重复的数据。在应该是唯一的列上设置UNIQUE约束。您可以随意运行INSERT，而重复项将会失败。此外，您可以查询接受的数据以查找相似之处，并根据需要进行更新。内存需求将相对较小。 - Dolph

你可以使用 HashSet 而不是依赖于 Map。 - Edward Q. Bridges

我确实更喜欢DB的答案，但我同意最初处理行可能会更慢，但总体而言，我打赌它会大致相同。您可以在事务中执行所有插入语句，如果失败，只需回滚即可。这肯定会提供更多的灵活性，并避免内存问题。Dolph，你应该把它留作答案，这样我就可以投票支持了。 - TheSteve0

我所看到的唯一问题是使用单个事务时，如果遇到一个重复项，你不能消除它，只能放弃整个批处理。 - PSpeed

非常抱歉 - 我在评论中表达得一点都不清楚。我的意思是每个插入操作都有自己的事务。因此，您将执行数百万个事务 - 而不是一个大事务。 - TheSteve0

感谢大家的回答。但我认为问题并不简单。首先，是否有可能将整个数据保留在内存中（HashSet）...请记住，有数百万行...即使在此之前，您能否将文件加载到内存中？我猜整个文件不需要在内存中，读取器会一次缓冲读取几个块（行）...所以我们可能已经解决了这个问题？...但是有没有办法使基于HashSet/Map的方法更有效？ - mnquasar

Answer 3

你有两个选择：

1. 用Java实现：你可以像组合一个HashSet一样进行测试 - 对于每个输入项，如果它不存在于集合中，则添加一个电子邮件ID。

2. 在数据库中实现：在表上放置唯一约束条件，这样重复项就不会被添加到表中。这样做的额外好处是，您可以重复此过程并从以前的运行中删除重复项。

- akf

---

对于第二个问题，加载可能会被唯一约束条件的违反所中断。根据集合的大小和重复项的数量，这可能会不必要地增加加载时间。 - Edward Q. Bridges

是的，这是唯一约束方法存在的问题...虽然我喜欢这个想法...但你必须捕获唯一约束异常才能避免中断。 - mnquasar

Answer 4

看看Duke(https://github.com/larsga/Duke)，这是一个用Java编写的快速去重和记录链接引擎。它使用Lucene进行索引并减少比较数量（以避免不可接受的笛卡尔乘积比较）。它支持最常见的算法（编辑距离、Jaro Winkler等），非常可扩展和可配置。

- Fabrizio Fortino

Answer 5

你能不能不用电子邮件和产品ID作为索引来建立表格？这样，通过索引进行读取时，重复的电子邮件或电子邮件+产品ID可以通过顺序读取并匹配前一个记录轻松地被识别出来。

- Lawrence Dol

Answer 6

你可以使用提取、转换、加载（ETL）方法来解决你的问题：

• 将数据加载到导入模式中；
• 对数据进行任何想要的转换；
• 然后将其加载到目标数据库模式中。

你可以手动完成这个过程，也可以使用ETL工具。

- Thomas Jung