摘要：Java容器是什么？容器中有什么，它是用来干嘛的？内心抱着无数的疑问去了解它无疑是认识记住它的最好的一个方法。
Java容器中有collection和map两大类，其中包含很多的分支。在Java.util中定义两个接口List和Set（还有对列queue），他们两个都继承于collection的接口。而map中又有HashMap和TreeMap。
1、List（表）的使用：List中有一些特性，比如元素的有序性，两个元素的值可以相等，List中有许多方法如add()添加元素、remove()移除元素、获取表的大小size()、get()获取元素；它们都是使用下标说明位置。
package test;
import java.util.ArrayList;
import java.util.List;
public class collectiontdemo {
public static void main(String []args){
List <String> ls=new ArrayList<String> ();
ls.add("apple");
ls.add("bananel");
ls.add("tree");
ls.remove(0);
System.out.println(ls.get(1));
System.out.println(ls.size());
}
}
2、Set的使用方法：保存的是数组
Set<Integer> st = new HashSet<Integer>(); st.add(1);
st.add(2);
st.remove(1);
System.out.println(st.size());
3、Queue(队列)的使用：
package test;
import java.util.LinkedList;
import java.util.Queue;
import javax.management.Query;
public class Main {
public static void main (String []args){
//创建一个新的队列
Queue <String> queue = new LinkedList<String>();
//添加元素
queue.offer("a");
queue.offer("b");
queue.offer("c");
queue.offer("d");
queue.offer("e");
//顺序输出队列
for(String q:queue){
System.out.println(q);
}
System.out.println("===");
//返回第一个元素，并在队列中删除并输出
System.out.println("poll="+queue.poll());
for(String q : queue){
System.out.println(q);
}
//而queue.element()方法和queue.peek()方法都只是返回第一个元素，并不会删除
System.out.println("===");
System.out.println("element="+queue.element()); //返回第一个元素
for(String q : queue){
System.out.println(q);
}
}
}
队列中的方法需要注意一下poll()是返回第一个元素，并在队列中删除输出，而element()和peek()方法都是返回第一个元素，并不会删除。
二、
1、HashMap的使用与特性
Map中是以键值对的形式存在的<key,value>
实现一个HashMap
package test;
import java.util.HashMap;
import java.util.Map;
public class collectiontdemo {
public static void main(String []args){
Map <String,Integer> m=new HashMap<String,Integer>();
m.put("123", 11);
m.put("456", 22);
m.put("789", 33);
System.out.println(m.get("123"));
}
}
通过put()放入元素，get()获取元素。
2、TreeMap的使用
TreeMap是一个有序的<key,value>集合
TreeMap继承于AbstractMap。在TreeMap中比较重要的是红黑树，什么是红黑树？它有什么用？怎么去用红黑树？
接下来我们一一去实现它。
红黑树：它是一颗空的树或则具有以下性质
（1）节点非红即黑
（2）根节点都是黑色
（3）所有NULL节点都是子叶子节点且颜色默认为黑色
（4）所有红节点的子叶子节点都为黑色
（5）从任一节点到其子叶子节点的所有路径上都包含相同数目的黑节点
OK，我们现在先知道有这么一些性质，大概结构先了解，至于有什么功能，为什么要这么做，怎么去用，一步步往下分析。
（懒得去画红黑树了，就从百度上截一张红黑树的图）
红黑树的用处：红黑树对插入时间、查找时间和删除时间最好可能的最坏担保
在了解红黑树之前我们先了解二叉查找树
二叉查找树的一些性质：
（1）左子树上所有的节点的值都比根结点的值小。
（2）右子树上所有的节点的值都比根结点的值大。
（3）左右子树也一定为二叉排序树（也就是二叉查找树）。
二叉查找树与红黑树的关系是什么呢？红黑树相比于二叉查找树的优势是什么呢？
首先我们看二叉查找树，要找到节点值等于10，就与根节点相比，由于树的特性，10比根节点大，故向右子树查找，此时10比节点为11的值小，故向左查找。比较方便。
但是假如有这么一颗树仅仅只有三个节点
我们要往树中插入{1，2，3，4}四个元素，那么树就会变成这个样子：
树的“左腿”就特别长，树左右不平衡，查找起来就比较费时间，这时候红黑树就出现了。由于红黑树的独特性质，就如上面第五点性质（5）：从任意节点到其子叶子节点的所有路径包含的黑节点数目相同，从而保证了树的平衡，最长的路径不会超过最短的路径的两倍，查找起来比较方便。
为什么从上面的五条性质中会得出最长的路径不会超过最短路径的两倍呢？
因为第1条该树上的节点非红即黑，由于第4条该树上不允许存在两个连续的红节点，那么对于从一个节点到其叶子节点的一条最长的路径一定是红黑交错的，那么最短路径一定是纯黑色的节点；而又第5条从任一节点到其叶子节点的所有路径上都包含相同数目的黑节点，这么来说最长路径上的黑节点的数目和最短路径上的黑节点的数目相等！而又第2条根结点为黑、第3条叶子节点是黑，那么可知：最长路径<=2*最短路径
（上图中满足了红黑树的五个性质，最长路径红黑交错，而最短路径为全黑，最长路径小于最短路径的两倍）
接下来就是红黑树的插入操作：
（1）如果树为空，则插入的节点直接插到根节点上即可，由于插入的新的节点都是红色，这时只需要将颜色变成黑色即可。
（2）如果插入的节点位置它刚好是黑色，那么直接插入即可，无需其他操作。
（3）如果插入的节点为红色，那么有三种情况，我们一一讨论：
1：插入的节点位置为父节点的左孩子节点
操作：先将F节点和G 节点的颜色变换，然后进行左左单旋即可，此时F节点来到了之前G节点的位置
2、与第一种情况不同的是叔父节点为红色
操作：将F节点和U节点与G节点变换，然后未结束，G节点往上父亲节点查找，如果没有，就将所有节点红黑变换即可
3、与第一种情况不同的是插入的节点位置为F节点的右孩子节点
操作：首先N、F变换颜色不变，进行左旋操作，然后就变成第一中情况，接下来就按照情况一中的操作执行即可。
问题来了，怎么进行左旋呢？代码如何实现？
public void leftRotate(Entry <K,V> e){
Entry<K,V> right = e.right;
Entry<K,V> rightOfLeft =right.left;
right.parent = e.parent;
if(e.parent==null){
root=right;
}else{
if(e==e.parent.left)
e.parent.left=right;
else
e.parent.right=right;
}
right.left=e;
e.parent=right;
e.right=rightOfLeft;
if(rightOfLeft!=null){
rightOfLeft.parent=e;
}
}
接下来就是删除节点的操作：
删除节点的类型，有三种
1：单个的叶子节点（不是NULL节点）
2：只有右子树（或者左子树）的节点
3：删除的节点有两个子节点
我们分析一下删除掉节点对整棵树的影响，在删除节点时红黑树的1、2、3特性不会被破坏这是肯定的，只需要考虑4、5特性。
对于类型1，肯定不会违背特性4，如果删除的节点是红色，不影响平衡性，如果删除的是黑色，5特性肯定会被破坏，我们先将这种情况记录下来，接下来进行讨论。
对于类型2，有可能删除的是左子树或则右子树，暂时不讨论。如果删除的节点为红色，不影响平衡性，如果删除的是黑色，那么肯定和特性五冲突，当删除的节点的父节点为红色，子节点为红色也会和特性4冲突。
对于类型3，其实最后删除的是它的替代节点，根据替代节点的特性，最终是回到了类型1和2。
总结上面的三种类型可得出一个结论，只有删除节点为黑色时才会破坏原红黑树的平衡，因在删除节点之前红黑树是出于平衡状态的，删除以后很明显的其他兄弟节点分支必然比删除节点的分支多了一个黑色的节点，因此我们只需要改变兄弟节点的颜色即可，我们只讨论左节点，右节点对称。
一：删除节点的兄弟节点红色
将兄弟节点与父亲节节点的颜色互换，进行LL旋转或者RR旋转，如果要删除的节点为父节点的右孩子节点，左孩子节点为红色，则RR旋转，否则LL旋转。
二、兄弟节点为黑色，远侄子为红色。
这个时候，如果我们删除D，这样经过D的子节点（NULL节点）的路径的黑色节点个数就会减1，但是我们看到S的孩子中有红色的节点，如果我们能把这棵红色的节点移动到左侧，并把它改成黑色，那么就满足要求了，这也是为什么P的颜色无关，因为调整过程只在P整棵子树的内部进行。
调整过程为，将P和S的颜色对调，然后对P树进行类似AVL树LL型的操作，最后把SR节点变成黑色，并删除D即可。
三、兄弟节点为黑色，近侄子节点为红色
将S与SR颜色互换，再左旋得到情况4
四、父亲节点P为红色，兄弟节点和兄弟节点的两个孩子节点（只能为null节点）都为黑色
将父亲节点P换成黑色，兄弟节点S换成红色，然后将节点删去即可。
五、父亲节点为黑色，兄弟节点及兄弟节点的子节点（只能为NULL）也为黑色
将S变成红色，然后将节点删去即可平衡，但是P的所有路径的黑色节点会少1。这个时候，我们再以P为起始点，继续根据情况进行平衡操作（这句话的意思就是把P当成D（只是不要再删除P了），再看是那种情况，再进行对应的调整，这样一直向上，直到新的起始点为根节点）。