在磁盘上存储和比较巨大的键值对映射

Question

我有一个场景，我必须比较2个地图。我必须获取源Map的一个键，并遍历目标Map以获得for equals的键，然后比较它们的值。问题是这些map应该保存非常高(>=10,000,000)的记录量。所以我不能在内存中保存这些映射。

可能的解决方式:

以"key=value"格式将两者存储为文本文件

问题:

我们必须为源文件中的每个键值遍历目标Map文本文件，这既无效又耗时。

可能的解决方式:将两者存储为文本文件"key=value"，并为目标

创建id=>行号的索引

问题:

没有有效的方法根据行号从大文本文件中直接读取一行。有些方法使用Java 1.8的api，它们同样需要将文件加载到内存中

可能的解决方式:

在数据库中存储

问题:

在这种情况下，我们必须为每个键值查询数据库。如果我们在源和目标中有100万个键，我们必须查询100万次。无效且耗时

可能的解决方式:

使用mapDB

问题:

尝试了这个，但是在26万条记录之后失败了。它给出了一个Writer线程失败异常，主要是因为我使用的是32位JVM。所以我想自己写实现，而不是依赖于MapDB。

我如何有效地存储/检索和比较键值映射，以便它不会影响性能，当我做比较。在任何时候，我不能把任何东西到内存中，因为它会给内存不足的异常。解决方案应该读写磁盘，而不是内存——我没有12 GB的RAM。此外，该解决方案应该适用于32/64位系统

Answer 1

一个相当简单的选择:

• 把地图放到磁盘上
• 对它们进行排序(以多种方式中的任何一种)
• 为每个地图打开阅读器，并读取第一行
• 遍历每个map的行，根据"当前"键的比较决定从哪个map读取。

这样在任何时候你只需要两个键/值对在内存中。

例如，假设我们有一个包含键a、B、H、I的"源"映射和一个包含键B、C、I、j的"目标"映射，流程如下:

• 读取源=A，目标=B
• 比较:源在目标之前，所以从源(B)中读取另一行
• 比较:源键和目标键相等，因此处理B的条目，并从每个(源=H，目标=C)中读取另一行
• 比较:目标在源之前，所以从目标(I)中读取另一行
• 比较:源在目标之前，所以从源(I)中读取另一行
• 比较:源键和目标键相等，因此处理I的条目，并从每个(源=空，目标=J)中读取另一行
• 由于我们已经从数据源中耗尽了数据，我们完成了

Answer 2

感谢@Jon的算法。这是我对这个问题的实现。如果有任何错误或可以改进的地方，请告诉我。

package controller;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
public class ReadAndCompareMapOnDisk {
    public static void main(String args[]) {
        final String newLine = "n";
        String sourceSortedFile = "C:\TestData\SourceSorted.txt";
        String targetSortedFile = "C:\TestData\TargetSorted.txt";
        String matchedOutputFile = "C:\TestData\OutputMatched.txt";
        String sourceNotPresentInTarget = "C:\TestData\OutputSourceUnMatched.txt";
        String targetNotPresentInSource = "C:\TestData\OutputTargetUnMatched.txt";
        String keyValueSeparator = "=";
        BufferedReader sourceReader;
        BufferedReader targetReader;
        BufferedWriter matchedWriter;
        BufferedWriter sourceUnMatchedWriter;
        BufferedWriter targetUnmatchedWriter;
        try {
            sourceReader = new BufferedReader(new FileReader(new File(sourceSortedFile)));
            targetReader = new BufferedReader(new FileReader(new File(targetSortedFile)));
            matchedWriter = new BufferedWriter(new FileWriter(new File(matchedOutputFile)));
            sourceUnMatchedWriter = new BufferedWriter(new FileWriter(new File(sourceNotPresentInTarget)));
            targetUnmatchedWriter = new BufferedWriter(new FileWriter(new File(targetNotPresentInSource)));
            String sourceLine = "";
            String targetLine = "";
            String sourceKey = "";
            String targetKey = "";
            String sourceValue = "";
            String targetValue = "";
            int matchedCounter = 0;
            int sourceUnMatchedCounter = 0;
            int targetUnmatchedCounter = 0;
            System.out.println("Started");
            boolean isReadSource = true;
            boolean isReadTarget = true;
            while (true) {
                if (isReadSource == true) {
                    sourceLine = sourceReader.readLine();
                }
                if (isReadTarget == true) {
                    targetLine = targetReader.readLine();
                }
                if (sourceLine == null) {
                    while (targetLine != null) {
                        targetUnmatchedWriter.write(targetLine + newLine);
                        targetLine = targetReader.readLine();
                    }
                    break;
                }
                if (targetLine == null) {
                    while (sourceLine != null) {
                        targetUnmatchedWriter.write(sourceLine + newLine);
                        sourceLine = sourceReader.readLine();
                    }
                    break;
                }
                sourceKey = sourceLine.split(keyValueSeparator)[0];
                targetKey = targetLine.split(keyValueSeparator)[0];
                int result = sourceKey.compareTo(targetKey);
                if (result < 0) {
                    // source before Target
                    sourceUnMatchedCounter++;
                    isReadSource = true;
                    isReadTarget = false;
                    sourceUnMatchedWriter.write(sourceLine + newLine);
                    if (sourceUnMatchedCounter % 1000 == 0) {
                        sourceUnMatchedWriter.flush();
                    }
                } else if (result > 0) {
                    // target before Source
                    targetUnmatchedCounter++;
                    isReadTarget = true;
                    isReadSource = false;
                    targetUnmatchedWriter.write(targetLine + newLine);
                    if (targetUnmatchedCounter % 1000 == 0) {
                        targetUnmatchedWriter.flush();
                    }
                } else {
                    // matched key
                    matchedCounter++;
                    sourceValue = sourceLine.split(keyValueSeparator)[1];
                    targetValue = targetLine.split(keyValueSeparator)[1];
                    matchedWriter.write("Key Matched for Matched - " + sourceKey + " and " + targetKey
                            + "Value Equals = " + (sourceValue.equals(targetValue) + "n"));
                    if (matchedCounter % 1000 == 0) {
                        matchedWriter.flush();
                    }
                    isReadSource = true;
                    isReadTarget = true;
                }
            }
            flushAndCloseWriters(sourceReader, targetReader, matchedWriter, sourceUnMatchedWriter,
                    targetUnmatchedWriter);
            System.out.println("Finished");
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
    private static void flushAndCloseWriters(BufferedReader sourceReader, BufferedReader targetReader,
            BufferedWriter matchedWriter, BufferedWriter sourceUnMatchedWriter, BufferedWriter targetUnmatchedWriter)
            throws IOException {
        targetUnmatchedWriter.flush();
        sourceUnMatchedWriter.flush();
        matchedWriter.flush();
        sourceUnMatchedWriter.close();
        targetUnmatchedWriter.close();
        matchedWriter.close();
        sourceReader.close();
        targetReader.close();
    }
}