在Java中实现动态数组扩容原理与实例

原创深碍√TFBOYSˉ_ 2024-11-07 19:27 7阅读 0赞

在Java中，动态数组通常指的是`ArrayList`，它内部使用一个数组来存储元素，当数组容量不足以容纳更多元素时，会自动进行扩容。以下是`ArrayList`扩容的原理和实现实例。

###动态数组扩容原理1. **初始容量**：`ArrayList`在创建时会有一个初始容量，通常是10。
2. **容量计算**：当添加元素时，如果当前容量不足以容纳新元素，`ArrayList`会进行扩容。
3. **扩容策略**：扩容时，`ArrayList`会创建一个新的数组，其容量是原数组容量的1.5倍（向上取整）加上1，这样可以减少扩容的次数，提高效率。
4. **复制元素**：将原数组中的所有元素复制到新数组中。
5. **更新引用**：更新内部数组的引用，使其指向新数组。

### 实现代码示例下面是一个简单的模拟`ArrayList`扩容的Java类实现：

```javaimport java.util.Arrays;

public class DynamicArray<T> {
 private T[] array;
 private int size;

public DynamicArray() {
 this.array = (T[]) new Object[10]; //初始容量为10 this.size =0;
 }

public void add(T element) {
if (size == array.length) {
resize();
 }
 array[size++] = element;
 }

private void resize() {
int newCapacity = (array.length *3) /2 +1; //扩容策略：1.5倍 +1T[] newArray = (T[]) new Object[newCapacity];
 System.arraycopy(array,0, newArray,0, array.length);
 array = newArray;
 }

public T get(int index) {
if (index >= size || index <0) {
 throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
 }
 return array[index];
 }

public int size() {
 return size;
 }

@Override public String toString() {
 return Arrays.toString(Arrays.copyOf(array, size));
 }

public static void main(String[] args) {
DynamicArray<Integer> dynamicArray = new DynamicArray<>();
 for (int i =0; i <20; i++) {
 dynamicArray.add(i);
 System.out.println(dynamicArray);
 }
 }
}
```###代码解释- `DynamicArray`类是一个泛型类，可以存储任何类型的元素。
- `add`方法用于添加元素，如果当前数组容量不足，会调用`resize`方法进行扩容。
- `resize`方法计算新容量，并创建新数组，将原数组元素复制到新数组中，然后更新内部数组引用。
- `get`方法用于获取指定索引的元素。
- `size`方法返回当前数组的大小。
- `toString`方法用于返回数组的字符串表示，方便打印和调试。
- `main`方法演示了如何使用`DynamicArray`类，并展示了扩容的过程。

这个简单的实现展示了`ArrayList`的动态扩容原理，实际的`ArrayList`实现更加复杂和高效。