浅谈TreeMap以及在java中的使用
2018-06-18 03:52:11来源：未知 阅读 ()
treemap结构是红黑树
1.先介绍一下平衡二叉树
其特点是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。也就是说该二叉树的任何一个子节点，其左右子树的高度都相近。
2.红黑树（Red Black Tree） 是一种自平衡二叉查找树
（1） 检索效率O(log n)
（2）红黑树的五点规定：
a每个节点都只能是红色或者黑色
b根节点是黑色
c每个叶节点（NIL节点，空节点）是黑色的。
d从每个叶子到根的所有路径上不能有两个连续的红色节点。
e从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
3.java中的定义：public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable
treeMap继承AbstractMap，实现NavigableMap、Cloneable、Serializable三个接口。而AbstractMap表明TreeMap为一个Map即支持key-value的集合。
4.java中的应用：
（1）TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) ，TreeMap是非同步的
（2）TreeMap中默认的排序为升序，如果要改变其排序可以自己写一个Comparator
eg:
1 import java.util.Comparator; 2 import java.util.Iterator; 3 import java.util.Set; 4 import java.util.TreeMap; 5 6 7 public class Compare { 8 public static void main(String[] args) { 9 TreeMap<String,Integer> map = new TreeMap<String,Integer>(new xbComparator()); 10 map.put("key_1", 1); 11 map.put("key_2", 2); 12 map.put("key_3", 3); 13 Set<String> keys = map.keySet(); 14 Iterator<String> iter = keys.iterator(); 15 while(iter.hasNext()) 16 { 17 String key = iter.next(); 18 System.out.println(" "+key+":"+map.get(key)); 19 } 20 } 21 } 22 class xbComparator implements Comparator 23 { 24 public int compare(Object o1,Object o2) 25 { 26 String i1=(String)o1; 27 String i2=(String)o2; 28 return -i1.compareTo(i2); 29 } 30 }
（3）Tree的遍历
a遍历键值对
Integer value = null;
Iterator iter = map.entrySet().iterator();
while(iter.hasNext()) {
Map.Entry entry = (Map.Entry)iter.next();
// 获取key
key = (String)entry.getKey();
// 获取value
value = (Integer)entry.getValue();
}
b遍历键
String key = null; Integer value= null; Iterator iter = map.keySet().iterator(); while (iter.hasNext()) { // 获取key key = (String)iter.next(); // 根据key，获取value value= (Integer)map.get(key); }
c遍历value
Integer value = null; Collection c = map.values(); Iterator iter= c.iterator(); while (iter.hasNext()) { value = (Integer)iter.next(); }
注：使用entrySet遍历方式要比keySet遍历方式快
entrySet遍历方式获取Value对象是直接从Entry对象中直接获得，时间复杂度T(n)=o(1);
keySet遍历获取Value对象则要从Map中重新获取，时间复杂度T(n)=o(n);keySet遍历Map方式比entrySet遍历Map方式多了一次循环，多遍历了一次table，当Map的size越大时，遍历的效率差别就越大。
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
- java环境教程：Tomcat下载，安装，设置为Windows服务，启动 2020-06-09
- Java跨平台原理（字节码文件、虚拟机） 以及Java安全性 2020-06-07
- Java生鲜电商平台-生鲜系统代码审查以及优化方案(小程序/APP 2020-06-01
- Java动态代理与静态代理以及它能为我们做什么 2020-05-31
- ElasticSearch7.4.2安装、使用以及与SpringBoot的整合 2020-05-27
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
