0

从关于 Hashtable 类的 Java 文档中，它说

作为一般规则，默认负载因子 (.75) 在时间和空间成本之间提供了良好的折衷

所以 Hashtable 的加载因子是 0.75，这意味着如果有 N 个键，Hashtable 将使用 M = N/0.75 个空格来存储它们。

在 CLRS 书中，它还介绍了负载因子 alpha。

但据我了解，CLRS 打算将 alpha 设置为大于 1，即 M = N/alpha < N。这意味着 Hashtable 可以使用 M 个插槽，其中 M < N 以便它可以节省未使用键的存储空间。

我说 M < N 可以节省存储空间，因为通常我们不知道 N 的确切值，但我们知道键的集合并使用 N 代表可能的键数。密钥的集合可能非常大，但实际使用的密钥数量非常少。所以设置 M 小于 N 可以节省存储空间。这也是为什么通常 Hashtable 不使用直接数组来映射每个 {key, value} 1:1 的原因。

但是 Java 中的 Hashtable 使用存储多于 N。我认为这与 CLRS 设计不相符，对吧？

我对吗？

谢谢

4

2 回答 2

2

好吧，负载因子应该大于添加的元素。除以小于一的数字会导致比初始数字更大的数字。

假设您要添加 100 个元素，您可以编写：

AllocationSize = 100 / 0.75; // Your formula: M = N/0.75

或者

AllocationSize = 100 * 1.33333333; // M = N / X -> M = N * (1/X)

两者都导致133.333333-> 133。

整个 JavaDoc：

Hashtable 的实例有两个影响其性能的参数：初始容量和负载因子。容量是哈希表中的桶数，初始容量只是哈希表创建时的容量。注意哈希表是开放的：在“哈希冲突”的情况下，单个桶存储多个条目，必须按顺序搜索。负载因子是哈希表在其容量自动增加之前允许达到的程度的度量。当哈希表中的条目数超过负载因子与当前容量的乘积时，通过调用 rehash 方法增加容量。

通常，默认负载因子 (.75) 在时间和空间成本之间提供了良好的折衷。较高的值会减少空间开销，但会增加查找条目的时间成本（这反映在大多数 Hashtable 操作中，包括 get 和 put）。

初始容量控制了浪费空间和需要重新哈希操作之间的权衡，这些操作非常耗时。如果初始容量大于 Hashtable 将包含的最大条目数除以其负载因子，则不会发生重新哈希操作。但是，将初始容量设置得太高会浪费空间。

如果要在 Hashtable 中创建许多条目，则创建具有足够大容量的条目可能比让它根据需要执行自动重新散列以增长表来更有效地插入条目。

于 2012-02-18T09:15:35.690 回答
0

我没有听说过 CLRS 的书，但我可以告诉你使用超过 0.75 的负载因子（对于某些哈希映射设计甚至更少）会导致大量的冲突。

如果允许 HashMap 或 Hashtable 自然增长，其容量将与条目数成正比。与 Entry 对象的大小（通常为 16 - 24 个字节）相比，这些引用很小（通常为 4 个字节），因此您关心的哈希索引表将始终比 Entry 对象的大小小几倍，更不用说键了和价值观。

于 2012-02-18T09:16:37.243 回答