HashMap何时会进行扩容

2023-07-06 00:45| 来源: 网络整理| 查看: 265

最近在学习hashmap底层扩容机制，发现其扩容算法还挺有意思的，不多说，先上源码。首先是put()方法 public V put(K key, V value) { 　　　　//判断当前Hashmap(底层是Entry数组)是否存值（是否为空数组）　　　　if (table == EMPTY_TABLE) { 　　　　　　inflateTable(threshold);//如果为空，则初始化　　　　} 　　　　　　　　//判断key是否为空　　　　if (key == null) 　　　　　　return putForNullKey(value);//hashmap允许key为空　　　　　　　　//计算当前key的哈希值　　　　　　　　int hash = hash(key); 　　　　//通过哈希值和当前数据长度，算出当前key值对应在数组中的存放位置　　　　int i = indexFor(hash, table.length); 　　　　for (Entry e = table[i]; e != null; e = e.next) { 　　　　　　Object k; 　　　　　　//如果计算的哈希位置有值（及hash冲突），且key值一样，则覆盖原值value，并返回原值value 　　　　　　if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 　　　　　　　　V oldValue = e.value; 　　　　　　　　e.value = value; 　　　　　　　　e.recordAccess(this); 　　　　　　　　return oldValue; 　　　　　　} 　　　　} 　　　　modCount++; 　　　　//存放值的具体方法　　　　addEntry(hash, key, value, i); 　　　　return null; 　　} 在put()方法中有调用addEntry()方法，这个方法里面是具体的存值，在存值之前还要判断是否需要扩容 void addEntry(int hash, K key, V value, int bucketIndex) { 　　　　//1、判断当前个数是否大于等于阈值　　　　//2、当前存放是否发生哈希碰撞　　　　//如果上面两个条件否发生，那么就扩容　　　　if ((size >= threshold) && (null != table[bucketIndex])) { 　　　　　　//扩容，并且把原来数组中的元素重新放到新数组中　　　　　　resize(2 * table.length); 　　　　　　hash = (null != key) ? hash(key) : 0; 　　　　　　bucketIndex = indexFor(hash, table.length); 　　　　} 　　　　createEntry(hash, key, value, bucketIndex); 　　}

由此可以看出扩容必须满足两个条件：

1、存放新值的时候当前已有元素的个数必须大于等于阈值 2、存放新值的时候当前存放数据发生hash碰撞（当前key计算的hash值换算出来的数组下标位置已经存在值）

因为上面这两个条件，所以存在下面这些情况

（1）、就是hashmap在存值的时候（默认大小为16，负载因子0.75，阈值12），可能达到最后存满16个值的时候，再存入第17个值才会发生扩容现象，因为前16个值，每个值在底层数组中分别占据一个位置，并没有发生hash碰撞。

（2）、当然也有可能存储更多值（超多16个值，最多可以存27个值）都还没有扩容。原理：前11个值全部hash碰撞，存到数组的同一个位置（虽然hash冲突，但是这时元素个数小于阈值12，并没有同时满足扩容的两个条件。所以不会扩容），（在存入第12个元素的时候，还是存入前面11个元素所在的下标位置，因为存入之前此时比较当前元素个数 11

【本文地址】

公司简介

联系我们