四叉树与哈希映射表

Question

我考虑将HashMap作为QuadTree的后备结构。我相信我可以使用莫顿序列来唯一地标识我感兴趣的每个方块。我知道我的QuadTree最多会有16层。根据我的计算，这将导致一个65,536 x 65,536的矩阵，这应该至多给我4,294,967,296个单元格。有人知道这对于HashMap来说是否太多了吗？我总是可以编写一个使用树的QuadTree，但我认为使用HashMap可以获得更好的性能。

高度为1的莫顿序列==（2x2）== 4

高度为2的莫顿序列==（4x4）== 16

高度为3的莫顿序列==（8x8）== 64

用于最大高度为3的树的莫顿序列示例。

以下是我知道的内容：

• 我将在已知矩形区域内获得经纬度数据。
• 数据不会完全覆盖整个区域，并且很可能会被合并成该区域的某些部分。（最坏情况是所有4,294,967,296个单元格中都有数据）
• 数据的分辨率最终会将该区域分解为65k x 65k的矩形。
• 我还知道，插入/更新数据的查询很可能是10比1。

- Justin

---

你所说的“可能会得到10比1的查询来插入/更新数据”是什么意思？你是指查找比插入操作多10倍吗？ - Dave

@Dave 是的，我认为目前是这样的。 - Justin

Answer 1

哈希表不是一个好的选择。有一种更好的解决方案，用于导航系统：

为每个四叉树单元格分配一个字母：A（左上角），B（右上角），C和D。

现在您可以通过一个字符串寻址每个四叉树单元格：

ABACE：这标识了第5级中的单元格。（A-> B-> A-> C-> E）搜索互联网以获取有关该特定四叉树编码的详细信息。

不要忘记：您决定子分割规则（何时将单元格细分为更小的单元格），这决定了您获得的单元格数量。您给出的数字远远过高。这只是一个理论计算，让我想起了Google Maps Quad树的1:1。

此外，重要的是要知道您的应用程序需要哪种类型的四叉树：

点四叉树、区域四叉树（边界框）、线四叉树。

如果您知道任何现有的Java四叉树实现，请发表评论或编辑此答案。

此外，您不能实现通用解决方案。
您必须大致知道您将支持多少元素。 理论最大值并不等于预期最大值，这不是一个好的方法。

您必须知道这一点，因为您必须决定是否将其存储在主内存中或磁盘上，这也会影响四叉树的结构。 "ABCD"解决方案适用于从磁盘动态加载。

Google方法将图像存储在四叉树中，这与您要存储的点不同，因此我怀疑您的计算是否现实。

如果您想存储世界上所有国家的所有街道，则可以估计该数字，因为已知点的数量（OpenStreetMap、TomTom（Teelatlas）或（Nokia Maps）Navteq）。

如果您意识到您必须将四叉树存储在磁盘上，则可能大小是开放的，并且仅受磁盘空间限制。

- AlexWien

Answer 2

我认为将Quad Tree实现为Tree会给你更好的结果。实际上，在HashMap中实现如此大的数据库无论如何都是一个坏主意。因为如果有很多碰撞，HashMap的性能会严重下降。

而且显然你知道自己有多少数据。在这种情况下，HashMap完全是多余的。HashMap是用于当您不知道有多少数据时。但在这种情况下，您知道树的每个节点都有四个元素。那么为什么还要使用HashMap呢？

此外，您的表显然至少有4GB大小。在大多数系统上，它刚好适合您的内存。由于还有Java VM开销，为什么要将其存储在内存中？最好找到一种适用于磁盘的数据结构。对于空间数据（我假设您正在使用四叉树），一种这样的数据结构是R-Tree。

- kokx

---

我其实不知道我会有多少数据，但我知道我最多可以有多少数据。如果 HashMap 不起作用，我考虑使用 QuadTree 或 B-Tree。 - Justin

Answer 3

哇，我们一下子得到了许多概念。首先，你想要达到什么目的？存储四叉树？单元格矩阵？哈希查找？

如果你想要一个四叉树，为什么要使用哈希映射？你知道每个节点最多可能有4个子节点。哈希映射对于需要快速查找任意数量的键值映射非常有用。如果你只有4个，哈希甚至可能不重要。此外，虽然你可以嵌套映射，但这有点笨拙。最好使用某些数据结构或编写自己的数据结构。

此外，你想通过四叉树实现什么目的？快速查找矩阵中的单元格？在那种情况下，一些坐标映射函数可能更适合你。

最后，我关心的不是哈希映射中节点的数量，而是它本身的数量。即使每个单元格只有一个字节，65536²个单元格也会占用4 GiB的内存。

我认为最好回到问题“我的目标是什么”，然后找出哪些数据结构可以帮助你实现目标（考虑查找等要求），同时设法将其放入内存中。

- G_H

---

好的，从目标开始。我将在已知矩形区域内获得纬度/经度数据。数据不会完全覆盖整个区域，并且可能会在该区域的某个地方被合并成块。数据的精度最终会将该区域分解为65k x 65k的矩形。我还知道我可能会获得10到1的查询来插入/更新数据。 - Justin

@Justin 根据潜在空间中可能有多少数据，这似乎很可能符合稀疏矩阵的条件。该数据结构的维基百科页面上列出了一些存储策略：http://en.wikipedia.org/wiki/Sparse_matrix#Storing_a_sparse_matrix - G_H

是的，我看到了稀疏矩阵，并在boost中找到了一种使用映射作为其内部数据结构的实现。这是我想在Java中使用HashMap的一个原因。 - Justin

@G_H 稀疏矩阵是胡说八道，四叉树才是正解，它具有稀疏特性。 - AlexWien

在地理空间领域中，有众所周知的结构来处理这个任务。没有必要使用不具体的概念，如稀疏矩阵，因为存在详细的概念，它们被称为地理空间索引。通常是“四叉树、kd树”之一。而四叉树不是稀疏矩阵，kd树也不是。 - AlexWien

Answer 4

出于空间和速度的原因，建议直接使用链接节点。

对于如此大的数据，我会避免使用Java。你会不断地受到垃圾收集器的限制。选择更接近机器的语言：C或C++、Pascal/Delphi、Ada等。

将四个子节点指针放入数组中，以便您可以将叶子作为2位索引的打包数组引用（这是使用Ada的一个好理由，它将允许您在不进行任何位操作的情况下定义这样的事物）。我想这就是莫顿序列。我不知道那个术语。

这种索引子节点的方法本身就是避免Java的原因。在节点类实例中包括子数组将使您付出指针加上数组大小字段的代价：每个节点多8或16字节，在其他某些语言中不需要这些字节。对于40亿个单元，则非常浪费空间。

实际上，你应该做一下数学计算。如果使用隐式叶子单元格，仍需要表示10亿个节点。如果使用32位索引来引用它们（为了节省内存而不是64位指针），则每个节点的最小值为16字节。假设节点属性只有4字节。那么即使没有任何Java开销，一个完整的树也需要20 GB 的空间。

最好有足够的RAM预算。

- Gene

---

在Java中，您不需要使用子数组，只需使用4个字段：从nw到se。 - AlexWien

Answer 5

虽然大多数传统的四叉树只是使用带有四个子节点指针的节点进行遍历，而没有任何哈希映射的提及。但是，我们也可以编写一个有效的类四叉树空间索引方法，将所有节点存储在一个大哈希映射中。

好处是，通过使用莫顿序列或其他类似生成的值作为键，您可以通过只有一个指针解除引用来检索任何级别的节点。

在“传统”的四叉树实现中，由于重复的指针解除引用而导致缓存未命中，这成为主要瓶颈。因此，如果编码坐标空间和获取哈希的成本低于沿搜索路径解除引用节点指针的成本，这样的实现可能会更快。特别是如果地图很深（需要高精度的稀疏位置）。

实际上，您并不需要使用莫顿序列，并且在执行此操作时几乎无需将其视为四叉树。下面是一个非常简单的示例实现：

为了检索某个级别的四叉树，请使用{x，y，level}作为哈希映射键，其中x和y被量化到该级别。如果要在同一地图中存储多个级别，则只需在键中包含级别即可。

这是否仍然是四叉树有待讨论，但功能是相同的。

- Jostein