当前位置:网站首页>Detailed explanation of ArrayList expansion
Detailed explanation of ArrayList expansion
2022-07-01 17:49:00 【Full stack programmer webmaster】
Hello everyone , I meet you again , I'm your friend, Quan Jun .
This article discusses ArrayList Expansion process
ArrayList At the bottom is an array elementData, Used to store inserted data . The initial size is 0, When data is inserted , Default size DEFAULT_CAPACITY = 10. If you're creating ArrayList When it comes to initialCapacity, Then the initial size is ArrayList
1. Verify the code example of capacity expansion
As you can see from the example , When adding elements , If the number of elements +1> Current array length 【size + 1 > elementData.length】 when , super-popular , The size of the expanded array is : oldCapacity + (oldCapacity >> 1)
Pass the contents of the old array Array.copyOf Copy all to the new array , At this time, the old and new lists size Same size , but elementData The length is different from the capacity
Be careful : Expansion is not strict 1.5 times , Is to shift the length of the array one bit to the right before expansion + The length of the array before expansion
public class SimpleTest {
public static void main(String[] args) {
ArrayList list = new ArrayList();
int size = 0;
for (int i = 0; i < 100; i++) {
list.add(i);
if(getCapacity(list)>size) {
System.out.println("capacity:"+getCapacity(list) + ",size:"+list.size());
size = getCapacity(list);
}
}
}
public static Integer getCapacity(ArrayList list) {
Integer length = null;
Class clazz = list.getClass();
Field field;
try {
field = clazz.getDeclaredField("elementData");
field.setAccessible(true);
Object[] object = (Object[]) field.get(list);
length = object.length;
return length;
} catch (Exception e) {
e.printStackTrace();
}
return length;
}
}
The operation results are as follows :
capacity:10,size:1 capacity:15,size:11 capacity:22,size:16 capacity:33,size:23 capacity:49,size:34 capacity:73,size:50 capacity:109,size:74
2. Expansion related source code
public boolean add(E e) {
// Called a ensureCapacityInternal Method , Ensure that the array subscript does not cross the bounds
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// The new capacity is expanded to about 1.5 times , Moving one bit to the right is equivalent to dividing the original value by 2, Expansion is not strict 1.5 position
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);
}
3. Why press about 1.5 Double expansion
Size selection of expansion factor , The following situations need to be considered :
- The expansion capacity cannot be too small , Prevent frequent expansion , Frequently apply for memory space + Arrays are copied frequently
- The expansion capacity should not be too large , Need to make full use of space , Avoid wasting too much space ;
In order to make full use of the previously allocated memory space , It's better to set the growth factor to 1<k<2.
k=1.5 when , You can make full use of the space already released in front . If k >= 2, The new capacity is just right, which is always greater than the capacity of all abandoned arrays in the past
And make full use of the shift operation ( Moves to the right one ), Reduce floating point numbers or operation time and number of operations
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/130890.html Link to the original text :https://javaforall.cn
边栏推荐
- 多线程使用不当导致的 OOM
- 中国一次性卫生用品生产设备行业深度调研报告(2022版)
- (27) Open operation, close operation, morphological gradient, top hat, black hat
- Work and leisure suggestions of old programmers
- pyqt5中,在控件上画柱状图
- 网上股票开户安全吗?是否可靠?
- (16) ADC conversion experiment
- At present, where is the most formal and safe account opening for futures speculation? How to open a futures account?
- Is it safe to open an ETF account online? What are the steps?
- The difference and relationship between iteratible objects, iterators and generators
猜你喜欢
Intelligent operation and maintenance practice: banking business process and single transaction tracking
Technical secrets of ByteDance data platform: implementation and optimization of complex query based on Clickhouse
The difference and relationship between iteratible objects, iterators and generators
Integer array merge [JS]
ACM mm 2022 video understanding challenge video classification track champion autox team technology sharing
June issue | antdb database participated in the preparation of the "Database Development Research Report" and appeared on the list of information technology and entrepreneurship industries
Gameframework eating guide
Setting up a time server requires the client to automatically synchronize the time of the server at 9 a.m. every day
Official announcement! Hong Kong University of science and Technology (Guangzhou) approved!
Penetration practice vulnhub range Nemesis
随机推荐
At present, where is the most formal and safe account opening for futures speculation? How to open a futures account?
China biodegradable plastics market forecast and investment strategy report (2022 Edition)
SQL injection vulnerability (MySQL and MSSQL features)
整形数组合并【JS】
Smart factory digital management system software platform
【牛客网刷题系列 之 Verilog快速入门】~ 优先编码器电路①
Redis -- data type and operation
Replace UUID, nanoid is faster and safer!
[2. Basics of Delphi grammar] 4 Object Pascal operators and expressions
Gameframework eating guide
China PBAT resin Market Forecast and Strategic Research Report (2022 Edition)
Kernel stray cat stray dog pet adoption platform H5 source code
Function, condition, regular expression
Product service, operation characteristics
China acetonitrile market forecast and strategic consulting research report (2022 Edition)
Sword finger offer 20 String representing numeric value
中国乙腈市场预测与战略咨询研究报告(2022版)
Good looking UI mall source code has been scanned, no back door, no encryption
中国酶制剂市场预测与投资战略研究报告(2022版)
PIP version problems: PIP problems still occur when installing akshare and using Tsinghua source and Douban source