一、Java集合

List相关面试题

数组

是一种用连续的内存空间存储相同数据类型数据的线性数据结构

例：

int 是4字节，所以一个数字占4个空

寻址公式：a[i] = baseAddress + i * dataTypeSize

直接根据漂移量就能找到数组中的元素，所以数组访问速度很快

ArrayList源码分析

初始化ArrayList

ArrayList<Integer> list = new ArrayList<>();

创建空数组Object[] elementData = {}
初始容量为10
就算是

ArrayList list = new ArrayList(10);

那也只是创建了一个大小为10的数组，容量为10，并没有扩容

添加元素

list.add(1);

调用源码：

public boolean add(E e) {
    modCount++; // 修改计数器
    add(e, elementData, size); // 调用私有添加方法
    return true;
}

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length) { // 检查容量是否已满
        elementData = grow(); // 触发扩容
    }
    elementData[s] = e; // 存入元素
    size = s + 1; // 更新元素数量
}

扩容机制（grow方法）

private Object[] grow() {
    return grow(size + 1); // 传入最小所需容量
}

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0) {
        // 常规扩容：新容量 = 旧容量 + 旧容量/2（约1.5倍）
        int newCapacity = ArraysSupport.newLength(
            oldCapacity,
            minCapacity - oldCapacity,  // 最小扩容增量
            oldCapacity >> 1            // 推荐扩容增量（旧容量的一半）
        );
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        // 首次扩容：使用默认容量10和所需容量的最大值
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

1.扩容策略

操作序列	当前容量	所需最小容量	扩容计算	新容量
首次添加	0	1	max(10, 1) = 10	10
添加第11个元素	10	11	10 + max(1, 10>>1)=10+5=15	15
添加第16个元素	15	16	15 + max(1, 15>>1)=15+7=22	22
添加第23个元素	22	23	22 + max(1, 22>>1)=22+11=33	33