hashmap数组什么时候扩容_hashmap是数组还是链表

全栈程序员-站长 • 2022年9月17日上午7:46 • 未分类 • 阅读 0

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

为什么需要扩容？

因为HashMap为了节省创建出的对象的内存占用，一开始只默认分配：

static final int DEFAULT_INITIAL_CAPACITY=1<<4; 也就是默认的数组大小是16个，而在HashMap的源码中可以发现HashMap扩容方法如下，就是说当HashMap里存储元素的个数大于threshold(capacity*loadFactor时，会进行扩容，一般都会扩大成为原大小的一倍(总之是%2＝0的一个newCapacity)，之所以需要和2的幂相关，是因为散列表的hash算法是根据移位来进行计算的，而我们都知道计算机是二进制的，移位也只能是进行＊2或者／2因此，扩容的大小要符合这个标准，否则会造成没必要的浪费甚至错误。

hashmap数组什么时候扩容_hashmap是数组还是链表判断何时需要扩容

知道什么场景下会造成扩容，下面聊聊扩容是如何实现的：

hashmap数组什么时候扩容_hashmap是数组还是链表扩容方法

首先判断原本的capacity是否已经是static final intMAXIMUM_CAPACITY=1<<30;，如果不是，会重新创建新的Entry数组，并将数组长度更改为newCapacity，接着调用了transfer方法，并将新的table和threshold赋值给当前hashMap对象，这里最重要的方法就是transfer，因为这个方法会根据newCapacity重新计算在Entry数组中原先存在的entry的新的散列位置。方法如下：

hashmap数组什么时候扩容_hashmap是数组还是链表 rehash重新计算entry的散列位置

计算过程比较简单与重新创建新的hashMap比较类似，就是根据entry的key重新计算出hash值，然后根据新的数组长度计算出应该把老的entry放在新数组的那个位置，如果有冲突就将entry链接其上。(这个方法一个有趣的地方是：是否rehash是可选的，而选择的方法是通过hash因子来决定的，这边暂时不多做讨论)在执行完这些东西之后，hashMap的扩容就结束了。

可以发觉，扩容的成本并不低，因为需要遍历一个时间复杂度为O(n)的数组，并且为其中的每个enrty进行hash计算。加入到新数组中，所以最好的情况是能够合理的使用HashMap的构造方法创建合适大小的HashMap，使得在不浪费内存的情况下，尽量减少扩容，这个就要根据业务来决定了。

另外引申一个问题，为什么hashMap会使用着么复杂的结构，而且在元素并没有将数组填充满的情况下就进行扩容？这个其实是和HashMap散列表的目的有关，因为使用hashCode先进行查找到entry所在的HashMap数组位置，再去遍历这个数组位置上的bucket，会使得查询的时间复杂度为O(1)，这样一对比一般意义上的数组，不难发现有质的飞跃。这也是HashMap大费周章搞出这些的原因。而由此引申出来的冲突处理这样的问题后面会谈到。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/192636.html原文链接：https://javaforall.net