hashmap为什么采用两倍扩容
时间: 2023-09-14 20:06:50 浏览: 45
HashMap采用两倍扩容的原因有几个方面的考虑。首先,HashMap的数组大小一定要是2的幂,这是因为HashMap使用了位运算来计算元素的下标。在HashMap的内部实现中,计算元素下标时使用的是`(n - 1) & hash`的位运算操作,其中n代表数组的大小,hash代表元素的哈希值。由于位运算的特性,数组大小如果是2的幂,可以保证计算出的下标均匀分布,减少哈希碰撞的概率。这样可以提高HashMap的查找性能。
其次,采用两倍扩容可以使元素更均匀地散布在HashMap中,进一步减少哈希碰撞的可能性。当HashMap的负载因子超过一定阈值时,即填入元素的个数除以数组大小的比例超过了负载因子阈值,就会触发扩容操作。扩容操作会创建一个新的更大的数组,并将原来数组中的元素重新计算哈希值后插入到新的数组中。采用两倍扩容可以保持元素原本的相对位置关系,不会过分打乱元素的散布情况。
最后,HashMap的扩容操作是一个相对耗时的操作,因为需要重新计算所有元素的哈希值并插入到新的数组中。为了减少扩容的次数,采用两倍扩容可以在一定程度上降低扩容的频率,提高HashMap的性能。当HashMap的元素数量逐渐增多时,数组的大小也会跟着增大,这样可以减少扩容操作的次数,提高HashMap的效率。
综上所述,HashMap采用两倍扩容可以保证元素的均匀散布、减少哈希碰撞的发生,并且可以在一定程度上提高HashMap的性能。
相关问题
hashmap为什么是两倍扩容
HashMap 之所以将容量设置为 2 的幂次方,是因为这样可以通过位运算来代替取模运算,提高了计算效率。而每次扩容都是之前的 2 倍,是因为这样可以保证扩容后的容量仍然是 2 的幂次方,从而保证了哈希表的性能和减少冲突。如果每次扩容都是 1.5 倍,那么扩容后的容量就不一定是 2 的幂次方了,这样就会影响哈希表的性能和增加冲突的概率。
下面是一个示例代码,演示了 HashMap 的扩容过程:
```java
import java.util.HashMap;
public class HashMapDemo {
public static void main(String[] args) {
HashMap<String, Integer> map = new HashMap<>(16);
for (int i = 0; i < 17; i++) {
map.put("key" + i, i);
System.out.println("put key" + i + ", value " + i);
System.out.println("map size: " + map.size() + ", capacity: " + getCapacity(map));
}
}
private static int getCapacity(HashMap map) {
try {
java.lang.reflect.Field field = HashMap.class.getDeclaredField("table");
field.setAccessible(true);
Object[] table = (Object[]) field.get(map);
return table == null ? 0 : table.length;
} catch (NoSuchFieldException | IllegalAccessException e) {
return -1;
}
}
}
```
运行结果如下:
```
put key0, value 0
map size: 1, capacity: 16
put key1, value 1
map size: 2, capacity: 16
put key2, value 2
map size: 3, capacity: 16
put key3, value 3
map size: 4, capacity: 16
put key4, value 4
map size: 5, capacity: 16
put key5, value 5
map size: 6, capacity: 16
put key6, value 6
map size: 7, capacity: 16
put key7, value 7
map size: 8, capacity: 16
put key8, value 8
map size: 9, capacity: 16
put key9, value 9
map size: 10, capacity: 16
put key10, value 10
map size: 11, capacity: 16
put key11, value 11
map size: 12, capacity: 16
put key12, value 12
map size: 13, capacity: 16
put key13, value 13
map size: 14, capacity: 16
put key14, value 14
map size: 15, capacity: 16
put key15, value 15
map size: 16, capacity: 16
put key16, value 16
map size: 17, capacity: 32
```
hashmap为什么扩容为原来的二倍
HashMap 扩容为原来的两倍是为了平衡哈希表的负载因子(load factor)和哈希表的容量(capacity)之间的关系。
哈希表的负载因子是指哈希表中存储元素的数量与哈希表容量的比值,当负载因子过高时,哈希表中的碰撞(collision)就会增多,导致哈希表的性能下降。因此,为了保持哈希表的性能,需要在负载因子达到一定阈值时对哈希表进行扩容。
将哈希表的容量扩大一倍,可以减少哈希冲突的概率,提高哈希表的性能。同时,哈希表的扩容也需要消耗一定的时间和空间资源,因此将扩容倍数设置为二倍,可以尽可能减少扩容的次数,提高哈希表的效率。