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

栏目: Java · 发布时间: 5年前

内容简介:4、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;
}
复制代码

}


以上所述就是小编给大家介绍的《二、JAVA知识点之HashMap、TreeMap、红黑树——精髓》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

HTML5与CSS3基础教程(第8版)

HTML5与CSS3基础教程(第8版)

[美] Elizabeth Castro、[美] Bruce Hyslop / 望以文 / 人民邮电出版社 / 2014-5 / 69.00元

本书是风靡全球的HTML和CSS入门教程的最新版,至第6版累积销量已超过100万册,被翻译为十多种语言,长期雄踞亚马逊书店计算机图书排行榜榜首。 第8版秉承作者直观透彻、循序渐进、基础知识与案例实践紧密结合的讲授特色,采用独特的双栏图文并排方式,手把手指导读者从零开始轻松入门。相较第7版,全书2/3以上的内容进行了更新,全面反映了HTML5和CSS3的最新特色,细致阐述了响应式Web设计与移......一起来看看 《HTML5与CSS3基础教程(第8版)》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试