ArrayList:底层是数组，初始容量是10，若存入数量达到11即触发扩容方法，容量扩容百分之50。
int newCapacity =oldCapacity + (oldCapacity >> 1);
elementData = Arrays.copyOf(elementData, newCapacity);
每次调用add或remove方法，modCount都会加一，这个值会在checkForComodification方法中作为判断条件决定是否抛出异常。
LinkedList：底层是继承AbstractSequentialList的双向循环链表。它也可以被当作堆栈、队列或双端队列进行操作，每次调用add方法都是添加至尾部，无论LInkedList大小，每次添加所需时间都是固定的（只需开辟最后一个节点的空间，塞值），
在删除可插入对象的动作时，为什么ArrayList的效率会比较低呢?
解析:因为ArrayList是使用数组实现的,若要从数组中删除或插入某一个对象，需要移动后段的数组元素，从而会重新调整索引顺序,调整索引顺序会消耗一定的时间，所以速度上就会比LinkedList要慢许多. 相反,LinkedList是使用链表实现的,若要从链表中删除或插入某一个对象,只需要改变前后对象的引用即可!
Vector:底层是对象数组，初始容量是10，扩容百分之百。
int newCapacity
= oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);
底层方法都用synchronized方法保证并发安全。所以效率低。且调用remove方法时， 不会调节底层数组大小。
Vector扩展：Vector所有方法都上锁，单个方法被调用是都是线程安全的，但是对它的复合操作无法保证其线程安全。
例如定义该方法：public Object deleteLast(Vector v){
int lastIndex = v.size()-1;
v.remove(lastIndex);
}
Remove源码：public synchronized E remove(int index) {
modCount++;
if (index >= elementCount)
throw newArrayIndexOutOfBoundsException(index);
E oldValue = elementData(index);
int numMoved = elementCount - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData,index, numMoved);
elementData[--elementCount] = null; // Let gcdo its work
return oldValue;
}
Size和remove方法都是线程安全的，但在该deleteLast方法中，多线程操作可能会抛 出异常。AB线程同时进入 deleteLast方法内，A方法执行到了remove，B方法执行到 size，A先删除，B就抛异常。
CopyOnWriteArrayList:实现了List、RandomAccess接口，底层使用ReentrantLock支持并发操作，调用add 方法时，上锁后，获得当前数组，数组扩容+1，新数组插入数据后将数组引用指向新数 组，释放锁。另一个add(index,value)方法，在插入值时，先判断该Index是否有效且位 置上没存值，若没存则重复上述划线操作；若有值，则
newElements = new Object[len + 1];
System.arraycopy(elements, 0,newElements, 0, index);
System.arraycopy(elements,index, newElements, index + 1,numMoved);
删除方法与上述斜体字操作类似，若index位置在末尾则直接缩减数组大小，否则
Object[] newElements = new Object[len - 1];
System.arraycopy(elements, 0,newElements, 0, index);
System.arraycopy(elements,index + 1, newElements, index,numMoved);
setArray(newElements);
LinkedList以及ArrayList的迭代效率比较
ArrayList实现了RandomAccess接口，LinkedList没有实现。
实现RandomAccess接口的意思：http://www.jb51.net/article/92127.htm
结论：ArrayList使用最普通的for循环遍历最快，LinkedList使用foreach循环较为 快（*LinkedList使用foreach遍历巨慢，foreach底层调用Iterator遍历*）
如果集合类是RandomAccess的实现，则尽量用for(int i = 0; i < size; i++) 来遍历而不要用Iterator迭代器来遍历。
反过来，如果List是Sequence List，则最好用迭代器来进行迭代。
JDK中说的很清楚，在对List特别是Huge size的List的遍历算法中，要尽量来判断是属于RandomAccess(如ArrayList)还是Sequence List (如LinkedList），因为适合RandomAccess List的遍历算法，用在Sequence List上就差别很大
Vector和ArrayList的区别
实现原理都是通过数组实现，查询速度快，增加、删除、修改速度慢，区别在于vector是线程安全的，ArrayList是线程不安全的，但是效率高。
ArrayList 和 LinkedList区别
1. 随机访问get和set，ArrayList速度优于LinkedList，因为LinkedList需要移动指针
2. 对于add 和 remove操作，LinkedList速度优于ArrayList，因为ArrayList需要移动数据
CopyOnWriteArrayList和 ArrayList的区别：
1. 每次调用remove 和 add方法都会对modCount加1，这个值会在checkForComodification方法中作为判断条件决定是否抛出异常。
2. CopyOnWriteArrayList代码底层有重入锁，可以支持并发，它每次改动都会拷贝一个副本数组，在副本数组操作后，改变引用指向副本数组。
3. CopyOnWriteArrayList的缺点就是每个线程操作它都需要拷贝一个副本数组， 如果副本数组比较大则会占用大内存，造成多次垃圾回收。
假如多个线程一起操作CopyOnWriteArrayList，一个线程修改，一个线程读取，则读取到旧数据，所以CopyOnWriteArrayList只能保证最终的一致性，不能保证实时一致性。它适用于读操作远多于写操作的处理，例如缓存。
HashMap和HashTable的区别：
1.HashMap不是线程安全的 HastMap是一个接口 是map接口的子接口，是将键映射到值的对象，其中键和值都是对象，并且不能包含重复键，但可以包含重复值。HashMap允许null key和null value，而hashtable不允许。
2.HashTable是线程安全的一个Collection。
3.HashMap是Hashtable的轻量级实现（非线程安全的实现），他们都完成了Map接口，主要区别在于HashMap允许空（null）键值（key）,由于非线程安全，效率上可能高于Hashtable。
HashMap允许将null作为一个entry的key或者value，而Hashtable不允许。
HashMap把Hashtable的contains方法去掉了，改成containsvalue和containsKey。
a) HashMap底层是由数组+链表+红黑树构成。默认容量是16，加载因子是0.75，链表转红黑树的阈值是8。初始化HashMap有三种方法（无参，带初始容量，带初始容量及加载因子），其中后两种运用了门面模式（其实是一个方法），put值的时候先判断是否需要调用resize方法扩容.若resize后需要rehash重新计算Key对应的值（位置）再进行插入。HashMap的时间复杂度是O(n).允许存null
b) HashTable底层数组+链表。默认容量11，加载因子是0.75.初始化HashTable有三种方法（无参，带初始容量，带初始容量及加载因子），后两种也运用了门面模式，put值得时候先计算key的hash对应的Index，然后遍历该节点位置的值，若key相同则替换旧值，否则新开辟一个Entry存放key value.HashTable所有方法都带有synchronized,不支持存null.
c) ConcurrentHashMap底层是数组+链表+红黑树。默认容量16，加载因子0.75，链表转红黑树的阈值是8,。初始化ConcurrentHashMap有四种方法（无参，带初始容量，带初始容量及加载因子，带Map）。ConcurrentHashMap不支持存null,put值得时候先判断table是否为空，否则初始化table,然后计算key的hash后的Index，若该位置为空则直接新加节点存且过程不上锁。若该位置有值则上分段锁保证并发安全。（HashTable缩小版）
网友评论