前言：在java开发中我们肯定会大量的使用集合，在这里我将总结常见的集合类，每个集合类的优点和缺点，以便我们能更好的使用集合。下面我用一幅图来表示
其中淡绿色的表示接口，红色的表示我们经常使用的类。
1：基本概念
Java容器类类库的用途是保存对象，可以将其分为2个概念。
1.1：Collection
一个独立元素的序列，这些元素都服从一条或多条规则。其中List必须按照插入的顺序保存元素、Set不能有重复的元素、Queue按照排队规则来确定对象的产生顺序（通常也是和插入顺序相同）
1.2：Map
一组成对的值键对对象，允许用键来查找值。ArrayList允许我们用数字来查找值，它是将数字和对象联系在一起。而Map允许我们使用一个对象来查找某个对象，它也被称为关联数组。或者叫做字典。
2：List
List承诺可以将元素维护在特定的序列中。List接口在Collection的基础上加入了大量的方法，使得可以在List中间可以插入和移除元素。下面主要介绍2种List
2.1：基本的ArrayList
它的优点在于随机访问元素快，但是在中间插入和移除比较慢
那么现在我们就一起来看看为什么ArrayList随机访问快，而插入移除比较慢。先说关于ArrayList的初始化。
ArrayList有三种方式进行初始化如下
private transient Object[] elementData;
public ArrayList() {
this(10);
}
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
</div>
我们可以看出ArrayList其实就是采用的是数组（默认是长度为10的数组）。所有ArrayList在读取的时候是具有和数组一样的效率，它的时间复杂度为1。
插入尾部就是elementData[size++] = e;当然中间会进行扩容。现在主要说插入中间为什么相对来说比较慢源码如下
public void add(int index, E element) {
rangeCheckForAdd(index);//验证（可以不考虑）
ensureCapacityInternal(size + 1); // Increments modCount!!（超过当前数组长度进行扩容）
System.arraycopy(elementData, index, elementData, index + 1,
size - index);(核心代码)
elementData[index] = element;
size++;
}
</div>
System.arraycopy(elementData, index, elementData, index + 1)第一个参数是源数组，源数组起始位置，目标数组，目标数组起始位置，复制数组元素数目。那么这个意思就是从index索性处每个元素向后移动一位，最后把索引为index空出来，并将element赋值给它。这样一来我们并不知道要插入哪个位置，所以会进行匹配那么它的时间赋值度就为n。
2.2：LinkedList
它是通过代价较低在List中间进行插入和移除，提供了优化的顺序访问，但是在随机访问方面相对较慢。但是他的特性功能要比ArrayList强大的多。支持Queue和Stack
ListedList采用的是链式存储。链式存储就会定一个节点Node。包括三部分前驱节点、后继节点以及data值。所以存储存储的时候他的物理地址不一定是连续的。
我们看下它的中间插入实现
从代码我们可以看出先获取插入索引元素的前驱节点，然后把这个元素作为后继节点，然后在创建新的节点，而新的节点前驱节点和获取前驱节点相同，而后继节点则等于要移动的这个元素。所以这里是不需要循环的，从而在插入和删除的时候效率比较高。
我们在来看看查询（我们可以分析出它的效率要比ArrayList低了不少）
3：Set
Set也是一个集合，但是他的特点是不可以有重复的对象，所以Set最常用的就是测试归属性，很容易的询问出某个对象是否存在Set中。并且Set是具有和Collection完全一样的接口，没有额外的功能，只是表现的行为不同。
3.1：HashSet
HashSet查询速度比较快，但是存储的元素是随机的并没有排序，下面我写一段程序看一下
public static void main(String[] args){
/**
* 没有顺序可循，这是因为hashset采用的是散列（处于速度考虑）
*/
Random random=new Random(47);
Set<Integer> intset=new HashSet<Integer>();
for (int i=0;i<10000;i++){
intset.add(random.nextInt(30));
}
System.out.print(intset);
}
</div>
3.2：TreeSet
TreeSet是将元素存储红-黑树结构中，所以存储的结果是有顺序的（所以如果你想要自己存储的集合有顺序那么选择TreeSet）
public static void main(String[] args){
Random random=new Random(47);
Set<Integer> intset=new TreeSet<Integer>();
for (int i=0;i<10000;i++){
intset.add(random.nextInt(30));
}
System.out.print(intset);
}
</div>
关于LinkedHashSet后面再说。
4：Queue
Queue是队列，队列是典型的先进先出的容器，就是从容器的一端放入元素，从另一端取出，并且元素放入容器的顺序和取出的顺序是相同的。LinkedList提供了对Queue的实现，LinkedList向上转型为Queue。其中Queue有offer、peek、element、pool、remove等方法
offer是将元素插入队尾，返回false表示添加失败。peek和element都将在不移除的情况下返回对头，但是peek在对头为null的时候返回null，而element会抛出NoSuchElementException异常。poll和remove方法将移除并返回对头，但是poll在队列为null，而remove会抛出NoSuchElementException异常，以下是例子
public static void main(String[] args){
Queue<Integer> queue=new LinkedList<Integer>();
Random rand=new Random();
for (int i=0;i<10;i++){
queue.offer(rand.nextInt(i+10));
}
printQ(queue);
Queue<Character> qc=new LinkedList<Character>();
for (char c:"HelloWorld".toCharArray()){
qc.offer(c);
}
System.out.println(qc.peek());
printQ(qc);
List<String> mystrings=new LinkedList<String>();
mystrings.add("1");
mystrings.get(0);
Set<String> a=new HashSet<String>();
Set<String> set=new HashSet<String>();
set.add("1");
}
public static void printQ(Queue queue){
while (queue.peek
</div>
从上面的输出的结果我们可以看出结果并不是一个顺序的，没有规则的，这个时候如果想让队列按照规则输出那么这个时候我们就要考虑优先级了，这个时候我们就应该使用PriorityQueue，这个时候如果在调用offer方法插入一个对象的时候，这个对象就会按照优先级在对列中进行排序，默认的情况是自然排序，当然我们可以通过Comparator来修改这个顺序（在下一篇讲解）。PriorityQueue可以确保当你调用peek、pool、remove方法时，获取的元素将是对列中优先级最高的元素。ok我们再次通过代码查看
public static void main(String[] args) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>();
Random rand = new Random();
for (int i = 0; i < 10; i++) {
priorityQueue.offer(rand.nextInt(i + 10));
}
QueueDemo.printQ(priorityQueue);
List<Inte