java - 在预处理的大文本文件中搜索一行

Question

我有一个包含 100,000 多行的数据文件，每行仅包含两个字段，键和值以逗号分隔，并且所有键都是唯一。我想从此文件中按键查询值。将它加载到 map 是毫无疑问的，因为这会消耗太多内存(代码将在嵌入式设备上运行)而且我不希望涉及数据库。到目前为止，我所做的是在我的 PC 中预处理文件，即对行进行排序，然后在预处理文件中使用二进制搜索，如下所示:

public long findKeyOffset(RandomAccessFile raf, String key)
            throws IOException {
        int blockSize = 8192;
        long fileSize = raf.length();
        long min = 0;
        long max = (long) fileSize / blockSize;
        long mid;
        String line;
        while (max - min > 1) {
            mid = min + (long) ((max - min) / 2);
            raf.seek(mid * blockSize);
            if (mid > 0)
                line = raf.readLine(); // probably a partial line
            line = raf.readLine();
            String[] parts = line.split(",");
            if (key.compareTo(parts[0]) > 0) {
                min = mid;
            } else {
                max = mid;
            }
        }
        // find the right line
        min = min * blockSize;
        raf.seek(min);
        if (min > 0)
            line = raf.readLine();
        while (true) {
            min = raf.getFilePointer();
            line = raf.readLine();
            if (line == null)
                break;
            String[] parts = line.split(",");
            if (line.compareTo(parts[0]) >= 0)
                break;
        }
        raf.seek(min);
        return min;
    }

我认为有比这更好的解决方案。谁能给我一些启发？

Answer 1

数据是不可变的，键是唯一的(如问题评论中所述)。

一个简单的解决方案:编写您自己的散列代码以将键与行号映射。

这意味着，保留排序，而是按照哈希算法告诉的顺序将数据写入文件。

当查询键时，您对键进行哈希处理，获取特定的行号，然后读取值。

理论上，您的问题有 O(1) 的解决方案。

---

确保散列算法具有较少的冲突，但我认为根据您的具体情况，一些冲突应该没问题。示例:3 个键映射到相同的行号，因此您将所有三个键都写在同一行上，并且当搜索到任何冲突的键时，您将从该行读取所有 3 个条目。然后在整行上进行线性搜索(在本例中又称为 O(3) 或常数时间)。