严格意义来说，集合类不能算作一种数据结构，但在统一归纳上，依据其底层实现，便于理解，就当成数据结构来统筹在刷题的时候发现有很多关于集合类的问题，是时候总结一波了。
###集合类概述
####为什么使用集合类
数组是很常用的一种的数据结构，我们用它可以满足很多的功能，但有时我们会遇到如下这样的问题：
1、我们需要该容器的长度是不确定的。
2、我们需要它能自动排序。
3、我们需要存储以键值对方式存在的数据。
与数组类似的数据结构——集合类，集合类在Java中有很重要的意义，保存临时数据，管理对象，泛型，Web框架等，很多都大量用到了集合类。
以下是一张集合类图：
Collection接口是集合类的根接口，Java中没有提供这个接口的直接的实现类。但是却让其被继承产生了两个接口，就是Set和List。Set中不能包含重复的元素。List是一个有序的集合，可以包含重复的元素，提供了按索引访问的方式。
Map是Java.util包中的另一个接口，它和Collection接口没有关系，是相互独立的，但是都属于集合类的一部分。Map包含了key-value对。Map不能包含重复的key，但是可以包含相同的value。
Iterator，所有的集合类，都实现了Iterator接口，这是一个用于遍历集合中元素的接口，主要包含以下三种方法：
1.hasNext()是否还有下一个元素。
2.next()返回下一个元素。
3.remove()删除当前元素。
###常见的集合类
####实现Collection接口：Set（无序、不能重复）、List（有序、可重复）
Set接口和List接口的异同
相同点：都实现了Collection接口
不同点：Set接口不保证维护元素的顺序，且元素不能重复。List接口维护元素的顺序，且元素可以重复。
<mark><mark><mark><mark><mark><mark><mark><mark><mark><mark>ArrayList和其他两兄弟的比较</mark></mark></mark></mark></mark></mark></mark></mark></mark></mark>===
ArrayList和Vector
1，vector是线程同步的，所以它也是线程安全的，而arraylist是线程异步的，是不安全的。如果不考虑到线程的安全因素，一般用arraylist效率比较高。
2，如果集合中的元素的数目大于目前集合数组的长度时，vector增长率为目前数组长度的100%，而arraylist增长率为目前数组长度的50%。如果在集合中使用数据量比较大的数据，用vector有一定的优势。
3，如果查找一个指定位置的数据，vector和arraylist使用的时间是相同的，如果频繁的访问数据，这个时候使用vector和arraylist都可以。而如果移动一个指定位置会导致后面的元素都发生移动，这个时候就应该考虑到使用linklist,因为它移动一个指定位置的数据时其它元素不移动。
ArrayList 和Vector是采用数组方式存储数据，此数组元素数大于实际存储的数据以便增加和插入元素，都允许直接序号索引元素，但是插入数据要涉及到数组元素移动等内存操作，所以索引数据快，插入数据慢，Vector由于使用了synchronized方法（线程安全）所以性能上比ArrayList要差，LinkedList使用双向链表实现存储，按序号索引数据需要进行向前或向后遍历，但是插入数据时只需要记录本项的前后项即可，所以插入数度较快。
ArrayList和LinkList
相同点：都实现了Collection接口
不同点：ArrayList基于数组，具有较高的查询速度，而LinkedList基于双向循环链表，具有较快的添加或者删除的速度，二者的区别，其实就是数组和列表的区别。上文有详细的分析。
<mark><mark><mark><mark><mark><mark><mark><mark><mark><mark>HashSet和其他两兄弟的比较</mark></mark></mark></mark></mark></mark></mark></mark></mark></mark>=====
HashSet和TreeSet
TreeSet: 提供排序功能的Set，底层为树结构 。相比较HashSet其查询速度低，如果只是进行元素的查询，我们一般使用HashSet。
HashSet和LinkedHashSet
HashSet，为快速查找而设计的Set。存入HashSet的对象必须实现hashCode()和equals()。
LinkedHashSet，具有HashSet的查询速度，且内部使用链表维护元素的顺序(插入的次序)，于是在使用迭代器遍历Set时，结果会按元素插入的次序显示。
####实现Map接口（键值对、键唯一、值不唯一）：
以HashMap及其实现类为主
我们常用的有Map及其实现类HashMap(LinkedHashMap)，HashTable，TreeMap
最常用的就是HashMap:Map集合中存储的是键值对，键不能重复，值可以重复。根据键得到值，对map集合遍历时先得到键的set集合，对set集合进行遍历，得到相应的值。
在插入值的过程中：HashMap可以插入null的key或value，插入的时候，检查是否已经存在相同的key，如果不存在，则直接插入，如果存在，则用新的value替换旧的value
=<mark><mark><mark>HashMap和其他三兄弟的比较</mark></mark></mark>=================
HashMap和HashTable
相同点：二者都实现了Map接口，因此具有一系列Map接口提供的方法。
不同点：
1，继承不同。
public class Hashtable extends Dictionary implements Map
public class HashMap extends AbstractMap implements Map
2，Hashtable 中的方法是同步的，而HashMap中的方法在缺省情况下是非同步的。在多线程并发的环境下，可以直接使用Hashtable，但是要使用HashMap的话就要自己增加同步处理了。
3，Hashtable中，key和value都不允许出现null值。在HashMap中，null可以作为键，这样的键只有一个；可以有一个或多个键所对应的值为null。当get()方法返回null值时，即可以表示 HashMap中没有该键，也可以表示该键所对应的值为null。因此，在HashMap中不能由get()方法来判断HashMap中是否存在某个键， 而应该用containsKey()方法来判断。
4，两个遍历方式的内部实现上不同。Hashtable、HashMap都使用了 Iterator。而由于历史原因，Hashtable还使用了Enumeration的方式 。
5，哈希值的使用不同，HashTable直接使用对象的hashCode。而HashMap重新计算hash值。而且用与代替求模：
int hash = hash(k);
int i = indexFor(hash, table.length);
6 ， Hashtable和HashMap它们两个内部实现方式的数组的初始大小和扩容的方式。HashTable中hash数组默认大小是11，增加的方式是 old*2+1。HashMap中hash数组的默认大小是16，而且一定是2的指数。
7，Hashtable有contains方法而HashMap没有contains方法
//以下是Hashtable的方法
public synchronized boolean contains(Object value)
public synchronized boolean containsKey(Object key)
public boolean containsValue(Object value)
//以下是HashMap中的方法，注意，没有contains方法，所以，D错误
public boolean containsKey(Object key)
public boolean containsValue(Object value)
这些就是一些比较突出的不同点，实际上他们在实现的过程中会有很多的不同，如初始化的大小、计算hash值的方式等等。毕竟这两个类包含了很多方法，有很重要的功能，所以其他不同点，请感兴趣的读者自己去看源码，去研究。笔者推荐使用HashMap，因为她提供了比HashTable更多的方法，以及较高的效率，如果大家需要在多线程环境中使用，那么用Collections类来做一下同步即可。
HashMap和TreeMap
HashMap具有较高的速度(查询)，TreeMap则提供了按照键进行排序的功能。
HashMap和LinkedHashMap
具有LinkedHashMap的查询速度，且内部使用链表维护元素的顺序(插入的次序)，于是在使用迭代器遍历Map时，结果会按元素插入的次序显示。
##集合类的使用
###Arraylist的基本功能
####基本操作和遍历
package com.xtfggef.list.test;
import java.util.ArrayList;
/**
*
* 关于ArrayList的基本操作
* 其它操作感兴趣的读者可以自己结合源码实现一下
* * @author erqing
*
*/
public class ListTest {
public static void main(String[] args) {
/* 新建一个ArrayList */
ArrayList<String> list = new ArrayList<String>();
System.out.println("初始化大小:" + list.size());
/* 添加元素 */
list.add("zzz");
list.add("egg");
list.add("hell");
list.add("child");
System.out.println("当前容量:" + list.size());
/* 将ArrayList的大小和实际所含元素的大小设置一致 */
list.trimToSize();
/* 遍历 */
for (String string : list) {
System.out.println(string);
}
/* 在指定位置插入元素 */
list.add(2, "zhu");
for (String string : list) {
System.out.println(string);
}
System.out.println("--------------");
/* 清空list */
list.clear();
/* 遍历 */
for (String string : list) {
System.out.println(string);
}
System.out.println("--------------");
}
}
运行结果
初始化大小:0
当前容量:4
zzz
egg
hell
child
zzz
egg
zhu
hell
child
--------------
--------------
####查找替换
fill——使用指定元素替换指定列表中的所有元素。
frequency——返回指定 collection 中等于指定对象的元素数。
indexOfSubList—— 返回指定源列表中第一次出现指定目标列表的起始位置，如果没有出现这样的列表，则返回 -1。
lastIndexOfSubList——返回指定源列表中最后一次出现指定目标列表的起始位置，如果没有出现这样的列表，则返回-1。
max—— 根据元素的自然顺序，返回给定 collection 的最大元素。
min——根据元素的自然顺序 返回给定 collection 的最小元素。
replaceAll——使用另一个值替换列表中出现的所有某一指定值。
public static void main(String[] args) {
java.util.List<Integer> list = new ArrayList<Integer>();
list.add(1);
list.add(2);
list.add(3);
for (Integer integer : list) {
System.out.println(integer);
}
/*找出最大值*/
int max = Collections.max(list);
System.out.println("最大的为:"+max);
/*替换指定元素*/
Collections.replaceAll(list, 3, 6);
System.out.println("替换后:");
for (Integer integer : list) {
System.out.println(integer);
}
/*用指定元素替换指定list中的元素*/
Collections.fill(list, 6);
System.out.println("替换后:");
for (Integer integer : list) {
System.out.println(integer);
}
/*找出某个list里某个元素的个数*/
int count = Collections.frequency(list, 6);
System.out.println("里面有6的个数:"+count);
}
运行结果
1
2
3
最大的为:3
替换后:
1
2
6
替换后:
6
6
6
里面有6的个数:3
####排序
reverse——对List中的元素进行转置
shuffle——对List中的元素随即排列
sort——对List中的元素排序
swap——交换List中某两个指定下标位元素在集合中的位置。
rotate——循环移动
public static void main(String[] args) {
List<Integer> list = new ArrayList<Integer>();
list.add(5);
list.add(2);
list.add(1);
list.add(9);
list.add(0);
System.out.println("排序前:");
for (Integer integer : list) {
System.out.print(integer+" ");
}
System.out.println();
/*排序*/
Collections.sort(list);
System.out.println("排序后");
for (Integer integer : list) {
System.out.print(integer+" ");
}
}
运行结果
输出：
排序前:
5 2 1 9 0
排序后
0 1 2 5 9
###HashSet的基本功能
###Hashmap的基本功能
####基本操作和遍历
第一种方式：KeySet()
将Map中所有的键存入到set集合中。因为set具备迭代器。所有可以迭代方式取出所有的键，再根据get方法。获取每一个键对应的值。 keySet():迭代后只能通过get()取key 。取到的结果会乱序，是因为取得数据行主键的时候，使用了HashMap.keySet()方法，而这个方法返回的Set结果，里面的数据是乱序排放的。
Map map = new HashMap();
map.put("key1","lisi1");
map.put("key2","lisi2");
map.put("key3","lisi3");
map.put("key4","lisi4");
//先获取map集合的所有键的set集合，keyset（）
=======================================================================
Iterator it = map.keySet().iterator();
//获取迭代器
while(it.hasNext()){
Object key = it.next();
System.out.println(map.get(key));
}
lisi1
lisi2
lisi3
lisi4
第二种：entrySet（）（常用）
返回此映射中包含的映射关系的 Set 视图。（一个关系就是一个键-值对），就是把(key-value)作为一个整体一对一对地存放到Set集合当中的。Map.Entry表示映射关系。entrySet()：迭代后可以e.getKey()，e.getValue()两种方法来取key和value。返回的是Entry接口。
Map map = new HashMap();
map.put("key1","lisi1");
map.put("key2","lisi2");
map.put("key3","lisi3");
map.put("key4","lisi4");
=====================================================================
//将map集合中的映射关系取出，存入到set集合
Iterator it = map.entrySet().iterator();
while(it.hasNext()){
Entry e =(Entry) it.next();
System.out.println("键"+e.getKey () + "的值为" + e.getValue());
}
持续更新中…
###面试中的集合类（错题本）
####Collection和Collections的区别
java.util.Collection 是一个集合接口。它提供了对集合对象进行基本操作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为各种具体的集合提供了最大化的统一操作方式。
java.util.Collections 是一个包装类。它包含有各种有关集合操作的静态多态方法。此类不能实例化，就像一个工具类，服务于Java的Collection框架。
####HashSet子类依靠什么方法区分重复元素
HashSet内部使用Map保存数据，即将HashSet的数据作为Map的key值保存，这也是HashSet中元素不能重复的原因。而Map中保存key值前，会去判断当前Map中是否含有该key对象，内部是先通过key的hashCode，确定有相同的hashCode之后，再通过equals方法判断是否相同。
####Arraylist的初始容量
ArrayList的构造函数总共有三个：
（1）ArrayList()构造一个初始容量为 10 的空列表。
（2）ArrayList(Collection<? extends E> c)构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。
（3）ArrayList(int initialCapacity)构造一个具有指定初始容量的空列表。
京公网安备 11010502036488号