java - 对非常大的数据进行重复检测

Question

我是 Java 的新手，所以如果我做错了什么，请原谅我。

我正在做一个项目，我需要快速扫描大量数据(CSV 有 5000 万行或更多行，每行 5 个条目)以查找重复项。我求助于使用 HashMap，因为它的 .contains() 方法很快。

但是，我最终不得不在 map 中存储一百万个或更多键。每个键都与一个 int[] 数组相关联，该数组也有 1 到 100 个条目。很明显，除非我使用的笔记本电脑具有约 16 GB 的 RAM，否则我最终会收到 OutOfMemory 错误。

我在想，一旦 HashMap 获得超过 N 个键或一个键获得超过 N 个条目，我可以将它写在某个地方并清除它。但是，并不是所有的键或值都一次找到，所以我需要能够添加到写入的 HashMap 中，而不是覆盖它。

我搜索了很远，仍然找不到办法，所以非常感谢任何能提供帮助的人!

Answer 1

这里有很多选项，我将列出其中的一些:

1. 更多内存:听起来您已经尝试过为 Java 提供更多内存，但如果没有，请使用 -Xmx compiler flag - 例如-Xmx3G正如 Dimitry 所建议的那样，将为您提供 3 GB 的堆，而默认值 <= 1GB。

2. 存储较少的数据:您当前正在存储“1 到 100 个条目”的整行，而我们真正需要的只是知道数据是否唯一。 Arrays.hashCode() 函数为您提供了一个相当准确的指示，表明一行在单个 int 中是唯一的。 ，因此我们可以使用它来限制您需要在内存中保存的数据量:

   1. 构建两个HashSet<Integer>对象，称为 seen和 seenTwice .遍历你的数据，并将每个数组的散列添加到 seen , 和 seenTwice如果它已经在 seen 中，像这样:

      int[] arr = ... // construct the row's array
      int hash = Arrays.hashCode(arr);
      if(!seen.add(hash)) {
        // add returns false if we've already seen this hash
        seenTwice.add(hash);
      }
      

   2. 现在我们有一组我们见过两次或更多次的散列；理论上，这将比我们文件中的行数小得多。我们可以让seen收集垃圾，并使用 seenTwice 重新读取文件填充 HashSet<int[]> rows实际数据，就像您第一次尝试做的那样:

      int[] arr = ... // construct the row's array
      int hash = Arrays.hashCode(arr);
      if(seenTwice.contains(hash)) {
        // If the hash isn't in seenTwice, we know it's not a duplicate
        if(!rows.add(arr)) {
          System.out.println("Row "+Arrays.toString(arr))+" is a duplicate!");
        }
      }
      

3. 使用 Bash:如果您愿意放弃 Java，您可以使用基本的 bash 命令非常容易找到重复项:

   cat filename | sort | uniq -d
   

4. 使用数据库:正如您所暗示的那样，您可以使用一些内存不足的解决方案，尤其是数据库。一个好的、易于使用的 Java 数据库是 H2 ，但涵盖使用它超出了这个答案的范围。可以这么说，您可以将文件中的数据加载到数据库中，然后简单地查询重复行:Finding duplicate values in a SQL table

   但是，仅仅为了在 5000 万行中查找重复项而设置数据库未免太过分了。我不推荐这个选项。

---

另请参阅:Script to find duplicates in a csv file