16

好的,这是我的情况:

我有一个状态数组,其中可能包含重复项。为了摆脱重复,我可以将它们全部添加到一个集合中。

但是,当我创建 Set 时,它希望定义初始容量和负载因子,但是应该将它们设置为什么?

从谷歌搜索,我想出了:

String[] allStates = getAllStates();
Set<String> uniqueStates = new HashSet<String>(allStates.length, 0.75);

问题在于 allStates 可以包含 1 到 5000 个状态。因此 Set 的容量将超过 5000,但最多只能包含 50 个。

因此,或者将 Set 的最大大小设置为最大状态数,并将负载因子设置为 1。

我想我的问题真的是:

  • 当您不知道 Set 中有多少项目时,您应该将初始容量设置为多少?
  • 当它可以包含的最多是 50 时,它设置为什么真的很重要吗?
  • 我什至应该担心它吗?
4

7 回答 7

17

假设您知道不会超过 50 个州(您是指美国的州吗?),则

Set<String> uniqueStates = new HashSet<String>(allStates.length, 0.75);

引用肯定是错误的。我建议您选择 50 / 0.75 = 67 的初始容量,或者为了安全起见可能是 68。

我也觉得有必要指出你可能过度思考了这一点。将 arraylist 的大小从 16 调整到 64 两次不会给您带来明显的性能影响,除非这恰好在程序的最关键性能部分中。

所以最好的答案可能是使用:

new HashSet<String>();

这样一来,您就不会在一年后回来并疑惑为什么选择如此奇怪的构造函数参数。

于 2009-02-19T13:14:26.750 回答
7

使用不需要指定这些值的构造函数,然后选择合理的默认值。

于 2009-02-19T11:45:18.323 回答
3

首先,我要说的是,在你的情况下,你肯定是想多了。但是,在某些情况下,人们可能想要正确处理它。所以这就是我的理解:

1)您可以在 HashSet 中保存的项目数 = 初始容量 x 负载因子。因此,如果您希望能够容纳 n 个项目,则需要执行Zarkonnen所做的操作,并将 n 除以负载因子。

2) 在幕后,每个 Oracle 教程的初始容量四舍五入为 2 的幂。

3) 如Tom Hawtin-tackline所述,负载系数不应超过 0.80 以防止过度碰撞。

如果您只接受默认值(初始容量 = 16,负载系数 = 0.75),那么您最终的尺寸将增加一倍 3 倍。(初始最大尺寸 = 12,第一次增加使容量 32 和最大尺寸 24(32 * .75),第二次增加使容量 64 和最大尺寸 48(64 * .75),第三次增加使容量 128 和最大尺寸 96(128 * .75).)

要使您的最大尺寸接近 50,但要使集合尽可能小,请考虑 64(2 的幂)的初始容量和 0.79 或更高的负载系数。64 * .79 = 50.56,所以你可以得到所有 50 个州。指定 32 < 初始容量 < 64 将导致初始容量向上舍入为 64,因此这与预先指定 64 相同。指定初始容量 <= 32 将导致大小增加。除非您的初始容量 > 64,否则使用 < .79 的负载因子也会导致大小增加。

所以我的建议是指定初始容量 = 64 和负载因子 = .79。

于 2014-05-29T18:27:30.003 回答
1

安全的赌注是选择太小的尺寸。

因为调整大小可以通过指数增长算法得到改善(参见几周前的 stackoverflow 播客),所以变小永远不会花费你那么多。如果你有很多套(你很幸运),那么如果它们过大,那么性能就会很重要。

负载因子是一个棘手的问题。我建议将其保留为默认值。我了解:低于 0.70f 您会使阵列太大,因此速度较慢。高于 0.80f,您将开始遇到许多关键冲突。据推测,探测算法将需要比桶算法更低的负载因子。

另请注意,“初始容量”的含义与大多数人认为的略有不同。它指的是数组中的条目数。要获得许多元素的确切容量,请除以所需的负载因子(并适当地四舍五入)。

于 2009-02-19T12:12:55.060 回答
0

做一个很好的猜测。没有硬性规定。如果您知道可能有 10-20 个州,我会从这个数字(20)开始。

于 2009-02-19T11:46:03.610 回答
0

我第二扎科宁。你的最后一个问题是最重要的。如果这恰好发生在您的应用程序的热点中,那么可能值得努力查看并尝试优化,否则 CPU 周期比烧毁自己的神经元要便宜。

于 2009-02-19T14:20:39.760 回答
0

如果您要对此进行优化 - 并且这样做可能是合适的 - 您的某些决定将取决于您希望数组具有多少重复项。

  • 如果有很多重复项,您将需要较小的初始容量。迭代时,大而稀疏的哈希表很糟糕。

  • 如果预计不会有很多重复,您将需要一个初始容量,以便整个阵列无需调整大小即可容纳。

我的猜测是你想要后者,但如果你追求这个,这是值得考虑的事情。

于 2012-12-28T17:22:12.293 回答