《面试专题》第二部分 java集合框架List

1、说下Vector和ArrayList、LinkedList联系和区别？分别的使用场景

这道题主要从 线程是否安全、使用场景 两个方面回答问题

线程安全性区别
ArrayList：底层是数组实现，线程不安全，查询和修改非常快，但是增加和删除慢
LinkedList: 底层是双向链表，线程不安全，查询和修改速度慢，但是增加和删除速度快
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}
Vector: 底层是数组实现，线程安全的，增删改查等操作都使用synchronized进行加锁
使用场景

Vector已经很少用了

增加和删除场景多则用LinkedList

查询和修改多则用ArrayList

2、如果需要保证线程安全，ArrayList应该怎么做，用有几种方式？

方法1：自定义List包装类，对增、删、改等操作加锁，保证线程安全性

方法2：使用 Collections.synchronizedList()

Collections.synchronizedList() 生成一个线程安全集合类，改集合类的增删改查等操作均使用 synchronized 关键字保证线程安全

方法3：使用 CopyOnWriteArrayList

CopyOnWriteArrayList 底层的增删改操作，使用 ReentrantLock 可重入锁保证线程安全性，但是 CopyOnWriteArrayList 每次执行都会复制一个新的数组，在大数据场景下会产生两个大数据的数组，占用系统内存，容易产生Full GC

3、了解CopyOnWriteArrayList吗？和 Collections.synchronizedList实现线程安全有什么区别, 使用场景是怎样的？

CopyOnWriteArrayList：执行修改操作时，会拷贝一份新的数组进行操作（add、set、remove等)，代价十分昂贵，在执行完修改后将原来集合指向新的集合来完成修改操作，源码里面用ReentrantLock可重入锁来保证不会有多个线程同时拷贝一份数组
- 场景：读高性能，适用读操作远远大于写操作的场景中使用(读的时候是不需要加锁的，直接获取，删除和增加是需要加锁的, 读多写少)
Collections.synchronizedList：线程安全的原因是因为它几乎在每个方法中都使用了synchronized同步*锁
- 场景：写操作性能比CopyOnWriteArrayList好，读操作性能并不如CopyOnWriteArrayList

4、CopyOnWriteArrayList 的设计思想是怎样的,有什么缺点？

答案：设计思想：读写分离+最终一致

缺点：内存占用问题,写时复制机制,内存里会同时驻扎两个对象的内存，旧的对象和新写入的对象,如果对象大则容易发生Yong GC和Full GC

5、说下ArrayList的扩容机制是怎样的？

注意：JDK1.7之前ArrayList默认大小是10，JDk1.7之后是0

未指定集合容量，默认是0，若已经指定大小则集合大小为指定的；
当集合第一次添加元素的时候，集合大小扩容为10
ArrayList的元素个数大于其容量，扩容的大小= 原始大小+原始大小/2

6、设计一个简单的ArrayList【需要包含构造函数(有参和无参)、add(obj)、扩容机制】

//计算容量+确保容量
private void ensureCapacityInternal(int minCapacity){
    //如果是初次扩容，则使用默认的容量
    if(elementData == EMPTY_ELEMENT_DATA){
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //是否需要扩容，需要的最少容量大于现在数组的长度则要扩容
    if(minCapacity - elementData.length > 0){
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity>>1);
        //如果新容量 < 最小容量， 则讲最新的容量赋值给新的容量
        if(newCapacity - minCapacity < 0){
            newCapacity = minCapacity;
        }
        //创建新数组
        Object[] objects = new Object[newCapacity];
        //将旧的数组复制到新的数组里面
        System.arraycopy(elementData,0, objects,0,elementData.length);
        //修改引用
        elementData = objects;
    }
}

7、设计一个简单的ArrayList【remove(index)、get(index) 、indexOf(o) ,set(int index,Object obj)】