我正在考虑使用 HashMap 作为 QuadTree 的支持结构。我相信我可以使用 Morton 测序来唯一识别我感兴趣的区域的每个方格。我知道我的 QuadTree 的高度最多为 16。根据我的计算，这将导致一个 65,536 x 65,536 的矩阵，它最多应该给我 4,294,967,296 个单元格。有谁知道 HashMap 的元素是否太多？我总是可以使用 Tree 编写 QuadTree，但我认为使用 HashMap 可以获得更好的性能。
高度 1 == (2x2) == 4 的莫顿序列
高度 2 == (4x4) == 16 的莫顿序列
高度 3 == (8x8) == 64 的莫顿序列
最大高度为 3 的树的 Morton 测序示例。
这是我所知道的：
Hashmap 不是一个好主意。有一个更好的解决方案，用于导航系统：
为每个四叉树单元分配一个字母：A（左，上）、B（右，上）、C 和 D。
现在您可以通过字符串对每个四边形单元格进行寻址：
ABACE：这标识了第 5 级中的单元格。（A->B->A->C->E）在互联网上搜索有关该特定四叉树编码的详细信息。
不要忘记：您决定细分规则（何时将一个单元格细分为较小的单元格），这决定了您获得多少个单元格。你给的数字太高了。这只是一个理论计算，它让我想起了谷歌地图四叉树上的 1:1。
此外，了解您的应用程序需要哪种类型的四叉树也很重要：
点四叉树、区域四叉树（边界框）、线四叉树。
如果您知道 java 中任何现有的 Quadtree 实现。请发表评论，或编辑此答案。
此外，您无法实施一个适用于所有解决方案的解决方案。
你必须知道你将支持多少元素。不等于预期最大值的理论最大值不是一个好方法。
您必须知道，因为您必须决定是将其存储在主存储器还是磁盘上，这也会影响四叉树的结构。“ABCD”解决方案适用于从磁盘动态加载。
谷歌方法将图像存储在四叉树中，这与您要存储的点不同，所以我怀疑您的计算是否现实。
如果你想存储世界上所有国家的所有街道，你可以估计这个数字，因为点的数量是已知的（OpenStreetMap、TomTom (Teelatlas) 或 (Nokia Maps) Navteq.
如果您意识到必须将四叉树存储在磁盘上，那么可能大小是开放的，并且仅受磁盘空间的限制。
我认为将四叉树实现为树会给你带来更好的结果。无论如何，实际上在 HashMap 中实现这么大的数据库是一个坏主意。因为如果你有很多冲突，HashMap 的性能会严重下降。
显然，您确切地知道您拥有多少数据。在这种情况下，HashMap 是完全多余的。HashMap 适用于您不知道有多少数据的情况。但是在这种情况下，您知道树的每个节点都有四个元素。那么，为什么还要费心使用 HashMap。？
此外，您的表显然至少有 4GB 大。在大多数系统上，这几乎不适合您的记忆。既然还有 Java VM 开销，为什么要把它存储在内存中呢？最好找到在磁盘上运行良好的数据结构。一种用于空间数据的数据结构（我假设您拥有，因为您使用的是四叉树），是R-Tree。
哇，我们在这里一下子得到了许多概念。首先，你想达到什么目的？存储四叉树？细胞矩阵？哈希查找？
如果你想要一个四叉树，为什么要使用哈希映射？您知道每个节点最多可以有 4 个子节点。哈希映射对于需要快速查找的任意数量的键值映射很有用。如果您只有 4 个，那么哈希可能甚至都不重要。此外，虽然您可以嵌套地图，但它有点笨拙。您最好使用一些数据结构或编写自己的数据结构。
另外，你想用四叉树达到什么目的？快速查找矩阵中的单元格？一些坐标映射功能可能会更好地为您服务。
最后，我并不太担心哈希图中的节点数量，因为我只是担心数量本身。即使每个单元一个字节，65536² 个单元最终也会成为 4 GiB 的内存。
我认为最好一直回到“我对这些数据的目标是什么”这个问题，然后找出哪些数据结构可以帮助您解决这个问题（牢记查找等要求），同时设法适应它在记忆中。
出于空间和速度的原因，绝对使用直接链接的节点。
有了这么大的数据，我会完全避免使用 Java。您将不断受到垃圾收集器的摆布。选择更接近金属的语言：C 或 C++、Pascal/Delphi、Ada 等。
将四个子指针放在一个数组中，这样您就可以将叶子称为 2 位索引的打包数组（使用 Ada 的一个很好的理由，它可以让您定义这些东西，而无需任何摆弄）。我猜这是莫顿测序。我不知道那个词。
这种索引子项的方法本身就是避免使用 Java 的一个原因。在节点类实例中包含子数组将花费您一个指针加上一个数组大小字段：每个节点 8 或 16 个字节，这在某些其他语言中是不需要的。有 40 亿个细胞，这已经很多了。
事实上，你应该做数学。如果您使用隐式叶单元，您仍然有 10 亿个节点要表示。如果您使用 32 位索引来引用它们（以节省内存而不是 64 位指针），则每个节点的最小值为 16 个字节。说节点属性只有 4 个字节。那么即使没有任何Java 开销，你也有 20 GB 的空间来存储一棵完整的树。
最好有一个良好的 RAM 预算。
确实，大多数典型的四叉树将简单地使用具有四个子节点指针的节点并遍历它，而没有提及哈希图。但是，也可以编写一种高效的四叉树式空间索引方法，将其所有节点存储在一个大哈希图中。
好处是通过使用 Morton 序列（或另一个类似生成的值）作为键，您只需一个指针取消引用即可检索任何级别的节点。
在“传统”四叉树实现中，由于在查找节点时重复指针取消引用，我们会出现缓存未命中，这成为主要瓶颈。因此，如果编码坐标空间和获得哈希的成本低于沿搜索路径取消引用节点指针的成本，这样的实现可能会更快。特别是如果地图非常深（具有需要高精度的稀疏位置）。
您实际上并不需要 Morton 序列，并且在执行此操作时几乎不需要将其视为四叉树。一个非常简单的示例实现：
为了检索某个级别的四边形，请使用{ x, y, level }作为 hashmap 键，其中 x 和 y 被量化到该级别。如果您在同一个地图中存储多个级别，则只需在键中包含该级别。
这是否仍然是四叉树还有待讨论，但功能是相同的。