注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

和申的个人主页

专注于java开发,1985wanggang

 
 
 

日志

 
 

TreeMap和TreeSet  

2010-02-23 23:55:42|  分类: Java 笔试面试 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
笑话

哈希表HashMap,红黑树TreeMap,链表LinkedList,动态数组ArrayList等数据结构的迭代。

既然TreeMap是有序的,自然要求元素是可以比较大小的,如果构造函数指定Comparator的话,就使用这个Comparator比较大小,如果没有指定Comparator的话,就使用自然排序(元素要实现Comparable接口).如果这两个都不可用,就等着出错吧.
有关Java的排序:http://blog.csdn.net/treeroot/archive/2004/10/19/142636.aspx

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

================

 HashMap 的查找、添加、删除的效率都要高于TreeMapTreeMap存在是唯一理由就是它内部是一个树形结构存储结构,而Java中的其他的容器都是线性的(arraylist,linkedlist)或者说是线性的扩展(hashmap)

以下测试数据来源于Think in Java

          Type            Size    Put    Get     Iterator

         TreeMap             10    26.6     20.3    43.7

                                       100   34.1     27.2    45.8

                                      1000  27.8     29.3    8.8

        HashMap               10    21.9    18.8    60.9

100    21.9    18.6    63.3

1000   11.5    18.8    12.3

==================
大家都应该知道树的效率是和高度height高度紧密的联系着 所谓的效率是指insert,delete,search AVL tree的height < 1.75 log2(n) 红黑树的  height <=  2 log2(n+1) n是树中所有元素的个数。 很明显AVL树的高度height比红黑树小,那为什么java中的TreeMap不用AVL树来实现呢?
红黑树修改,插入比avl快点 avl查询比较快

 

  评论这张
 
阅读(2727)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2016