提高内存使用效率：IntegerHashMap

Question

我们使用了一个超过一百万条目的HashMap<Integer, SomeType>()。 我认为这很大。

但是整数本身就是它们自己的哈希码。我们不能使用特殊的Map.Entry，直接使用int而不是指向Integer对象的指针，从而节省内存吗？在我们的情况下，这将节省1000000倍需要一个Integer对象的内存。

我的思路有什么问题吗？太特殊以至于没有普遍的兴趣？（至少，有一个EnumHashMap）

add1. IntegerHashMap的第一个泛型参数用于使其与其他Map实现尽可能相似。当然，它可以被删除。

add2. 对于其他映射和集合，也应该是可能的。例如ToIntegerHashMap<KeyType，Integer>，IntegerHashSet<Integer>等。

- Ulrich Scholz

Answer 1

你需要的是一个“基本集合”库。它们通常在内存使用和性能方面更好。最古老/流行的库之一叫做“Trove”。然而，它现在有点过时了。现在主要活跃的库有：

• Goldman Sachs Collections
• Fast Util
• Koloboke

请在这里查看基准测试结果

- Laplie Anderson

---

对我来说，最好的情况是将原始集合的任何实现作为JDK / Apache commons / Guava的一部分。不幸的是，对我来说使用额外的库并不容易。速度并不是我的主要关注点，而是内存。尽管如此，您的答案可能是我能得到的最接近的答案。 - Ulrich Scholz

Answer 2

一些警告：

1. "整数是它们自己的哈希码"，这个说法需要非常小心。根据你拥有的整数，键的分布可能是最优的，也可能是极差的。理想情况下，我会设计一个映射表，使你可以传入一个自定义的IntFunction作为哈希策略。如果你想的话，仍然可以将其默认为(i) -> i，但你可能想要引入一个模因子，否则你的内部数组将会很大。你甚至可能想使用一个IntBinaryOperator，其中一个参数是整数，另一个参数是桶的数量。

2. 我会删除第一个泛型参数。你可能不想实现Map<Integer, SomeType>，因为这样你将不得不在所有方法中进行装箱/拆箱，并且你将失去所有优化（除了空间）。试图使一个原始集合与一个对象集合兼容将使整个过程毫无意义。

- Sean Patrick Floyd

---

对于“整数是它们自己的哈希码”这个说法，我的看法是：为了简单起见，我会为整数构建一个适当的哈希方法。但是，如果您使用特定的Map.Key对象，那么也可以这样做。 - Ulrich Scholz

@UlrichScholz 我原本以为整个重点是尽量避免使用对象。但这取决于你的使用情况。 - Sean Patrick Floyd

当然，我想避免不必要的对象。尽可能地避免它们是另一回事。 我不熟悉当前HashMap实现的详细信息。但是，很可能让IntegerHashMap紧随其后，除了使用int键外，还要使用适当的哈希函数。（甚至可以与Integer实现的相同）。 - Ulrich Scholz

显然，Integer类的hashcode()方法只返回其原始值。因此，“整数是它们自己的哈希码”最终可能并不那么错误。 - Ulrich Scholz

@UlrichScholz 这取决于您处理的整数分布以及将它们分配到桶中的方式。假设您所有的整数都是1024的倍数，并且1024也是您用于桶分配的模数，那么这基本上是最坏的情况。 - Sean Patrick Floyd