内容简介: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、从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点; 红黑树左旋、右旋: 右旋——自己变为左孩子的右孩子; 左旋——自己变为右孩子的左孩子。 例: 复制代码
左旋: 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、红黑树——精髓》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。