HashMap的最大容量是多少.

学而不思则罔

发布日期: 2020-06-06

文章字数: 990

阅读时长: 4 分

阅读次数:

HashMap的最大容量是多少.

首先, HashMap底层是数组+链表, 所以HashMap的容量约等于 数组长度 * 链表长度.
因为链表长度不固定,甚至可能链表会是树结构, 所以我们主要讨论数组长度.

那么, 数组的最大长度是多长呢? 仔细想想, 好像这么多年也没去看过数组的源码(笑).

一是规范隐含的限制。Java数组的length必须是非负的int，
所以它的理论最大值就是java.lang.Integer.MAX_VALUE = 2^31-1 = 2147483647。

二是具体的实现带来的限制。
这会使得实际的JVM不一定能支持上面说的理论上的最大length。
例如说如果有JVM使用uint32_t来记录对象大小的话，那可以允许的最大的数组长度（按元素的个数计算）就会是：
(uint32_t的最大值 - 数组对象的对象头大小) / 数组元素大小

嗯..数组长度理论上可以达到 2^31-1 这么长, 那么HashMap的最大长度也是这么了?

不, 在HashMap中规定HashMap底层数组的元素最大为 1<<30

static final int MAXIMUM_CAPACITY = 1 << 30;

为啥呢? 理论上不是可以更长吗?

还记得我们以前提到过的HashMap会把容量定为输入容量的最近的2次幂.

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

这串是干嘛呢?

现在想象一个场景, new HashMap(9);
我想初始化一个长度为9的HashMap

cap: 
00000000 00000000 00000000 00001001

int n = cap - 1:
00000000 00000000 00000000 00001000

n >>> 1:
00000000 00000000 00000000 00000100

n |= n >>> 1:
00000000 00000000 00000000 00001100

n >>> 2:
00000000 00000000 00000000 00000011

n |= n >>> 2:
00000000 00000000 00000000 00001111

n >>> 4:
00000000 00000000 00000000 00001111

n |= n >>> 4:
00000000 00000000 00000000 00001111


n >>> 8:
00000000 00000000 00000000 00001111

n |= n >>> 8:
00000000 00000000 00000000 00001111

n >>> 16:
00000000 00000000 00000000 00001111

n |= n >>> 16:
00000000 00000000 00000000 00001111

这边计算了什么呢

00000000 00000000 00000000 00001111 = 15

也就是将原本最高的一位后面全部变成1
也即, 变成了 2^n -1
这样只要最后结果加1, 就会变成离他最近的2次幂.

那这些有什么用呢?

00000000 00000000 00000000 00000001 左边不是31个位置吗? 为什么最大容量不是 1 << 31 ?

如果左移31, 就会变成10000000 00000000 00000000 00000000,
而最高位, 即最左边的位是符号位, 1为负数.

// 运行这条
System.out.println(0b10000000_00000000_00000000_00000000);

// 输出
-2147483648

数组长度总不能是负数吧. 所以HashMap的数组长度最长是 1<<30

尝试了一下添加1<<30个数进HashMap

public static void main(String[] args) {
    int times = 1<<30;
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < times; i++) {
        map.put(i, i);
        System.out.println(i);
    }
}

可以看到, 我没有设置HashMap初始大小, 因此默认大小是16, 因为我们知道, HashMap在一定条件下会扩容, 扩容导致的问题就是数据迁移.

所以在运行到 1486699 的时候第一次出现明显卡顿,时间很短大概一秒左右, 再往后的输出停顿时间越来越久.

因此小伙伴们如果预先知道要装多少数据, 或者大概数据, 不妨精心计算一下HashMap的初始大小.我认为总数据量 / (3|4|5|6) 都可以.

因为按照同一节点下链表的数据多少规律, 同一个节点下挂载多个数据的概率是逐渐减少的.(而且没有哪个map会装这么多数据吧

0:    0.60653066
1:    0.30326533
2:    0.07581633
3:    0.01263606
4:    0.00157952
5:    0.00015795
6:    0.00001316
7:    0.00000094
8:    0.00000006

在 23739181 的时候就OOM了, 或许下次把堆内存调大点再试试(逃