为什么Hashtable的initialCapacity为11而HashMap中的DEFAULT_INITIAL_CAPACITY为16且需要2的幂

Question

在jdk 1.6中比较HashMap和Hashtable源代码,我在HashMap中看到了下面的代码

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 16;

    int capacity = 1;
    while (capacity < initialCapacity)
        capacity <<= 1;

但是,在Hashtable中,我看到下面的代码？

table = new Entry[initialCapacity];

public Hashtable() {
    this(11, 0.75f);
}

所以我的问题是:为什么hashMap需要2的幂作为初始容量？而哈希表选择11作为默认初始容量？我认为这与哈希表是线程安全并且不允许空键或值的事情无关.

谢谢.

Answer 1

以下文章详细讨论了这个问题:HashMap需要更好的hashCode() - JDK 1.4 Part II.

根据那篇文章,转向两种尺寸幂的主要原因是位掩码比整数除法更快.这并非没有不良后果,原作者之一解释了这一点:

Joshua Bloch:使用二次幂的缺点是生成的哈希表对哈希函数(hashCode)的质量非常敏感.输入中的任何更改都必须影响哈希值的低位比特.(理想情况下,它应该以相同的可能性影响散列值的所有位.)因为我们无法保证这是真的,所以当我们切换到2的幂时,我们放入了二级(或"防御性")散列函数哈希表.在屏蔽低阶位之前,将该散列函数应用于hashCode的结果.它的工作是将信息分散在所有位上,特别是分散到低位.当然它必须运行得非常快,否则你将无法切换到两个尺寸的电源表.1.4中的原始二级散列函数证明是不够的.我们知道这是理论上的可能性,但我们认为它不会影响任何实际数据集.我们错了.替换的二级哈希函数(我在计算机的帮助下开发)具有强大的统计特性,几乎可以保证良好的桶分布.

Answer 2

Hashtable使用伪素数表大小并且增大表的大小相对较慢.HashMap使用2的幂作为位,并且比使用模数更快.

具有讽刺意味的是,2的幂的模数意味着需要一个好的hashCode(),因为顶部的位将被忽略,因此HashMap有一个重新排列hashCode的方法,以避免这个问题,这意味着它实际上可能更慢.位:Z