java - 为什么Hashtable的load factor和CLRS书中描述的不一致？

Question

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

As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs

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

在CLRS书中，也介绍了load factor alpha。

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

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

但是Java中的Hashtable使用的存储多于N，我觉得不符合CLRS的设计吧？

我说的对吗？

谢谢

Answer 1

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

假设你想添加 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:

An instance of Hashtable has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. Note that the hash table is open: in the case of a "hash collision", a single bucket stores multiple entries, which must be searched sequentially. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hashtable exceeds the product of the load factor and the current capacity, the capacity is increased by calling the rehash method.

Generally, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the time cost to look up an entry (which is reflected in most Hashtable operations, including get and put).

The initial capacity controls a tradeoff between wasted space and the need for rehash operations, which are time-consuming. No rehash operations will ever occur if the initial capacity is greater than the maximum number of entries the Hashtable will contain divided by its load factor. However, setting the initial capacity too high can waste space.

If many entries are to be made into a Hashtable, creating it with a sufficiently large capacity may allow the entries to be inserted more efficiently than letting it perform automatic rehashing as needed to grow the table.