37

我应该传递什么值来为 N 个项目创建一个有效HashMap/基于结构的结构？HashMap

在 anArrayList中，有效数是 N（N 已经假设未来增长）。a 的参数应该是什么HashMap？((int)(N * 0.75d), 0.75d)？更多的？较少的？改变负载系数有什么影响？

4

9 回答 9

39

关于负载因子，我将简单地引用HashMap javadoc：

作为一般规则，默认负载因子 (.75) 在时间和空间成本之间提供了良好的折衷。较高的值会减少空间开销，但会增加查找成本（反映在 HashMap 类的大多数操作中，包括 get 和 put）。在设置其初始容量时，应考虑映射中的预期条目数及其负载因子，以尽量减少重新哈希操作的次数。如果初始容量大于最大条目数除以负载因子，则不会发生重新哈希操作。

这意味着，负载因子不应从 更改.75，除非您要进行一些特定的优化。初始容量是您唯一要更改的内容，并根据您的N值-含义(N / 0.75) + 1或该区域的某些内容进行设置。这将确保表总是足够大并且不会发生重新散列。

于 2009-01-12T10:12:37.667 回答
21

我进行了一些单元测试以查看这些答案是否正确，结果证明使用：

(int) Math.ceil(requiredCapacity / loadFactor);

因为初始容量给出了你想要的 aHashMap或 a Hashtable。通过“你想要什么”，我的意思是向requiredCapacity地图添加元素不会导致它包装的数组调整大小，并且数组不会大于所需的大小。由于默认负载容量为 0.75，因此像这样初始化 HashMap 可以：

... = new HashMap<KeyType, ValueType>((int) Math.ceil(requiredCapacity / 0.75));

由于 HashSet 实际上只是 HashMap 的包装器，因此同样的逻辑也适用于那里，即您可以像这样有效地构造 HashSet：

.... = new HashSet<TypeToStore>((int) Math.ceil(requiredCapacity / 0.75));

@Yuval Adam 的回答对于所有情况都是正确的，除了(requiredCapacity / 0.75)2 的幂，在这种情况下它分配了太多的内存。
@NotEdible 的答案在许多情况下使用了太多内存，因为 HashMap 的构造函数本身处理它希望 maps 数组的大小是 2 的幂的问题。

于 2012-08-15T14:06:38.997 回答
17

在 Google 的guava 库中，有一个函数可以创建针对预期数量的项目优化的 HashMap：newHashMapWithExpectedSize

来自文档：

创建一个 HashMap 实例，该实例具有足够高的“初始容量”，它应该容纳 expectedSize 元素而不会增长......

于 2013-04-18T11:19:40.620 回答
6

同样值得注意的是，在较小的一侧使用 HashMap 会使哈希冲突更有可能发生，这会减慢查找速度。因此，如果您真的担心地图的速度，而不太担心地图的大小，则可能值得将其设置得对于它需要容纳的数据来说有点太大。由于内存很便宜，我通常为已知数量的项目初始化 HashMaps

HashMap<Foo> myMap = new HashMap<Foo>(numberOfElements * 2);

随意不同意，事实上我很想验证或抛弃这个想法。

于 2009-01-12T10:19:35.763 回答
4

Yuval 给出的答案只对 Hashtable 是正确的。HashMap 使用二的幂次方桶，所以对于 HashMap，Zarkonnen 实际上是正确的。您可以从源代码中验证这一点：

  // Find a power of 2 >= initialCapacity
  int capacity = 1;
  while (capacity < initialCapacity)
  capacity <<= 1;

因此，尽管 0.75f 的负载因子在 Hashtable 和 HashMap 之间仍然相同，但您应该使用初始容量 n*2，其中 n 是您计划存储在 HashMap 中的元素数。这将确保最快的获取/放置速度。

于 2009-11-25T15:02:39.697 回答
2

参考 HashMap 源代码会有所帮助。

如果条目数达到阈值（容量 * 负载因子），则会自动进行重新散列。这意味着负载因子太小会随着条目的增长而导致频繁的重新散列。

于 2009-02-25T02:02:08.413 回答
2

在大多数情况下，List使用以下大小参数进行orMap初始化是安全的。ListMap

List<T>(numElements + (numElements / 2));
Map<T,T>(numElements + (numElements / 2));

这遵循.75* 2规则，并且比上述操作节省了一点开销。

于 2010-07-27T16:03:17.737 回答
1

在 ArrayList 中，有效数字是 N（N 已经假设未来增长）。

嗯，不，它没有，除非我误解了你在说什么。当您将整数传递给 Arraylist 构造函数时，它将创建一个与该大小完全相同的底层数组。如果事实证明您甚至需要一个额外的元素，那么当您下次调用 add() 时，ArrayList 将需要调整底层数组的大小，从而导致此调用花费比通常更长的时间。

另一方面，如果您在谈论考虑到增长的 N 值 - 那么是的，如果您可以保证该值永远不会超过此值，那么调用这样的 Arraylist 构造函数是合适的。在这种情况下，正如 Hank 所指出的，映射的类似构造函数将是 N 和 1.0f。即使您碰巧超过 N，这也应该合理地执行（尽管如果您希望这会定期发生，您可能希望为初始大小传递更大的数字）。

如果您不知道，负载因子是地图容量增加的点，占总容量的一小部分。

编辑：Yuval 可能是对的，对于通用地图，将负载因子保持在 0.75 左右是一个更好的主意。如果您的键具有顺序哈希码（例如顺序整数键），则 1.0 的负载因子会表现出色，但对于其他任何事情，您可能会遇到与哈希桶的冲突，这意味着查找某些元素需要更长的时间。创建比严格必要的更多的桶将减少这种碰撞的机会，这意味着元素有更多的机会位于自己的桶中，因此可以在最短的时间内检索到。正如文档所说，这是时间与空间的权衡。如果其中任何一个对您特别重要（如分析器所示，而不是过早优化！），您可以强调这一点；否则，坚持使用默认值。

于 2009-01-12T10:18:33.347 回答
1

对于关键系统中非常大的 HashMap，初始容量错误可能会带来很大的问题，您可能需要经验信息来确定如何最好地初始化 Map。

CollectionSpy ( collectionspy.com ) 是一个新的 Java 分析器，它可以让您在眨眼之间看到哪些 HashMap 接近需要重新散列，过去已经重新散列了多少次等等。确定基于容量的容器构造函数的安全初始容量参数的理想工具。

于 2009-07-03T19:24:55.437 回答