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

Question

我有一个场景，我必须比较 2 个地图。我必须获取源 Map 的键并遍历目标 Map 以获得等于的键，然后比较它们的值。问题是这些地图应该保存非常多（>=10,000,000）的记录量。所以我无法将这些地图保存在内存中。

可能的解决方案：

将两者都存储为文本文件 "key=value"

问题：

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

可能的解决方案： 将文本文件存储为 "key=value" 并为目标

创建 id=> 行号的索引

问题：

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

可能的解决方案：

将两者都存储在数据库中

问题：

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

可能的解决方案：

使用mapDB

问题：

试过了，但是在 260,000 条记录后失败了。它给出了 Writer thread failed 异常，主要是因为我使用的是 32 位 JVM。所以我想自己编写实现而不是依赖 MapDB。

我如何有效地 store/retrieve 并比较键值映射，以便在我进行比较时不会对性能造成太大影响。在任何时候我都不能将任何东西带入内存，因为它会给出内存不足异常。该解决方案应该读取和写入磁盘，而不是内存 - 我没有 12 GB 的 RAM。该解决方案也适用于 32/64 位系统

Answer 1

一个相当简单的选项：

将地图放到磁盘上
对它们进行排序（以多种方式中的任何一种）
为每个地图打开一个reader，并阅读第一行
遍历每个地图的行，根据 "current" 个键的比较决定从哪个地图读取。

这样一来，您一次只需要内存中的两 key/value 对。

例如，假设我们有一个包含键 A、B、H、I 的 "source" 映射和一个包含键 B、C、I、J 的 "target" 映射。该过程看起来像这个：

读取源=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();
    }
}

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

Java Store and compare huge key value pair maps on disk

java

key-value

key-value-store