HashMap 默认容量
看过 HashMap 源代码的同学都知道, HashMap 有默认的最小容量和最大容量, 最小容量是 16, 最大容量是 2 的 30 次方.
- /**
- * 默认的初始化容量 - 必须是 2 的幂
- */
- static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
- /**
- * 最大容量, 如果任意带参构造函数传入的值大于该数 , 那么替换成该数.
- * 必须是 2 的幂, 小于等于 2~30
- */
- static final int MAXIMUM_CAPACITY = 1 << 30;
为什么不是 2 的 31 次方?
由于 int 类型限制了该变量的长度为 4 个字节共 32 个二进制位, 按理说可以向左移动 31 位即 2 的 31 次幂, 这里为什么不是 2 的 31 次方, 而是 2 的 30 次方呢?
事实上由于二进制数字中最高的一位也就是最左边的一位是符号位, 用来表示正负之分 (0 为正, 1 为负), 所以只能向左移动 30 位, 而不能移动到处在最高位的符号位, 所以最大容量只能是 2 的 30 次方.
- public static void main(String[] args) {
- System.out.println(1<<30);
- System.out.println(1<<31);
- System.out.println(1<<32);
- System.out.println(1<<33);
- System.out.println(1<<34);
- }
输出结果:
- 1073741824
- -2147483648
- 1
- 2
- 4
为什么要满足 2 的 n 次方
至于为什么是 2 的 30 次方, 不是别的数字或者最大整数, 这主要是从性能和分布均匀两方面来考虑的:
加快 hash 计算速度;
均匀分布, 减少 hash 冲突;
2 的 n 次方, 可以通过位移操作来实现, 可以加快 hash 计算速度, 结合按位与计算加快数组下标的计算. 例如在 HashMap 做扩容时, 满足 2 的幂就是相当于每次扩容都是翻倍 (就是 <<1 右移一位), 这样扩容时在重新计算下标位置时, 只有两种情况, 一种是下标不变, 另一种是下标变为: 原下标位置 + 扩容前容量, 这样扩容后节点移动相对较少, 也可以提高性能..
可以改善数据的均匀分布, 减少 hash 冲突, 毕竟 hash 冲突越大, 代表数组中一个链的长度越大, 这样的话会降低 hashmap 的性能.
其中关键代码为 HashMap 中的数组下标计算: i = (n - 1) & hash, 该计算方法可以实现一个均匀分布.
来源: http://www.jianshu.com/p/c8c60b543377