java集合框架

两大基类Collection与Map

在集合框架的类继承体系中，最顶层有两个接口：

• Collection表示一组纯数据
  
  • Set表示不允许有重复元素的集合（A collection that contains no duplicate elements）
  • List表示允许有重复元素的集合（An ordered collection (also known as a sequence)）
  • Queue JDK1.5新增，与上面两个集合类主要是的区分在于Queue主要用于存储数据，而不是处理数据。
• Map表示一组key-value对

Vector和ArrayList

• Vector是线程同步的，所以它也是线程安全的，而ArrayList是线程不安全的。如果不考虑到线程的安全因素，一般用ArrayList效率比较高。

• 如果集合中的元素的数目大于目前集合数组的长度时，Vector增长率为目前数组长度的100%，而ArrayList增长率为目前数组长度的50%。如果在集合中使用数据量比较大的数据，用Vector有一定的优势。如果提前可以预知集合的长度，应该在构造的时候指出集合的长度，避免不停扩容导致的数组申请和释放以及对数组的拷贝带来的性能损失。

ArrayList和LinkedList

• ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。

• 对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。

• 对于新增和删除操作add和remove，LinkedList比较占优势，因为ArrayList要移动数据。 这一点要看实际情况的。若只对单条数据插入或删除，ArrayList的速度反而优于LinkedList。但若是批量随机的插入删除数据，LinkedList的速度大大优于ArrayList. 因为ArrayList每插入一条数据，要移动插入点及之后的所有数据。

HashMap与TreeMap

• HashMap通过hashcode对其内容进行快速查找，而TreeMap中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该使用TreeMap（HashMap中元素的排列顺序是不固定的）。
• 在Map 中插入、删除和定位元素，HashMap是最好的选择。但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。使用HashMap要求添加的键类明确定义了hashCode()和 equals()的实现。

HashTable与HashMap

• 同步性:Hashtable是线程安全的，也就是说是同步的，而HashMap是线程序不安全的，不是同步的。

• HashMap允许存在一个为null的key，多个为null的value 。

• HashTable的key和value都不允许为nul.

• HashTable是一个早期JDK遗留的类，如果要使用线程安全的Map，应该考虑使用效率更高的ConcurrentHashMap。

HashMap、LinkedHashMap、TreeMap

• HashMap不保证顺序，随机取元素最好情况下可以达到O(1)的时间复杂度，最坏情况下可以保证O(logN)的复杂度。

• LinkedHashMap继承自HashMap并通过双向链表维护着元素的插入顺序

• TreeMap通过红黑树维持插入的Key的大小顺序，和效率。随机取元素可以保证O(logN)的复杂度。