java - 使用 HashMap 而不是数组是否有空间开销？

Question

我试图实现一个 trie 并在示例实现中读到，使用大小为 26 的小数组来存储子项会更节省空间，因为这样您就不必使用 HashMap 浪费空间(代码是用 Java 编写的，如果这有什么区别的话)

但是，由于您不一定需要存储所有 26 个值，所以 map 不是更节省空间吗？或者，包含 Character 对象作为键的 HashMap 对象是否只是需要更多空间，因为简单的 int[] 类型不会在后台使用这些更复杂对象的实现将使用的额外空间？

只是想检查一下这个人是否弄错了，或者使用 HashMap 等对象类型是否涉及一些我应该注意的开销。

Answer 1

HashMap 存储键和值，因此如果您要使用 HashMap 实现 trie，则不仅会存储值，还会存储键。如果您使用数组，那么键实际上是数组中值的索引，因此您不必将其存储在任何地方。

除此之外， HashMap 的空间效率比数组低，因为它们的负载因子始终小于 1，这相当于它们保留了比需要的更多的条目，因为他们的工作方式。我不会对此进行扩展，因为它与您的问题无关，但如果您好奇，请搜索 HashMap 负载因子。