`
wangdei
  • 浏览: 374493 次
社区版块
存档分类
最新评论

TreeMap的使用及注意事项

    博客分类:
  • JAVA
阅读更多

 

 

TreeMap是红黑树算法的实现,实现了SortedMap接口,要注意的是它不在使用哈希表,存储方式是一个特殊的二叉树,有关红黑树:
http://baike.baidu.com/view/133754.htm  http://www.bt285.cn

这篇文章介绍的不错,我之前没有听说过二叉树,我就是看这篇文章加上看一下TreeMap的源代码才搞懂红黑树算法的.

 

这里不打算研究TreeMap的源代码了,因为完全是一个算法的实现,如果对这个算法不了解,肯定看不懂,我也有很多地方不是没有完全看明白,这里就谈谈TreeMap的使用吧.

 

TreeMap的声明:public class TreeMap extends AbstractMap implements SortedMap,Cloneable, java.io.Serializable
所以我们要知道SortedMap接口:
SortedMap表示的是一个排序的Map
public interface SortedMap extends Map
增加了几个方法的定义
SortedMap headMap(Object toKey)
SortedMap tailMap(Object fromKey)
SortedMap subMap(Object fromKey, Object toKey)
Object firstKey()
Object lastKey()

 

既然TreeMap是有序的,自然要求元素是可以比较大小的,如果构造函数指定Comparator的话,就使用这个Comparator比较大小,如果没有指定Comparator的话,就使用自然排序(元素要实现Comparable接口).如果这两个都不可用,就等着出错吧.

现看一下该接口的定义:
public interface Comparable{
   public int compareTo(Object o);
}
该接口定义类的自然顺序,实现该接口的类就可以按这种方式排序.
一般要求:
e1.equals((Object)e2)和e1.compareTo((Object)e2)==0具有相同的值,
这样的话我们就称自然顺序就和equals一致.
这个接口有什么用呢?
如果数据或者List中的元素实现了该接口的话,我们就可以调用Collections.sort或者Arrays方法给他们排序.

如果自然顺序和equals不一致的话,如果出现在Sorted Map和Set里面,
就会出现预想不到的逻辑错误,可能你调用add的时候添加不了,而集合里面确没有这个元素.具体的讨论要接口哈希表的应用.

 

 

public interface Comparator {
  int compare(Object o1, Object o2);
  boolean equals(Object obj);
}

定义了两个方法,其实我们一般都只需要实现compare方法就行了,因为类都是默认从Object继承
所以会使用Object的equals方法.
Comparator一般都作为一个匿名类出现,对于没有实现Comparable的对象的集合,排序的时候
需要指定一个Comparator.

这里举例说明
对于实现了Comparable的类我们就用最简单的Integer
List list=new ArrayList();
list.add(new Integer(3));
list.add(new Integer(53));
list.add(new Integer(34));
Collections.sort(list);

对于没有实现Comparable的,我们就用Object,按照hashCode大小来排序.
List list= new ArrayList();
list.add(new Object());
list.add(new Object());
list.add(new Object());
Collections.sort(list,new Comparator(){ public int compare(Object o1, Object o2){
                    return (o1.hashCode()-o2.hashCode());
})

因为是二叉树,所以一般查找时间复杂度为 o(lg(n)),这个效率当然没有HashMap的效率高.不过TreeMap比HashMap功能强大,如果不需要排序的话当然不会用TreeMap,如果需要排序的话,HashMap无法胜任,当然要用TreeMap了,它可以求子Map.所以这个是适用场合问题,无法比较他们.
 
另外,我们也习惯了,有Map就会跟一个Set,我们都可以猜到TreeSet和通过TreeMap实现的一个SortedSet的实现.不过我觉的TreeSet好像比TreeMap用的场合多一些,求子集是很常用的呀!!

 

3
0
分享到:
评论

相关推荐

    TreeMap in Java_java_treemap_

    四、`TreeMap`的注意事项 1. **线程安全性**:`TreeMap`不是线程安全的,如果多个线程同时访问并修改`TreeMap`,可能会造成数据不一致。如果需要线程安全,可以使用`Collections.synchronizedMap()`或者`...

    关于JAVA内存泄漏问题注意事项

    以下是一些关于Java内存泄漏的注意事项和相关知识点: 1. **理解可达性和无用性**:内存泄漏在Java中发生时,通常是由于某些对象尽管不再使用,但仍然可以通过对象引用图到达,这使得垃圾收集器无法识别它们为无用...

    Java TreeMap排序算法实例

    在本文中,我们将通过实例形式来介绍Java TreeMap排序算法的原理、实现方法与相关注意事项。 1. 对于一些简单的排序,如数字、英文字母等,可以使用Comparator接口来实现自定义的排序规则。例如: ```java TreeMap,...

    Java源码解析TreeMap简介

    5. TreeMap的注意事项 TreeMap不是线程安全的,如果多个线程同时访问TreeMap,需要进行外部同步以避免数据不一致问题。此外,TreeMap的结构修改操作,如添加或删除键值对,也需要externally synchronized。 6. ...

    A Tree Map_map_tree_

    1. "TreeMap in Java.pdf"很可能是关于Java中`TreeMap`的详细教程或文档,可能涵盖了`TreeMap`的实现、操作方法、注意事项和示例代码。 2. "mind reader.txt"标题可能暗示了这个文本文件包含了与`TreeMap`相关的思维...

    SQL空间图工具 v0.12源码20130523

    注意事项: 这个项目包含Microsoft Research一个组件,允许它呈现一个TreeMap基础的数据视图。如果你打算对这个项目出售或衍生作品,你必须删除TreeMap的成分 但是可以个人免费下载研究,不能用于商业

    JAVA TREE

    7. **注意事项** - 尽管`TreeMap`和`TreeSet`提供了高效的性能,但它们的内存开销比其他数据结构(如`HashMap`和`HashSet`)大,因为需要维护额外的树结构。 - 如果不需要排序或者不需要保持元素的插入顺序,使用...

    java-集合-知识点汇总

    Java集合的知识点汇总将会涵盖Java集合的基本概念、类型、实现、操作和注意事项等方面。 Java集合的基本概念 Java集合是Java语言中的一种数据结构,用于存储和操作数据。Java集合可以存储多个元素,每个元素可以是...

    Java中实现参数名ASCII码从小到大排序(字典序).doc

    6. **注意事项**: - 当值是数字或需要编码的特殊字符时,应先将值转换为字符串并进行URL编码(使用`URLEncoder.encode()`)。 - 如果`Map`中的值是集合类型,可能需要进一步处理,比如对集合内的元素进行排序或...

    java 新手小白的入门课

    - **选择结构**:if语句、switch语句的应用及注意事项。 - **循环结构**:for循环、while循环、do-while循环的语法及应用场景。 - **循环控制语句**:break、continue语句的使用方法及技巧。 ### 3. 运算符 #### -...

    张孝祥正在整理Java就业面试题大全

    - **流程控制**:if语句、switch语句、for循环、while循环等的使用方法及注意事项。 - **运算符**:算术运算符、关系运算符、逻辑运算符、位运算符等的优先级和使用场景。 #### 二、类相关的语法 - **面向对象基础...

    LeetCode-DataStructure:关于leetcode旅程的注意事项

    本文将深入探讨在LeetCode上学习数据结构时需要注意的关键知识点,并结合Java语言进行讨论。 首先,理解基本数据结构是基础。在LeetCode上,常见的数据结构包括数组(Array)、链表(LinkedList)、栈(Stack)、...

    地图的简单使用(Map)

    8. **注意事项**: - 键的比较通常是用equals()方法,而不是==,以确保正确地比较对象的内容。 - 使用自定义类作为键时,需重写hashCode()和equals()方法以保持一致性。 总的来说,`Map`是编程中非常重要的数据...

    B站找的课件一共60天

    3. Map的并发性:线程安全的Map实现,如ConcurrentHashMap,以及在多线程环境下的使用注意事项。 4. 泛型与类型安全:理解如何使用泛型来确保Map中键和值的类型安全。 5. 实际应用:在实际项目中如何选择合适的Map...

    AlgorithmsNotes:阅读算法第4版时的注意事项

    在阅读《Algorithms Notes》第四版的过程中,尤其是在深入学习与Java相关的数据结构和算法时,有许多关键点需要注意,这些知识点将对你的编程能力和问题解决技巧产生深远影响。下面,我们将详细探讨这些重要的概念。...

    Java语言程序设计课件第四章 数组、字符串、向量和哈希表

    本章节将涵盖数组、字符串、向量和哈希表的定义、特点、创建、初始化、操作及注意事项,帮助读者全面掌握这些集合数据结构在Java中的应用。正确地使用这些结构对于编写高效、可维护的Java程序至关重要。在实际开发中...

    阿里+Java+开发手册(嵩山版).zip

    手册详细涵盖了Java语言的各种最佳实践、编程规约、设计原则以及注意事项,是Java开发者必备的参考文档。 1. **编程规约** - 命名规约:包括类名、方法名、变量名的命名规则,提倡使用有意义的驼峰命名,避免使用...

    Treemaps-Java-Algorithms.zip_algorithms_treemaps

    注意事项** - 键必须是可比较的,即实现`Comparable`接口,或者在构造Treemap时提供`Comparator`。 - 如果键的`equals()`和`hashCode()`方法不一致,可能会导致意外行为。 综上所述,这个压缩包中的Java代码实例...

    阿里Java编程规范试题答案.zip

    - 类注释:描述类的功能和使用注意事项。 - 方法注释:解释方法的作用、参数、返回值以及可能抛出的异常。 3. **代码格式**: - 缩进:使用4个空格,不使用制表符。 - 行宽:尽量不超过80字符。 - 大括号风格...

Global site tag (gtag.js) - Google Analytics