二、JAVA知识点之HashMap、TreeMap、红黑树——精髓

4、 JAVA 中HashMap和TreeMap什么区别?低层数据结构是什么?

1)、使用层次上的区别：
	HashMap：
		a)、数组+链表存储key-value，1.8加入红黑树(优化链表查找过长的问题)
		b)、允许null作为key和value，key不可以重复，value允许重复
		c)、不能保证插入顺序是有序的
		d)、线程非安全
	TreeMap：
		a)、基于红黑二叉树的NavigableMap的实现
		b)、不允许null，key不可以重复，value允许重复
		c)、元素应当实现Comparable接口或者实现Comparator接口，元素进行自动排序
		d)、线程非安全
		
2)、低层数据结构
	HashMap：
		a)、1.8之前数组+链表，1.8加入红黑树
		
	HashTree：	
	        实现了SotredMap接口，它是有序的集合。而且是一个红黑树结构，每个key-value都
	        作为一个红黑树的节点。如果在调用TreeMap的构造函数时没有指定比较器，则根据
	        key执行自然排序
		
总结：
   红黑树特征：
	1、每个节点要么是红色，要么是黑色；
	2、根节点永远是黑色的；
	3、所有的叶节点都是是黑色的（注意这里说叶子节点其实是上图中的 NIL 节点）；
	4、每个红色节点的两个子节点一定都是黑色；
	5、从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；
	
    红黑树左旋、右旋：
	右旋——自己变为左孩子的右孩子；
	左旋——自己变为右孩子的左孩子。
	例:
复制代码

左旋：
private void rotateLeft(Entry<K,V> p) {
if (p != null) {
    Entry<K,V> r = p.right; //p 是上图中的 x，r 就是 y
    p.right = r.left;       //左旋后，x 的右子树变成了 y 的左子树 β 
    if (r.left != null)         
        r.left.parent = p;  //β 确认父亲为 x
    r.parent = p.parent;    //y 取代 x 的第一步：认 x 的父亲为爹
    if (p.parent == null)   //要是 x 没有父亲，那 y 就是最老的根节点
        root = r;
    else if (p.parent.left == p) //如果 x 有父亲并且是它父亲的左孩子，
                                    x 的父亲现在认 y 为左孩子
        p.parent.left = r;
    else            //如果 x 是父亲的右孩子，父亲就认 y 为右孩子
        p.parent.right = r;
    r.left = p;     //y 逆袭成功，以前的爸爸 x 现在成了它的左孩子
    p.parent = r;
}
复制代码

}