二、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、红黑树——精髓》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

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

数字化崇拜

数字化崇拜

[加] 文森特·莫斯可 / 黄典林 / 北京大学出版社 / 2010-1 / 26.00元

与此前的许多技术发展一样,以互联网为标志的数字化时代同样为人们提供了社会根本性变革的许诺:通过电脑,我们可以超越时空和政治。在本书中,文森特·莫斯可透过技术发展和经济泡沫的迷雾,试图探明围绕数字化新技术出现了哪些迷思,以及为何人们对这些迷思坚信不疑。他认为互联网时代投资者如此狂热的动因并不是他们对经济规则的无知,而是对赛博空间开启了一个新世界这样的迷思的坚定信念。 莫斯可指出,迷思并不是一些......一起来看看 《数字化崇拜》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

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

正则表达式在线测试

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具