ArrayList及HashMap的扩容规则讲解

ArrayList及HashMap的扩容规则讲解

1、ArrayList

默认大小为10

/**

* Default initial capacity.

*/

private static final int DEFAULT_CAPACITY = 10;

最大容量为2^30 - 8

/**

* The maximum size of array to allocate.

* Some VMs reserve some header words in an array.

* Attempts to allocate larger arrays may result in

* OutOfMemoryError: Requested array size exceeds VM limit

*/

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**

* A constant holding the maximum value an {@code int} can

* have, 2³¹-1.

*/

public static final int MAX_VALUE = 0x7fffffff;

扩容规则为：oldCapacity*1.5

/**

* Increases the capacity to ensure that it can hold at least the

* number of elements specified by the minimum capacity argument.

* @param minCapacity the desired minimum capacity

*/

private void grow(int minCapacity) {

// overflow-conscious code

int oldCapacity = elementData.length;

int newCapacity = oldCapacity + (oldCapacity >> 1);

if (newCapacity - minCapacity < 0)

newCapacity = minCapacity;

if (newCapacity - MAX_ARRAY_SIZE > 0)

newCapacity = hugeCapacity(minCapacity);

// minCapacity is usually close to size, so this is a win:

elementData = Arrays.copyOf(elementData, newCapacity);

}

2、HashMap

默认大小： 16

/**

* The default initial capacity - MUST be a power of two.

*/

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

最大容量为：2^30

/**

* The maximum capacity, used if a higher value is implicitly specified

* by either of the constructors with arguments.

* MUST be a power of two <= 1<<30.

*/

static final int MAXIMUM_CAPACITY = 1 << 30;

扩容规则为：大于oldCapacity的最小的2的n次方整数

/**

* Adds a new entry with the specified key, value and hash code to

* the specified bucket. It is the responsibility of this

* method to resize the table if appropriate.

* Subclass overrides this to alter the behavior of put method.

*/

void addEntry(int hash, K key, V value, int bucketIndex) {

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);

}

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对我们的支持。如果你想了解更多相关内容请查看下面相关链接

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。