List是一个接口,查关键的实现类有ArrayList和LinkedList
arrayList扩容源码实现如下:
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData,
newCapacity(minCapacity));
}
private Object[] grow() {
return grow(size + 1);
}
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}
可以看到,在graw方法里面进行扩容,将数组容量扩大为原来的1.5倍。 举个例子,如果初始化的值是8,当添加第9个元素的时候,发现数组空间不够,就会进行扩容,扩容之后容量为12. 扩容之后,会调用Arrays.copyOf()方法对数组进行copy。
对于随机index访问的get和set方法,ArrayList的速度要优于LinkedList,因为ArrayList直接通过数组下标直接找到元素;LinkedList要移动指针遍历每一个元素直到找到为止。 新增和删除元素,LinkedList的速度要优于ArrayList,因为ArrayList在新增和删除元素的时候,可能会扩容和复制数组,而LinkedList的新增和删除操作只需要修改指针即可。 因为ArrayList适用于查询多,增删少的场景,而LinkedList适用与查询少,增删多的场景
List以索引来存取元素,有序的,元素是允许重复的,可以插入多个null值,Set不能存放重复元素,无序的,只允许插入一个null。 List底层实现有数组,链表两种方式,Set基于Map实现,Set里的元素值就是Map的键值。
Vector的底层结构是数组,现在基本没有使用Vector了,因为操作Vector效率比较低,相对于ArrayList,它是线程安全的,在扩容的时候容量扩展为原来的2倍。
可以使用Collections.synchronizedList()方法返回一个线程安全的List。 还有另外一种方法,使用CopyOnWriteArrayList。
CopyOnWriteArrayList是一个线程安全的List,底层是通过复制数组的方式来实现的。 所谓的CopyOnWrite,就是写时复制。 当我们往容器添加元素时,不直接往容器添加,而是先将当前容器进行复制,复制出一个新的容器,然后往新的容器添加元素,添加完元素之后,再将原容器引入指向新容器。 这样做的好处就是可以对CopyOnWrite容器进行并发的读而不需要加锁,因为当前容器不会被修改。
主要有以下俩个问题:
可以使用List自身的sort方法,或者使用Collections.sort(list)方法。
如果使用foreach删除元素的话,会导致快速失败问题,可以使用迭代器的remove方法,避免快速失败问题。