Java-集合框架

• Java 集合框架主要包括两种类型的容器，一种是集合（Collection），存储一个元素集合，另一种是图（Map），存储键/值对映射。

• Java集合类主要由两个根接口Collection和Map派生出来的，Collection派生出了三个子接口：List、Set、Queue（Java5新增的队列），因此Java集合大致也可分成List、Set、Queue、Map四种接口体系，（注意：Map不是Collection的子接口）。

List

ArrayList

• 以数组实现。节约空间，但数组有容量限制。超出限制时会增加50%容量，用 System.arraycopy()复制到新的数组，因此最好能给出数组大小的预估值。默 认第一次插入元素时创建大小为10的数组。
• 按数组下标访问元素—get(i)/set(i,e) 的性能很高，这是数组的基本优势。
  直接在数组末尾加入元素—add(e)的性能也高，但如果按下标插入、删除元素 —add(i,e), remove(i), remove(e)，则要用System.arraycopy()来移动部分受影 响的元素，性能就变差了，这是基本劣势。
• ArrayList是一个相对来说比较简单的数据结构，最重要的一点就是它的自动扩容， 可以认为就是我们常说的“动态数组”。

LinkedList

• 以双向链表实现。链表无容量限制，但双向链表本身使用了更多空间，也需要 额外的链表指针操作。
• 按下标访问元素—get(i)/set(i,e) 要悲剧的遍历链表将指针移动到位(如果i>数组 大小的一半，会从末尾移起)。
• 插入、删除元素时修改前后节点的指针即可，但还是要遍历部分链表的指针才 能移动到下标所指的位置，只有在链表两头的操作—add()，addFirst()， removeLast()或用iterator()上的remove()能省掉指针的移动。

Set

Set继承于Collection接口，是一个不允许出现重复元素，并且无序的集合

HashSet

• HashSet是哈希表结构，主要利用HashMap的key来存储元素，计算插入元素的hashCode来获取元素在集合中的位置；
• HashSet实现Set接口，底层由HashMap(后面讲解)来实现，为哈希表结构，新增元素相当于HashMap的key，value默认为一个固定的Object。在我看来，HashSet相当于一个阉割版的HashMap;

TreeSet

• TreeSet具有排序功能，分为自然排序(123456)和自定义排序两类，默认是自然排序；在程序中，我们可以按照任意顺序将元素插入到集合中，等到遍历时TreeSet会按照一定顺序输出--倒序或者升序；

Queue

• 队列是数据结构中比较重要的一种类型（是一种数据结构），它支持 FIFO，尾部添加、头部删除（先进队列的元素先出队列），跟我们生活中的排队类似。

Map

HashMap

TreeMap

LinkedHashMap