二、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、从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点;
	
    红黑树左旋、右旋:
	右旋——自己变为左孩子的右孩子;
	左旋——自己变为右孩子的左孩子。
	例:
复制代码
二、JAVA知识点之HashMap、TreeMap、红黑树——精髓
左旋:
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;
}
复制代码

}

原文 

https://juejin.im/post/5bf7c6a16fb9a04a0604839c

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 二、JAVA知识点之HashMap、TreeMap、红黑树——精髓

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址