Java集合类

面试

1. List

• ArrayList：Object[]数组，可以对元素进行快速随机访问，其内部存储是物理连续的。
• Vector：Object[]数组，和ArrayList一样，数组实现，不同的是它支持线程同步。
• LinkedList：双向链表，适合动态插入和删除。并且提供了List结构中没有定义的方法、专门用于操作表头和表尾，可以当做堆、队列和双向队列使用。

1. CopyOnWriteArrayList

歇菜做在一个复制的数组上进行，读操作还是在原始数组上进行，读写分离互不影响。

写操作需要加锁，防止并发写入时导致写入丢失。写操作结束之后需要把原始数组指向新的复制数组。

2. Map

• HashMap：由数组+链表组成的，数组是HashMap的主体，链表是为了解决哈希冲突而存在的。当链表的长度大于8的时候，会将链表转化为红黑树，以减少搜索时间。

• LinkedHashMap：继承自HashMap，所以它的底层仍然基于拉链式散列结构即有数组、链表或红黑树组成。另外，LinkedHashMap在上面结构的基础上，增加了双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序的相关逻辑。

• HashTable：是HashMap的改版，不同之处在于HashMap允许空Key/Value。

• ConcurrentHashMap：线程安全的Map。使用Synchronized以及CAS来操作。新增了TreeBin和ForwardingNode的概念。

• TreeMap：基于红黑树的实现（自平衡的排序二叉树）。键或者键值对的次序是由Comparable或Comparator决定的，TreeMap是唯一带有subMap方法的map，可以放回一个子树。