java - 存储二维数据的数据结构的想法？

Question

我有一个大的二维网格，x-by-y。应用程序的用户将在该网格上添加有关特定点的数据。不幸的是，网格太大而无法实现为大型 x-by-y 数组，因为运行它的系统没有足够的内存。

什么是实现此目的的好方法，以便只有添加了数据的点才存储在内存中？

我的第一个想法是创建数据点的 BST。将使用诸如“(long)x<<32 + y”的哈希函数来比较节点。

然后我得出结论，如果没有很好地平衡，这可能会降低效率，所以我想出了一个由可比较的 BST 点组成的 BST 的想法。外部 BST 将根据它们的 x 值比较内部 BST。内部 BST 将通过它们的 y 值比较点(并且它们都将具有相同的 x)。因此，当程序员想查看 (5,6) 处是否有一个点时，他们会向外部 BST 查询 5。如果该点存在内部 BST，则程序员将向内部 BST 查询 6。结果将是被退回。

你能想出更好的实现方法吗？

编辑:关于 HashMap:大多数 HashMap 都需要一个数组来进行查找。有人会说“data[hash(Point)] = Point();”设置一个点，然后通过散列找到索引来找到该点。然而，问题是数组必须是散列函数范围的大小。如果此范围小于添加的数据点总数，则它们要么没有空间，要么必须添加到溢出中。因为我不知道要添加的点数，所以我必须假设这个数字小于某个数量，然后将数组设置为该大小。同样，这会实例化一个非常大的数组(尽管如果假设数据点少于 x*y，则比原来的要小)。我希望该结构随数据量线性扩展，并且在空时不会占用大量数据。

看起来我想要的是一个 SparseArray，正如一些人提到的那样。它们的实现方式是否与在 BST 中包含 BST 类似？

Edit2: Map<> 是一个接口(interface)。如果我要使用 map ，那么看起来 TreeMap<> 是最好的选择。所以我最终会得到 TreeMap< TreeMap< Point>>，类似于人们提出的 Map< Map< Point>> 建议，它基本上是 BST 中的 BST。不过，感谢您提供的信息，因为我不知道 TreeMap<> 基本上是 BST 的 Java SDK。

Edit3:对于那些可能关心的人来说，选择答案是最好的方法。首先，必须创建一个包含 (x,y) 并实现可比性的 Point 类。 Point 可能与 (((long)x)<<32)+y 之类的东西进行比较。然后将 TreeMap 每个指向数据。搜索它是有效的，因为它在平衡树中，所以 log(n) 成本。用户还可以使用 TreeMap.entrySet() 函数查询所有这些数据，或遍历这些数据，该函数会随数据一起返回一组点。

总而言之，这允许实现稀疏数组的空间高效和搜索高效的实现，或者在我的例子中，二维数组也可以有效地迭代。

Answer 1

要么 Quadtree , 一个 k-d-tree或 R-tree .

将大点数组的索引存储到其中一个空间结构中。如果数据不是均匀分布的，那么这种空间结构是有利的，比如地理数据集中在城市，没有指向大海。

想一想你是否可以忘记规则网格，而继续使用四叉树。
(想一想，为什么需要规则网格？规则网格通常只是一种简化)

在任何情况下都不要使用对象来存储点。这样的对象只需要 20 个字节，因为它是一个对象!对于庞大的数据集来说，这是个坏主意。

int x[] 和 int[] y 或 int[]xy 数组与内存使用情况相关。

考虑阅读

Hanan Samet's "Foundations of Multidimensional Data Structures"

(至少是介绍)。