Java HashMap数组大小

Question

Java HashMap数组大小

javaoopcollectionsjava-8hashmap

3

我正在阅读Java 8 HashMap的实现细节，有没有人能告诉我为什么Java HashMap的初始数组大小特定为16？16有什么特别之处？为什么它总是2的幂？谢谢。

- Imran

2

你对“16”有什么意见吗？这是一个非常性感的数字。 - Scary Wombat

3个回答

2

在选择hash & (n - 1)和modulo时，还有一件事情需要注意，那就是负数的哈希值。hashcode的类型为int，当然可能是负数。在Java中，对负数取模会得到负数，而&则不会。

- Eugene

1

另一个原因是您希望数组中的所有插槽都等可能地被使用。由于hash()均匀分布在32位上，如果数组大小无法整除哈希空间，则会产生余数，导致较低的索引具有稍高的使用机会。理想情况下，不仅哈希，而且（hash（）％array_size）是随机且均匀分布的。

但这只对哈希范围小的数据（如字节或字符）真正重要。

- Randy Hudson

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Anish Goyal · Accepted Answer

2的幂次方在各处出现的原因是因为在二进制中表达数字（正如电路中所用）时，对2的幂进行的某些数学操作更简单、更快速（想想我们使用的十进制系统中使用10的幂进行的简单的数学运算即可）。例如，在计算机中乘法不是一个非常高效的过程 - 电路使用类似于将两个带有多位数字的数相乘的方法。通过2的幂次方进行乘或除只需要计算机将位向左移动以进行乘法或向右移动以进行除法。

至于为什么HashMap使用16？10是一种常用的默认值用于动态增长的结构（任意选择），而16并不远离此值 - 但是它是2的幂次方。

当d是2的幂次方时，可以非常有效地进行模数计算。n % d = n & (d-1) 并且模数被用于确定项目映射到内部数组中的哪个索引 - 这意味着它在Java HashMap中经常出现。模数需要除法，这也比使用按位与运算符要低效得多。您可以通过阅读关于数字逻辑的书来自我验证这一点。

2的幂次方的按位与工作方式之所以能够实现这一点是因为每个2的幂次方都可以表示为单个位设置为1。假设该位为t。当你从2的幂次方中减去1时，你将每个位在t以下的位设置为1，并且在t以上（以及t本身）的每个位都设置为0。按位与因此保存了数字n中所有低于位置t的位的值（如上所述），并将其余部分设置为0。

但这对我们有什么帮助呢？记住，在除以10的幂时，您可以计算跟随1后面的零的数量，并从被除数的最低有效数字开始取该数字数量，以找到余数。例如：637989 % 1000 = 989。类似的属性也适用于二进制数字，只有一个位设置为1，其他位设置为0。例如：100101 % 001000 = 000101。