java - 高效存储稀疏二维网格

Question

我有一张巨大的 map ，上面有瓷砖。这是一个地牢，所以显然有很多空白空间，我可以在其中存储空值。

显然，拥有一个巨大的二维数组是一种选择，但我认为这不是最优雅的选择。此外，当我想将其保存到文件时，存储大量的空标记并不是很整洁。

类似这样，但要大得多:

+--------------+
|   X     X    |
| XXX    XX    |
|   XXXXXXX    |
|    X   XX    |
|   XXX   XXX  |
|     X   X    |
+--------------+ 

除了宽×高数组，我还有哪些其他选择？

只有像 Map<IntCoord, Tile> 这样的东西？或者是否有针对类似场景的一些广泛使用的解决方案？

Answer 1

您可以使用三样东西:

1. 二维数组。
2. 列表。
3. map 。

二维数组是最好的，除非你的 map 很大，在这种情况下你可以使用列表。

---

二维数组:

优点:它具有最快的查找时间。

缺点:它(很可能)占用最多的内存。

查找时间可能大大超过内存成本。除非您的地牢有数十万格那么大，否则这可能是可行的方法。

---

列表(可能是 ArrayList):

优点:只存储您需要的元素。

缺点:查找时间非常糟糕。

虽然列表会使用较少的内存，但查找图 block 或项目会花费更长的时间，因为您必须遍历列表才能找到与位置匹配的内容。

---

Map(可能是 HashMap):

优点:每个位置都将链接到每个 map 的一个对象，因此查找时间还可以。

缺点:查找时间不会是最佳的，会使用适量的内存。

映射介于列表和数组之间。与数组相比，它们会占用更多内存，但查找时间比列表短。

---

由于查找时间短，二维数组是最好的。在大多数现代计算机上，内存不是问题。如果是，您始终可以缓存当前未用于文件的区域并根据需要动态加载它们。