ArrayList扩容机制的发展过程

怼烎@ 2023-03-04 15:25 17阅读 0赞

### jdk1.2中 ###

扩容算法是这样的。`1.5倍+1`

public void ensureCapacity(int minCapacity) { 
    	modCount++;
    	int oldCapacity = elementData.length;
    	if (minCapacity > oldCapacity) { 
    	    Object oldData[] = elementData;
    	    int newCapacity = (oldCapacity * 3)/2 + 1;
        	    if (newCapacity < minCapacity)
    				newCapacity = minCapacity;
    	    elementData = new Object[newCapacity];
    	    System.arraycopy(oldData, 0, elementData, 0, size);
    	}
    }

### jdk1.3中 ###

和`jdk1.2`一样的扩容机制

### jdk1.4中 ###

和`jdk1.2`一样的扩容机制

### jdk1.5中 ###

和`jdk1.2`一样的扩容机制

### jdk1.6中 ###

和`jdk1.2`一样的扩容机制，但是采用新的方式  
`Arrays.copyOf( elementData , newCapacity );`拷贝新数组

--------------------

### jdk1.7中 ###

这个版本的`ArrayList`发生了变化  
扩容机制采用了右移相当于除2，并且没有+1操作，也就是1.5倍原来长度

private void grow(int minCapacity) { 
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);  //这里直接是1.5倍，没有和一起一样进行+1
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

### jdk1.8中 ###

与`jdk1.7`相同

### jdk9中 ###

代码发生了一点点变动但是基本不变

### jdk10中 ###

没多大变化

### jdk11中 ###

代码更简洁了，但是和前面一样没有多大变化

### jdk12中 ###

和前面一样

### jdk13中 ###

应该时采用了`ArraysSupport.newLength`得到新数组长度

private Object[] grow(int minCapacity) { 
        int oldCapacity = elementData.length;
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth */
                    oldCapacity >> 1           /* preferred growth */);
            return elementData = Arrays.copyOf(elementData, newCapacity);
        } else { 
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }

### jdk14中 ###

与jdk13一样