java集合框架总结
Java集合框架
数据结构是以某种形式将数据组织在一起的集合，它不仅存储数据，还支持访问和处理数据的操作。Java提供了几个能有效地组织和操作数据的数据结构，这些数据结构通常称为Java集合框架。在平常的学习开发中，灵活熟练地使用这些集合框架，可以很明显地提高我们的开发效率，当然仅仅会用还是不够的，理解其中的设计思想与原理才能更好地提高我们的开发水平。
1.Collection接口
从图中可以知道Collection 有三个子接口List,Set,Queue和一个直接实现类AbstractCollection
1.1.List接口：
List接口的特点是：有序，可重复
List接口的常用实现类有ArrayList，Vector，LinkedList
1.1.1.ArrayList实现类
ArrayList底层依赖数组，它封装了一个Object[]类型的数组。而数组的优点就是方便查询。但是对于元素的增删效率较低。
其构造方法有：1.ArrayList()无参构造，默认初始化集合容量，大小为10；
2.ArrayList(int initialCapacity)有参构造，自定义集合容量。
Arraylist在对元素进行添加操作的时候 在添加元素之前都会进行扩容检测，在添加元素的时候，会调用ensureCapacityInternal方法来判断是否需要扩容，当minCapacity（也就是add方法中的（size+1））大于数组长度时，将调用grow方法真正的进行扩容操作，切扩容1.5倍，最后，将旧数组复制元素到新数组完成扩容操作。
ArrayList总结：
1.ArrayList底层依赖数组来实现，查询效率较高，增删效率较低
2.ArrayList中的元素有序、可重复、允许null值
3.ArrayList会自动进行扩容1.5倍。初始化时尽量指定初始容量，可避免频繁扩容，影响程序执行效率
4.线程不安全，适用于单线程环境。
1.1.2.Vector实现类
Vector的底层实现与ArrayLIst一样，也是依赖数组。
Vector总结：
1.Vector底层依赖数组来实现，查询效率较高，增删效率较低
2.Vector中的元素有序、可重复、允许null值，添加单个元素的话，只能添加到集合末尾
3.Vector会自动进行扩容。扩容后的容量由增量来决定，（2倍 or 原容量+增量）
4.大多数方法用关键字synchronized修饰，线程安全。
1.1.3.LinkedList实现类
LinkedList底层依赖链表，而链表的优点就是方便增删节点。LinkedList集合容量默认为空，没有扩容的概念。
因为LinkedList无法随机访问，只能通过遍历的方式找到相应的节点所以会造成查找效率低
LinkedList总结：
1.LinkedList底层依赖双向循环链表实现，增删效率较高，查询效率较低
2.LinkedList中的元素有序、可重复、允许null值
3.线程不安全，适用于单线程环境。
1.2.Set接口
特点：元素无序(素存取顺序不一致),元素不可以重复
其实现类有：HashSet，LinkedHashSet，TreeSet
1.2.1. HashSet实现类
特点：其底层数据结构是哈希表，线程不安全,效率高,允许存储null元素,元素无序且唯一，哈希表:具有数组和链表的特点。
1.2.2. LinkedHashSet实现类
LinkedHashSet是HashSet的有序版本，它在所有元素之间维护一个双向链表。当需要维护迭代顺序时，使用这个类。在遍历HashSet时，顺序是不可预知的，而LinkedHashSet让我们按插入顺序遍历元素。当使用迭代器循环访问LinkedHashSet时，元素将按照插入的顺序返回。
1.2.3. TreeSet实现类
特点：无序（指的时存储顺序和取出顺序不同），但是内部其实有集合本身的排序方式(注：但是,添加到TreeSet中的数据类型必须是相同的），唯一（无重复元素），非线程安全
其底层数据结构是红黑树(是一个自平衡的二叉树)。
保证元素的排序方式有两种1.自然排序，2.比较器排序。
HashSet和TreeSet是Set接口的典型实现。对于HashSet和TreeSet如何选择？
HashSet的性能总是比TreeSet好，特别是最常用的添加，查询元素等操作。TreeSet需要额外的红黑树算法来维护集合元素的次序。只有当需要一个保持排序的Set时候，才应该使用TreeSet。否则都应该使用HashSet。
1.3.Queue集合
Queue用于模拟队列这种数据结构。队列通常是指“先进先出（FIFO）”的容器。队列的头部保存在队列中存放时间最长的元素，尾部保存存放时间最短的元素。新元素插入到队列的尾部，取出元素会返回队列头部的元素。通常，队列不允许随机访问队列中的元素。
1.3.1.PriorityQueue实现类
PriorityQueue是一种比较标准的队列实现类，而不是绝对标准的。这是因为PriorityQueue保存队列元素的顺序不是按照元素添加的顺序来保存的，而是在添加元素的时候对元素的大小排序后再保存的。因此在PriorityQueue中使用peek()或pool()取出队列中头部的元素，取出的不是最先添加的元素，而是最小的元素。
1.3.2. LinkedList实现类
LinkedList是List接口的实现类，因此它可以是一个集合，可以根据索引来随机访问集合中的元素。此外，它还是Duque接口的实现类，因此也可以作为一个双端队列，或者栈来使用。
1.3.3．集合中集中特殊的queue
1.优先级队列: 优先级队列 是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。
2. 双端队列: 双端队列是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行
3.阻塞队列: 阻塞队列与普通队列的区别在于，当队列是空的时，从队列中获取元素的操作将会被阻塞，或者当队列是满时，往队列里添加元素的操作会被阻塞。试图从空的阻塞队列中获取元素的线程将会被阻塞，直到其他的线程往空的队列插入新的元素。同样，试图往已满的阻塞队列中添加新元素的线程同样也会被阻塞，直到其他的线程使队列重新变得空闲起来
2.Map接口
2.1.HashMap实现类：
实现原理：HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。
特点：HashMap是线程不安全的，HashMap可以使用null作为key或value，元素是无序的，而且顺序会不定时改变，插入、获取的时间复杂度基本是 O(1)
HashMap的两种遍历方式：
1.效率高
Map map = new HashMap();
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Object key = entry.getKey();
Object val = entry.getValue();
}
2.效率低
Map map = new HashMap();
Iterator iter = map.keySet().iterator();
while (iter.hasNext()) {
Object key = iter.next();
Object val = map.get(key);
}
2.2. Hashtable实现类：
实现原理：和 HashMap 一样，Hashtable 也是一个散列表，它存储的内容是键值对
特点：Hashtable是线程安全的，Hashtable不允许使用null作为key和value。
HashTable的遍历方式：
//1、使用keys()
Enumeration<String> en1 = table.keys();
while(en1.hasMoreElements()) {
en1.nextElement();
}
//2、使用elements()
Enumeration<String> en2 = table.elements();
while(en2.hasMoreElements()) {
en2.nextElement();
}
//3、使用keySet()
Iterator<String> it1 = table.keySet().iterator();
while(it1.hasNext()) {
it1.next();
}
//4、使用entrySet()
Iterator<Entry<String, String>> it2 = table.entrySet().iterator();
while(it2.hasNext()) {
it2.next();
}
HashMap 和HashTable的比较：
HashMap和Hashtable都是Map接口的典型实现类，它们之间的关系完全类似于Arraylist和Vecctor的关系。
区别：
Hashtable是线程安全的，HashMap是线程不安全的，所以HashMap比Hashtable的性能高一点。
Hashtable不允许使用null作为key和value；但HashMap可以使用null作为key或value。
2.3.LinkedHashMap实现类
LinkedHashMap实现类使用链表来维护key-value的次序，可以记住键值对的插入顺序。
特点：非线程安全，遍历输出的顺序与put顺序一致，按访问顺序输出。
2.4.TreeMap实现类
实现原理：底层使用的数据结构是二叉树（红-黑树）
特点：1.无序，不允许重复（无序指元素顺序与添加顺序不一致，但是内部是一个有序的key-value集合）2.TreeMap集合默认会对键进行排序，所以键必须实现自然排序和定制排序中的一种，支持序列化操作