java - 内存效率: HashMap versus Array

Question

我正在考虑以下情况:我想计算字符串中字符的出现次数(例如用于排列检查)。

一种方法是分配一个包含 256 个整数的数组(我假设字符是 UTF-8)，用零填充它，然后遍历字符串并递增相应数组位置上的整数为字符的 int 值。

但是，对于这种方法，您每次都必须分配一个 256 数组，即使分析的字符串非常短(因此仅使用数组的一小部分)。

另一种方法是使用字符到整数哈希表并为每个遇到的字符存储一个数字。这样，您就只能拥有字符串中实际存在的字符的键。

由于我对 HashTable 的理解相当理论化，而且我真的不知道它是如何在 Java 中实现的，所以我的问题是:这两种方法中哪一种的内存效率更高？

编辑:

在讨论这个问题的过程中(谢谢大家的回答)我确实意识到我对UTF-8的本质理解非常模糊。经过一番搜索，我发现了this great video我想分享一下，以防有人遇到同样的问题。

Answer 1

当你假设你的字符串是 UTF-8 时，我很想知道为什么选择 256 作为数组的长度。在 UTF-8 中，一个字符最多可以由 4 个字节组成，这意味着字符数远多于 256 个字节。

无论如何:使用 HashTable/HashMap 需要巨大的内存开销。首先，所有字符和整数都需要包装在一个对象(整数/字符)中。 Integer 消耗的内存大约是 int 的 3 倍。对于数组，由于 java 对数组执行的优化，差异可能会更大(例如，java 堆栈仅以 4 字节的倍数工作，而在数组中，java 允许较小的类型(例如 char)仅消耗 2 个字节)。

然后，HashTable 本身会产生内存开销，因为它需要维护一个数组(通常不会完全使用)和链表来维护生成相同哈希的所有对象。

此外，数组的访问时间将显着加快。您可以保存多个方法调用(add、hashCode、iterator...)，并且 Java 字节代码中存在许多操作码，可以使数组的处理更加高效。

无论如何。您的问题是:

Which of the two approaches would be more memory efficient?

可以肯定地说，数组的内存效率更高。

但是您应该绝对确定您的要求是什么。您需要更高的内存效率吗？ (如果您处理大量数据或使用速度较慢的设备(移动设备？)，这可能是真的)代码的可读性有多重要？代码大小如何？可重用性？

256 真的是正确的尺寸吗？