java集合是java基础的重点知识库，但是好多人都知识了解了解。并没有系统的进行深入研究，下面我们就来看看集合家族的全部成员。掌握下面等东西
Collection和Map
(1)掌握Collection和Map的继承体系。
(2)掌握ArrayList、LinkedList、Vector、Stack、PriorityQueue、HashSet、 LinkedHashSet、TreeSet、HashMap、LinkedHashMap、TreeMap、WeakHashMap、EnumMap、 TreeMap、****HashTable的特点和实现原理。
(3)掌握CopyOnWriteArrayList、CopyOnWriteArraySet、ConcurrentHashMap的实现原理和适用场景。
知识点1，Collection 
关系拓扑图如图所示
Collection是最基本的集合接口，一个Collection代表一组Object，即Collection的元素（Elements）。一些 Collection允许相同的元素而另一些不行。一些能排序而另一些不行。Java SDK不提供直接继承自Collection的类，Java SDK提供的类都是继承自Collection的“子接口”如List和Set。
所有实现Collection接口的类都必须提供两个标准的构造函数：无参数的构造函数用于创建一个空的Collection，有一个 Collection参数的构造函数用于创建一个新的Collection，这个新的Collection与传入的Collection有相同的元素。后 一个构造函数允许用户复制一个Collection。
如何遍历Collection中的每一个元素？不论Collection的实际类型如何，它都支持一个iterator()的方法，该方法返回一个迭代子，使用该迭代子即可逐一访问Collection中每一个元素。典型的用法如下：
Iterator it = collection.iterator(); // 获得一个迭代子
while(it.hasNext()) {
Object obj = it.next(); // 得到下一个元素
} 由Collection接口派生的两个接口是List和Set。
(1)List
List是有序的Collection，使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素，这类似于Java的数组。
和下面要提到的Set不同，List允许有相同的元素。
除了具有Collection接口必备的iterator()方法外，List还提供一个listIterator()方法，返回一个 ListIterator接口，和标准的Iterator接口相比，ListIterator多了一些add()之类的方法，允许添加，删除，设定元素， 还能向前或向后遍历。
List常用方法
package com.itlwc;
import java.util.ArrayList;
import java.util.List;
public class Test {
public static void main(String[] args) {
List list = new ArrayList();
// 向列表的尾部追加指定的元素
list.add("double");
// 在列表的指定位置插入指定元素
list.add(1, "double1");
// 追加指定 collection 中的所有元素到此列表的结尾
list.addAll(new ArrayList());
// 从列表中移除所有元素
list.clear();
// 如果列表包含指定的元素,则返回true
list.contains("double");
// 如果列表包含指定 collection 的所有元素,则返回 true
list.containsAll(new ArrayList());
// 比较指定的对象与列表是否相等
list.equals(new ArrayList());
// 返回列表中指定位置的元素
list.get(0);
// 返回列表的哈希码值
list.hashCode();
// 返回列表中首次出现指定元素的索引,如果列表不包含此元素,则返回 -1
list.indexOf("double");
// 返回列表中最后出现指定元素的索引,如果列表不包含此元素,则返回 -1
list.lastIndexOf("double");
// 如果列表不包含元素,则返回 true
list.isEmpty();
// 移除列表中指定位置的元素
list.remove(0);
// 移除列表中出现的首个指定元素
list.remove("double");
// 从列表中移除指定 collection 中包含的所有元素
list.removeAll(new ArrayList());
// 用指定元素替换列表中指定位置的元素
list.set(0, "double");
// 返回列表中的元素数
list.size();
// 返回列表中指定的fromIndex(包括)和toIndex(不包括)之间的部分视图
list.subList(1, 2);
// 返回以正确顺序包含列表中的所有元素的数组
list.toArray();
// 返回以正确顺序包含列表中所有元素的数组
list.toArray(new String[] { "a", "b" });
}
} 实现List接口的常用类有LinkedList，ArrayList，Vector和Stack。
LinkedList类
ublic class Test {
public static void main(String[] args) {
List link = new LinkedList();
link.add(123);
link.add("double");
link.add(8.8);
link.add("double");
link.add(520);
printList(link);
printReversedList(link);
}
private static void printList(List link) {
System.out.println("正序链表中的元素");
// 的到链表的迭代器,位置指向链头
ListIterator li = link.listIterator();
// 判断迭代器中是否有下一个元素
while (li.hasNext()) {
// 返回下个元素
System.out.print(li.next() + " ");
}
System.out.println();
}
private static void printReversedList(List link) {
System.out.println("逆向链表中的元素");
// 的到链表的迭代器,位置指向link.size()结尾
ListIterator li = link.listIterator(link.size());
// 判断迭代器中是否有前一个元素
while (li.hasPrevious()) {
// 返回前一个元素
System.out.print(li.previous() + " ");
}
System.out.println();
}
}
/*
打印结果:
正序链表中的元素
123 double 8.8 double 520
逆向链表中的元素
520 double 8.8 double 123
*/ LinkedList实现了List接口，允许null元素。此外LinkedList提供额外的get，remove，insert方法在 LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。
注意LinkedList没有同步方法。如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List：
List list = Collections.synchronizedList(new LinkedList(...));自定义LinkedList结构
class Node {
Node previous;// 前驱
String data;// 数据
Node next;// 后驱
public Node(String data) {
this.data = data;
}
}
public class Test {
public static void main(String[] args) {
Node node1 = new Node("node1");
Node node2 = new Node("node2");
Node node3 = new Node("node3");
node1.next = node2;
node2.previous = node1;
node2.next = node3;
node3.previous = node2;
node3.next = node1;
node1.previous = node3;
// 增加node4
Node node4 = new Node("node4");
node1.next = node4;
node4.previous = node1;
node4.next = node2;
node2.previous = node4;
// 删除node4
node1.next = node2;
node2.previous = node1;
node4.previous = null;
node4.next = null;
}
} 依赖倒置原理依赖应该尽量在抽象层进行,避免在具体层进行,
在实际开发中尽量使用接口类型的引用,避免采用具体类型的引用
public class Test {
//如果我们需要传入参数是ArrayList就需要改动代码
public void printLinkedList(LinkedList ll){
System.out.println(ll);
}
//如果我们传入参数是List的子类,我们不需要改动代码,灵活性大
public void printList(List l){
System.out.println(l);
}
将数组转换为列表
public class Test {
public static void main(String[] args) {
String[] str = { "1", "2", "3" };
//使用Java类库中java.util.Arrays类的静态方法asList()
List l = Arrays.asList(str);
System.out.println(str);
}
} ArrayList类
ArrayList实现了可变大小的数组。它允许所有元素，包括null。ArrayList没有同步。
size，isEmpty，get，set方法运行时间为常数。但是add方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。
每个ArrayList实例都有一个容量（Capacity），即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加，但是增长算法 并没有定义。当需要插入大量元素时，在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。
和LinkedList一样，ArrayList也是非同步的（unsynchronized）。
遍历arraylist
public class Test {
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("double");
list.add("double");
// 方法一
Iterator<String> ite1 = list.iterator();
while (ite1.hasNext()) {
String str = ite1.next();
System.out.println(str);
}
System.out.println("---------------------");
// 方法二(方法一的变形)
for (Iterator<String> ite2 = list.iterator(); ite2.hasNext();) {
String str = ite2.next();
System.out.println(str);
}
System.out.println("---------------------");
// 方法三
for(String s : list){
System.out.println(s);
}
}
}
/*
打印结果:
double
double
---------------------
double
double
---------------------
double
double
*/ArrayList VS LinkedList
ArrayList底层采用数组实现,LinkedList底层采用双链表实现
如果为列表增加对象
ArrayList是ArrayList底层数组维护的,LinkedList是LinkedList底层Entry对象维护的
LinkedList底层Entry结构
Entry{
Entry previous;
Object element;
Entry next;
}
其中element就是我们添加的元素,最后将生成的Entry对象加入到链表中
插入和删除操作时,采用LinkedList好,搜索时,采用ArrayList好 List
public class Test {
public static void main(String[] args) {
Map<Integer, String> map1 = new HashMap<Integer, String>();
map1.put(new Integer(1), "beijing");
map1.put(new Integer(2), "shanghai");
Map<Integer, String> map2 = new HashMap<Integer, String>();
map2.put(new Integer(3), "tom");
map2.put(new Integer(4), "cat");
List<Map<Integer, String>> list = new ArrayList<Map<Integer, String>>();
list.add(map1);
list.add(map2);
// 方法一
Iterator<Map<Integer, String>> ite1 = list.iterator();
while (ite1.hasNext()) {
Map<Integer, String> m = ite1.next();
System.out.println(m);
}
System.out.println("-----------------------------");
// 方法二(方法一的变形)
for (Iterator<Map<Integer, String>> ite2 = list.iterator(); ite2.hasNext();) {
Map<Integer, String> m = ite2.next();
System.out.println(m);
}
System.out.println("-----------------------------");
// 方法三:
for (Map<Integer, String> m : list) {
System.out.println(m);
}
}
} Vector类
public class Test {
public static void main(String[] args) {
Vector v = new Vector();
v.add("123");
v.add("tw");
v.add("你好");
// Vector转换为枚举
Enumeration e = v.elements();
while (e.hasMoreElements()) {
System.out.println(e.nextElement());
}
} Vector非常类似ArrayList，但是Vector是同步的。由Vector创建的Iterator，虽然和 ArrayList创建的Iterator是同一接口，但是，因为Vector是同步的，当一个Iterator被创建而且正在被使用，另一个线程改变了 Vector的状态（例如，添加或删除了一些元素），这时调用Iterator的方法时将抛出 ConcurrentModificationException，因此必须捕获该异常。
Stack 类
public class Test {
public static void main(String[] args) {
Stack stack = new Stack();
// 向栈里面压一个整数
stack.push(new Integer(123));
stack.push("lwc");
stack.push(new Double(88.88));
// 遍历
Enumeration items = stack.elements();
while (items.hasMoreElements()) {
System.out.print(items.nextElement() + " ");
}
System.out.println();
// 出栈
while (stack.size() != 0) {
System.out.print(stack.pop() + " ");
}
} Stack继承自Vector，实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop 方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。
(2):Set接口
Set是一种不包含重复的元素的Collection，即任意的两个元素e1和e2都有e1.equals(e2)=false，Set最多有一个null元素。实现类 HashSet,LinkedHashSet 子接口 SortSet 实现类 TreeSet
不包含重复元素,最多包含一个null,元素没有顺序
很明显，Set的构造函数有一个约束条件，传入的Collection参数不能包含重复的元素。
请注意：必须小心操作可变对象（Mutable Object）。如果一个Set中的可变元素改变了自身状态导致Object.equals(Object)=true将导致一些问题。
HashSet
HashSet不是Ordered也不是Sorted,存储对象引用时是按照哈希策略来实现的,
HashSet中是否存在一个对象是通过equals()和hashCode()协同判断
不保证顺序
构造方法
public HashSet()
public HashSet(int initialCapacity)
public HashSet(Collection c) HashSet底层是使用HashMap实现的
HashSet的add()方法详解:
判断已经存储在集合中的对象hashCode值是否与增加对象的hashCode值一致
如果不一致,直接加进去
如果一致,再进行equals()比较
如果equals()返回true,对象已经存在不增加进去
如果equals()返回false,把对象增加进去
LinkedHashSet
LinkedHashSet是Ordered,采用双链表实现的
有固定顺序,也就是插入顺序
LinkedHashSet底层是使用LinkedHashMap实现的
构造方法
public LinkedHashSet()
public LinkedHashSet(int initialCapacity)
public LinkedHashSet(Collection c) ``
**SortedSet接口**
保证迭代器按照元素递增顺序遍历的集合,可以按照元素的自然顺序进行排序
常用方法
Object first()
返回此有序集合中当前第一个(最小的)元素
Object last()
返回此有序集合中最后一个(最大的)元素
SortedSet headSet(Object toElement)
返回此有序集合的部分视图,其元素严格小于toElement
SortedSet tailSet(Object fromElement)
返回此有序集合的部分视图,其元素大于或等于fromElement
SortedSet subSet(Object fromElement,Object toElement)
返回此有序集合的部分视图,元素范围从fromElement(包括)到toElement(不包括)
Comparator comparator()
返回与此有序集合关联的比较器,如果使用元素的自然顺序,则返回 null
**TreeSet**TreeSet是SortedSet接口的实现,元素不论以什么元素插入,在遍历的时候,都会以天然顺序遍历
TreeSet底层是使用TreeMap实现的
构造方法
public TreeSet()
public TreeSet(SortedSet s)
public TreeSet(int initialCapacity)
public TreeSet(Comparator
因为TreeSet是带排序的,所以想要为TreeSet增加自定义类型,必须指定排序规则
**Map接口**
请注意，Map没有继承Collection接口，Map提供key到value的映射。一个Map中不能包含相同的key，每个key只能映射一个 value。Map接口提供3种集合的视图，Map的内容可以被当作一组key集合，一组value集合，或者一组key-value映射。
**Hashtable类**
Hashtable继承Map接口，实现一个key-value映射的哈希表。任何非空（non-null）的对象都可作为key或者value。
添加数据使用put(key, value)，取出数据使用get(key)，这两个基本操作的时间开销为常数。
Hashtable通过initial capacity和load factor两个参数调整性能。通常缺省的load factor 0.75较好地实现了时间和空间的均衡。增大load factor可以节省空间但相应的查找时间将增大，这会影响像get和put这样的操作。
使用Hashtable的简单示例如下，将1，2，3放到Hashtable中，他们的key分别是”one”，”two”，”three”：
Hashtable numbers = new Hashtable();
numbers.put(“one”, new Integer(1));
numbers.put(“two”, new Integer(2));
numbers.put(“three”, new Integer(3));
“`
要取出一个数，比如2，用相应的key：
Integer n = (Integer)numbers.get(“two”);
System.out.println(“two = ” + n);
由于作为key的对象将通过计算其散列函数来确定与之对应的value的位置，因此任何作为key的对象都必须实现hashCode和equals方 法。hashCode和equals方法继承自根类Object，如果你用自定义的类当作key的话，要相当小心，按照散列函数的定义，如果两个对象相 同，即obj1.equals(obj2)=true，则它们的hashCode必须相同，但如果两个对象不同，则它们的hashCode不一定不同，如 果两个不同对象的hashCode相同，这种现象称为冲突，冲突会导致操作哈希表的时间开销增大，所以尽量定义好的hashCode()方法，能加快哈希 表的操作。
如果相同的对象有不同的hashCode，对哈希表的操作会出现意想不到的结果（期待的get方法返回null），要避免这种问题，只需要牢记一条：要同时复写equals方法和hashCode方法，而不要只写其中一个。
Hashtable是同步的。
HashMap类
HashMap和Hashtable类似，不同之处在于HashMap是非同步的，并且允许null，即null value和null key。，但是将HashMap视为Collection时（values()方法可返回Collection），其迭代子操作时间开销和HashMap 的容量成比例。因此，如果迭代操作的性能相当重要的话，不要将HashMap的初始化容量设得过高，或者load factor过低。
WeakHashMap类
WeakHashMap是一种改进的HashMap，它对key实行“弱引用”，如果一个key不再被外部所引用，那么该key可以被GC回收。
知识点2，PriorityQueue
Java中PriorityQueue通过二叉小顶堆实现，可以用一棵完全二叉树表示。本文从Queue接口函数出发，结合生动的图解，深入浅出地分析PriorityQueue每个操作的具体过程和时间复杂度，将让读者建立对PriorityQueue建立清晰而深入的认识。
PriorityQueue，即优先队列。优先队列的作用是能保证每次取出的元素都是队列中权值最小的（Java的优先队列每次取最小元素，C++的优先队列每次取最大元素）。这里牵涉到了大小关系，元素大小的评判可以通过元素本身的自然顺序（natural ordering），也可以通过构造时传入的比较器（Comparator，类似于C++的仿函数）。
Java中PriorityQueue实现了Queue接口，不允许放入null元素；其通过堆实现，具体说是通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值），也就意味着可以通过数组来作为PriorityQueue的底层实现。 
上图中我们给每个元素按照层序遍历的方式进行了编号，如果你足够细心，会发现父节点和子节点的编号是有联系的，更确切的说父子节点的编号之间有如下关系：
leftNo = parentNo*2+1
rightNo = parentNo*2+2
parentNo = (nodeNo-1)/2
通过上述三个公式，可以轻易计算出某个节点的父节点以及子节点的下标。这也就是为什么可以直接用数组来存储堆的原因。
PriorityQueue的peek()和element操作是常数时间，add(), offer(), 无参数的remove()以及poll()方法的时间复杂度都是log(N)。
知识点3HashSet
对于HashSet而言，它是基于HashMap来实现的，底层采用HashMap来保存元素。所以如果对HashMap比较熟悉，那么HashSet是so easy!!
一、定义
*public class HashSet extends AbstractSet
implements Set, Cloneable, java.io.Serializable*
HashSet继承AbstractSet类，实现Set、Cloneable、Serializable接口。其中AbstractSet提供 Set 接口的骨干实现，从而最大限度地减少了实现此接口所需的工作。Set接口是一种不包括重复元素的Collection，它维持它自己的内部排序，所以随机访问没有任何意义。
基本属性
//基于HashMap实现，底层使用HashMap保存所有元素
private transient HashMap