如何在 java 中有效地访问半稀疏数据？

Question

所以我正在处理一个问题，我正在将一个大文本文件解析为数据 - 文件的每一行都由一个具有多个数据字段的 Node 对象表示。

在程序执行期间，这些对象将根据它们的int id字段（在文本文档中指定）被多次访问。

如果每个 id 都存在，我会简单地将它们存储为 Node[] 数组，并且想要使用 id x 访问节点，我会简单地使用 nodeArray[x].

但是，数据表明 id 的大多数值都不存在。对于我当前的数据集，集合中只有大约 40-50% 的 id 介于 0 和集合中最大的 id、ID_MAX 之间。

依我看，我有两个选择：

使用包含许多未填写条目的大型 Node[]，如

Node[] nodeArray = new Node[ID_MAX];

BufferedReader br = new BufferedReader(new FileReader(file));
String line;

while((line = br.readLine()) != null) {
    Node n = ... // parse line of text into Node object
    nodeArray[n.getID()] = n;
end
br.close();

这将使访问具有特定 id 的节点变得微不足道，但在数据集很大的情况下会使用很多额外的 space。

另一种选择是使用较小的 Node[] 数组并使用稀疏 int[] 数组进行索引：

Node[] nodeArray = new Node[NUM_ROWS];
int[] indexArray = new Int[ID_MAX];

BufferedReader br = new BufferedReader(new FileReader(file));
String line;
int i = 0;

while((line = br.readLine()) != null) {
    Node n = ... // parse line of text into Node object
    nodeArray[i] = n;
    indexArray[n.id] = i;
    i++;
}

两者中的任何一个总体上是否比另一个更好，还是取决于数据的大小和稀疏性？有没有其他我没有考虑过的比这两种方法都更好的方法？

Answer 1

根据您在此处描述的内容，您可以使用 HashMap<Integer, Node> 或 HashMap<Long, Node>，具体取决于您拥有的 ID 范围。

根据您的其他要求，LinkedHashMap 和 TreeMap 可能是备选方案（LinkedHashMap 如果您需要按照插入的顺序遍历节点，TreeMap 如果您需要按某些特定条件对它们进行排序）。

如何在 java 中有效地访问半稀疏数据？

How can I access semi-sparse data efficiently in java?

java

arrays

indexing