今天开始学习Java基础八股文，先从我用的最多的一个数据结构开始看起。虽然我学Java接触了这个概念快两三年了，但是不看源码还是不知道ArrayList的具体实现。

Collections

集合分为两大类，Collection是单列集合，包含常用的Set，List，Queue等，其中Set里面使用HashSet比较多，List里面使用Arraylist比较多，Queue中有一个优先队列PriorityQueue的概念。

Set：HashSet，LinkedHashSet，SortedSet和继承其的TreeSet
List：ArrayList，LinkedList，Vector
Queue：PriorityQueue

还有一类是双列集合Map，使用的比较多的有HashMap，LinkedHashMap，TreeMap，HashTable

List

首先我们先复习一下顺序存储和链式存储的区别以及时间复杂度和空间复杂度。

顺序存储：

支持随机查找，空间连续，数据密度大（不像链表那样有额外的指针空间），删除和插入麻烦，不适合频繁在其中删除插入

插入：如果在表尾就不需要移动元素为o(1)，如果是在内部，需要移动的期望为 (1+2+3+…+n)/(n+1) = n(n+1)/2(n+1) = n/2，时间复杂度为o(n)。
删除：如果在表尾删除也不用移动，如果在内部，期望为 (1+2+…+n-1)/n = n(n-1)/2n = (n-1)/2 也是o(n)
查找：平均查找期望 (1+2+..+n)/n = (n+1)/2 也为o(n)

链式存储：

不支持随机查找，但是相对于顺序的插入和删除效率还是高那么一点，空间不连续，数据的密度小，因为要存指针。

插入：插入这个操作本身是o(1)的只需要改指针，但是要找到这个插入的位置是需要o(n)，删除同理。
查找：不支持随机查找，每次找都需要从头开始找(双向链表可以解决这个问题)，也是o(n)

ArrayList

ArrayList和Vector是基于数组实现的，但是是动态的，每次添加之前都要判断是否下一个就要超过了，如果溢出就要重新开辟一个更长的数组。

成员变量

/**
 * 默认的初始容量为10
 */
private static final int DEFAULT_CAPACITY = 10;
/**
 * 如果初始化为new ArrayList(n)，但是还没有在这个里面加东西的时候，elementData就是这个
 */
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
 * 如果初始化为new ArrayList()，但是还没有元素添加的时候，就是这个Default，为了和上面的区分开
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
 * 实际存储的数组结构
 */
transient Object[] elementData;

private int size;

构造方法

当initialCapacity给了是0或者没有提供的时候，不进行实例化，等到有元素进来了在进行扩容

/**
 * 有参数的：只要有这个参数就是EMPTY_ELEMENTDATA，跟下面这个区分开
 * 可以按照指定容量初始化
 */
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

/**
 * 无参数构造方法：DEFAULTCAPACITY_EMPTY_ELEMENTDATA来区分
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

add添加方法流程

public boolean add(E e) {
    //每一次加之前先检查size+1不会大于数组最大值
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    //calculateCapacity(elementData, minCapacity)如果是无参的返回就是10
    //如果不是返回的就是minCapacity
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    //如果是无参的初始化，那么就在当前这个容量和10之间选一个最大的
    //但是一般来说第一个元素size肯定是0吧，这里传来的minCapacity估计是1
    //所以第一次应该是初始化10个，对于无参构造方法而言
    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;
    //1.5倍，oldCapacity右移一位代表/2，1+0.5
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //只有第一次会这样minCapacity给的是10，这个肯定是<0
    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);
}

ArrayList的线程不安全问题

ArrayList不是线程安全的

非同步操作： ArrayList 的方法并没有进行同步处理，因此在多线程环境下，多个线程可以同时访问和修改 ArrayList 的状态。

不保证操作的原子性： ArrayList 的操作（例如添加、删除、修改元素等）并不是原子操作，它们可能会分解成多个步骤。在多线程环境下，如果一个线程在执行操作的过程中被另一个线程中断，可能会导致数据不一致的情况发生

迭代器不支持并发修改：在使用迭代器遍历 ArrayList 的过程中，如果其他线程对 ArrayList 进行了结构性修改（如添加或删除元素），则会抛出 ConcurrentModificationException 异常

举个例子，这里会报错，CopyOnWriteArrayList就不会

public static void main(String[] args) {
    ArrayListTest arrayListTest = new ArrayListTest();
    VectorTest vectorTest = new VectorTest();
    for (int i = 0; i < 10; i++) {
        new Thread(() -> {
            for (int j = 0; j < 1000; j++) {
                arrayListTest.insert(j);
            }
            System.out.println(arrayListTest.getSize());
        }).start();
    }

    // 等待所有线程执行完毕
    try {
        Thread.sleep(1000);
    } catch (InterruptedException e) {
        e.printStackTrace();
    }
}

有几种解决方法

CopyOnWriteArrayList：使用 java.util.concurrent 包中提供的线程安全的集合类，例如 CopyOnWriteArrayList，它通过在写操作时复制整个数组来实现线程安全，适用于读多写少的场景。

1 2	List<String> threadSafeList = new CopyOnWriteArrayList<>();

使用同步机制：使用 Collections 工具类提供的 synchronizedList 方法，将 ArrayList 包装成一个同步的 List，这样可以保证在多线程环境下对 ArrayList 的操作是线程安全的，但性能可能会受到影响。
1
2
List<String> synchronizedList = Collections.synchronizedList(new ArrayList<>());

几个面试题

new ArrayList(10)grow了几次

答：0次，因为这个在有参构造函数里面已经有了

new ArrayList(0)和new ArrayList()在第一次扩容后都是多少

new ArrayList()和new ArrayList(0)执行完之后elementData都是空数组，但是这两个空数组的内存地址是不一样的。if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) 这一段代码在new(0)的时候是不会走的，因为比的是地址，所以返回值是1，最后结果也是1
所以new ArrayList(0)第一次扩容是1，new ArrayList()第一次扩容是10

数组和list之间的转换？

数组->list:Arrays.asList()

list->数组: list.toArray(n)

数组转List ，使用JDK中java.util.Arrays工具类的asList方法
List转数组，使用List的toArray方法。无参toArray方法返回 Object数组，传入初始化长度的数组对象，返回该对象数组

用Arrays.asList转List后，如果修改了数组内容，list受影响吗

Arrays.asList转换list之后，如果修改了数组的内容，list会受影响，
因为它的底层使用的Arrays类中的一个内部类ArrayList来构造的集合，
在这个集合的构造器中，把我们传入的这个集合进行了包装而已，最终指向的都是同一个内存地址

List用toArray转数组后，如果修改了List内容，数组受影响吗

list用了toArray转数组后，如果修改了list内容，数组不会影响，当调用了toArray以后，在底层是它是进行了数组的拷贝，跟原来的元素就没啥关系了，所以即使list修改了以后，数组也不受影响

LinkedList

特点：

基于双向链表实现
也符合链式存储的一系列优缺点
线程不安全，因为是链表，如何安全呢，跟上面的ArrayList一样使用Collections.synchronizedList(new ArrayList<>());

Vector

特点：

也是基于顺序存储（数组结构），但是增长的策略与ArrayList不同，而且每次增长2倍
线程安全，这使其性能略逊于ArrayList
Stack是基于Vector的

对比

名称	基于数据结构	线程是否安全
ArrayList	数组	否
Vector	数组	是
LinkedList	双向链表	否

Collections集合篇-List

文章目录