1.单列集合List
1.1 Vector和ArrayList以及LinkedList区别和联系，以及分别的应用场景
线程安全：
Vector：如果创建Vector时没有指定容量，则默认容量为10，底层基于数组实现，线程是安全的，底层采用synchronized同步方法进行加锁
/**
* Adds the specified component to the end of this vector,
* increasing its size by one. The capacity of this vector is
* increased if its size becomes greater than its capacity.
*
* <p>This method is identical in functionality to the
* {@link #add(Object) add(E)}
* method (which is part of the {@link List} interface).
*
* @param obj the component to be added
*/
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}
ArrayList：底层基于数组，线程不安全，查询和修改效率高，但是增加和删除效率低
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
LinkedList：底层双向链表结构，线程不安全，查询和修改效率低，但是增加和删除效率高
/**
* Appends the specified element to the end of this list.
*
* <p>This method is equivalent to {@link #addLast}.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
linkLast(e);
return true;
}
使用场景：
1.Vector很少用
2.如果需要大量的添加和删除则可以选择LinkedList
3.如果需要大量的查询和修改则可以选择ArrayList
1.2 如果要保证ArraList线程安全，有几种方式？
1.2.1 自己表写一个ArrayList集合类，根据业务一般来说，add/set/remove加锁
1.2.2 利用List<Object> list = Collections.synchronizedList(new ArrayList<>()); //采用synchronized加锁
1.2.3 new CopyOnWriteArrayList<>().add(""); //采用 ReentrantLock加锁
1.3 了解CopyOnWriteArrayList底层？，CopyOnWriteArrayList与Collections.synchronizedList有什么区别
1.3.1 CopyOnWriteArrayList底层实现：
CopyOnWriteArrayList在执行修改操作的时候，会复制一份新的数组数据，代价昂贵，修改过后将原来的集合指向到新的集合完成操作
使用ReentrantLock保证多线程环境下的集合安全
public boolean add(E e) {
final ReentrantLock lock = this.lock; //获取了一把锁
lock.lock(); //加锁
try {
Object[] elements = getArray(); //获取当前数组数据，给elements
int len = elements.length; //记录当前数组的长度
Object[] newElements = Arrays.copyOf(elements, len + 1); //复制一个新的数组
newElements[len] = e; //将数据填入到新数组当中
setArray(newElements); //将当前array指针指向到新的数据
return true;
} finally {
lock.unlock(); //释放锁
}
}
CopyOnWriteArrayList应用场景：适用于读取操作远大于写操作场景（底层get读取时没有加锁，直接获取）
1.3.2 Collections.synchronizedList几乎底层方法都加上了synchronized的锁
场景：写操作的性能比CopyOnWriteArrayList要好，但是读取的性能不如CopyOnWriteArrayList
1.4 CopyOnWriteArrayList设计思想是怎么样的，有什么缺点？
设计思想：读写分离，最终一致
缺点：内存占用，由于写时复制，内存中就会出现两个对象占用空间，如果对象大则容易发生YongGC和FullGC
1.5 说一下ArrayList扩容机制是怎么样的
1.7 以及之前版本JDK，首先从默认大小来讲，默认为10
1.8 ArrayList集合大小如果创建时没有指定，则默认为0，若已经指定集合大小，则初始值为指
当第一次添加数据的时候，集合大小扩容为10，第二次及其后续每次按照int oldCapacity = elementData.length; newCapacity = oldCapacity+(oldCapacity>>1)
1.6 手写ArrayList集合框架
//代表集合真正存储的数据
private transient Object [] elementData;
//代表默认情况下，创建集合时，是一个空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//当前集合大小
private Integer size;
//默认初始容量
private static final Integer DEFAULT_CAPACITY=10;
1.6.1 创建一个ArrayList首先通过构建MyArrayList
public MyArrayList(){
//创建一个空数组
this.elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public MyArrayList(int initalCapaCity){
if(initalCapaCity>0){
this.elementData=new Object[initalCapaCity];
}else if(initalCapaCity==0){
this.elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}else{
throw new IllegalArgumentException("参数错误");
}
}
扩容机制
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
//ensureCapacityInternal方法接受了size+1作为minCapacity，并且判断如果数组是空数组，那么10和minCapacity的较大值就作为新的minCapacity。
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0) //如果其元素个数大于其容量，则进行扩容；
grow(minCapacity);
}
//判断传入的minCapacity和elementData.length的大小，如果elementData.length大于minCapacity，说明数组容量够用，就不需要进行扩容，
//反之，则传入minCapacity到grow()方法中，进行扩容
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length; //原来的容量
int newCapacity = oldCapacity + (oldCapacity >> 1); //新的容量，原来容量的1.5倍
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0) //如果大于ArrayList可以允许的最大容量，则设置为最大容量
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity); //最终进行扩容，生成一个1.5倍元素
}