doc/后端/Java/JAVA高阶/ArrayList/ArrayList源码分析.md

概念回顾

ArrayList：源码难点 扩容和缩容 存放元素：有序 线程是否安全：不安全 核心方法：get（下标查询） add 底层数据结构：数组基于object类型

为什么get方法是index下标？

时间复杂度的原因 O(1) O(n) O(lgn) 基于下标查询就是O(1) 基于元素值查询就是O(n)-----链表

扩容方法

private void ensureExplicitCapacity(int minCapacity) {
	// 线程同步，不能在遍历的时候进行添加或者删除操作
    modCount++;

    // 判断是否需要扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
	// 初始化容量为0
    int oldCapacity = elementData.length;
    // 新的容量还是为0
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
    	// 新的容量为10，只有第一次初始化会走这个判断
        newCapacity = minCapacity;
    // 这个判断正常不会走
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 扩容
    elementData = Arrays.copyOf(elementData, newCapacity);
}

每次扩容，容量增加1.5倍

缩容方法

注意hashmap集合没有缩容，因为缩容需要重新计算index值 基于value值删除复杂度为O(n)，需要考虑缩容问题

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

快速覆盖

private void fastRemove(int index) {
	// 线程同步，不能在遍历的时候进行添加或者删除操作
    modCount++;
    // 计算删除index后面的所有元素有多少个
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

arraycopy(Object src, int srcPos,Object dest, int destPos,int length);

Object src：原数组 int srcPos：从元数据的起始位置开始 Object dest：目标数组 int destPos：从目标数组的开始起始位置 int length：要copy的数组长度

ArrayList与vector的区别

相同点：都是基于数组实现，默认初始容量为10 不同点：

1. ArrayList线程不安全，vector线程安全。
2. ArrayList扩容为原容量的1.5倍，vector为原来的2倍---capacityIncrement可以自定义扩容的大小

HashSet底层实现原理

HashSet：基于HashMap实现

思考点： HashSet为什么是无序的？因为HashMap的key不允许重复 hash+equals，hash值排 序 HashSet底层数据结构模型：基于hashmap实现，key为hashset存放的元素，value是空值 缺点：比较占用内存

LinkedList

底层基于双向链表结构实现 查询的时间复杂度为O(n)

为什么需要一个变量记录头结点？ 为了后期遍历数据知道从哪里开始！