java - 查询java.util.Hashtable的实现细节

Question

我有以下关于 java.util.Hashtable 的查询 实现的。这些是低级查询，与 Hashtable 的使用无关，仅与设计者选择如何实现数据结构有关

• 创建的哈希表的默认大小为 11 个桶。 11有什么特别之处？为什么不是 10 个？虽然我倾向于认为这只是一个神奇的数字，但我也不这么认为
• 要计算桶号，为什么我们不直接使用传入的 key 对象的哈希码。在实现中，我们实际上将存储桶编号计算为 (hashcode & 7FFFFFFF) % 表大小，其中 hashcode 是输入键的返回值，表大小 默认为 11。为什么我们要重新散列哈希码本身？难道它不能只是哈希码 % 表大小吗？
• contains(Object value) 方法在哈希表中搜索值的存在。为此，我们从最后一个桶开始依次搜索并移至第一个桶。这只是采用的开发人员风格吗？哈希表只是一个链表数组。更直观地说，我希望搜索从第一个桶移动到最后一个桶，但发现情况并非如此。我知道在功能上两者是相同的。但还有其他原因吗？
• 最大数组大小(在重新哈希过程中使用)设置为 Integer.MAX - 8。8 在这里有什么意义？

Answer 1

1. 这似乎是一个经验值，涉及在使用太多空间和浪费时间的重新散列操作之间进行权衡。 Hashtable javadocs :

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.

1. 该值使用 0x7FFFFFFF 进行位掩码，以删除会使该值变为负数的第一位。这会强制该值为非负数，因此 % 操作后的结果索引也将是非负数。这是为内部存储桶数组生成可行索引所必需的。

2. 这样做可能是为了稍微提高性能。 This article claims that looping backwards does exactly that.

The result show there's not much different between forward and reverse looping in 1 million of data. However when data grow huge, the performance of reverse looping is slightly faster than forward looping around 15%.

我不知道这是不是真的，但这可能是动机。

1. 我拥有的源代码揭示了关于用于最大数组大小的私有(private)常量的 Javadoc。

/**
 * The maximum size of array to allocate.
 * Some VMs reserve some header words in an array.
 * Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

我不知道这现在有多有效，但这是为了避免意外的 OutOfMemoryError。