文档章节

Java学习笔记(35)——Java集合07之TreeMap

IT特种兵
 IT特种兵
发布于 2015/05/07 16:00
字数 1225
阅读 15
收藏 0

一、概述

TreeMap 简介

TreeMap 是一个有序的key-value集合,它是通过红黑树实现的。
TreeMap 继承于AbstractMap,所以它是一个Map,即一个key-value集合。
TreeMap 实现了NavigableMap接口,意味着它支持一系列的导航方法。比如返回有序的key集合。
TreeMap 实现了Cloneable接口,意味着它能被克隆
TreeMap 实现了java.io.Serializable接口,意味着它支持序列化

TreeMap基于红黑树(Red-Black tree)实现。该映射根据其键的自然顺序进行排序,或者根据创建映射时提供的 Comparator 进行排序,具体取决于使用的构造方法。
TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) 。
另外,TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fastl的。

TreeMap的构造函数

// 默认构造函数。使用该构造函数,TreeMap中的元素按照自然排序进行排列。
TreeMap()

// 创建的TreeMap包含Map
TreeMap(Map<? extends K, ? extends V> copyFrom)

// 指定Tree的比较器
TreeMap(Comparator<? super K> comparator)

// 创建的TreeSet包含copyFrom
TreeMap(SortedMap<K, ? extends V> copyFrom)

TreeMap的API

Entry<K, V>                ceilingEntry(K key)
K                          ceilingKey(K key)
void                       clear()
Object                     clone()
Comparator<? super K>      comparator()
boolean                    containsKey(Object key)
NavigableSet<K>            descendingKeySet()
NavigableMap<K, V>         descendingMap()
Set<Entry<K, V>>           entrySet()
Entry<K, V>                firstEntry()
K                          firstKey()
Entry<K, V>                floorEntry(K key)
K                          floorKey(K key)
V                          get(Object key)
NavigableMap<K, V>         headMap(K to, boolean inclusive)
SortedMap<K, V>            headMap(K toExclusive)
Entry<K, V>                higherEntry(K key)
K                          higherKey(K key)
boolean                    isEmpty()
Set<K>                     keySet()
Entry<K, V>                lastEntry()
K                          lastKey()
Entry<K, V>                lowerEntry(K key)
K                          lowerKey(K key)
NavigableSet<K>            navigableKeySet()
Entry<K, V>                pollFirstEntry()
Entry<K, V>                pollLastEntry()
V                          put(K key, V value)
V                          remove(Object key)
int                        size()
SortedMap<K, V>            subMap(K fromInclusive, K toExclusive)
NavigableMap<K, V>         subMap(K from, boolean fromInclusive, K to, boolean toInclusive)
NavigableMap<K, V>         tailMap(K from, boolean inclusive)
SortedMap<K, V>            tailMap(K fromInclusive)

二、TreeMap数据结构

TreeMap的继承关系

java.lang.Object
   ↳     java.util.AbstractMap<K, V>
         ↳     java.util.TreeMap<K, V>

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable {}

TreeMap与Map关系如下图:

从图中可以看出:
(01) TreeMap实现继承于AbstractMap,并且实现了NavigableMap接口。
(02) TreeMap的本质是R-B Tree(红黑树),它包含几个重要的成员变量: root, size, comparator
     root 是红黑数的根节点。它是Entry类型,Entry是红黑数的节点,它包含了红黑数的6个基本组成成分:key(键)、value(值)、left(左孩子)、right(右孩子)、parent(父节点)、color(颜色)。Entry节点根据key进行排序,Entry节点包含的内容为value。    
     红黑数排序时,根据Entry中的key进行排序;Entry中的key比较大小是根据比较器comparator来进行判断的。
     size是红黑数中节点的个数。

三、TreeMap遍历方式

3.1 遍历TreeMap的键值对

第一步:根据entrySet()获取TreeMap的“键值对”的Set集合。
第二步:通过Iterator迭代器遍历“第一步”得到的集合。

// 假设map是TreeMap对象
// map中的key是String类型,value是Integer类型
Integer integ = null;
Iterator iter = map.entrySet().iterator();
while(iter.hasNext()) {
    Map.Entry entry = (Map.Entry)iter.next();
    // 获取key
    key = (String)entry.getKey();
        // 获取value
    integ = (Integer)entry.getValue();
}

3.2 遍历TreeMap的键

第一步:根据keySet()获取TreeMap的“键”的Set集合。
第二步:通过Iterator迭代器遍历“第一步”得到的集合。

// 假设map是TreeMap对象
// map中的key是String类型,value是Integer类型
String key = null;
Integer integ = null;
Iterator iter = map.keySet().iterator();
while (iter.hasNext()) {
        // 获取key
    key = (String)iter.next();
        // 根据key,获取value
    integ = (Integer)map.get(key);
}

3.3 遍历TreeMap的值

第一步:根据value()获取TreeMap的“值”的集合。
第二步:通过Iterator迭代器遍历“第一步”得到的集合。

// 假设map是TreeMap对象
// map中的key是String类型,value是Integer类型
Integer value = null;
Collection c = map.values();
Iterator iter= c.iterator();
while (iter.hasNext()) {
    value = (Integer)iter.next();
}

TreeMap遍历测试程序如下:

import java.util.Map;
import java.util.Random;
import java.util.Iterator;
import java.util.TreeMap;
import java.util.HashSet;
import java.util.Map.Entry;
import java.util.Collection;

/*
 * @desc 遍历TreeMap的测试程序。
 *   (01) 通过entrySet()去遍历key、value,参考实现函数:
 *        iteratorTreeMapByEntryset()
 *   (02) 通过keySet()去遍历key、value,参考实现函数:
 *        iteratorTreeMapByKeyset()
 *   (03) 通过values()去遍历value,参考实现函数:
 *        iteratorTreeMapJustValues()
 *
 * @author skywang
 */
public class TreeMapIteratorTest {

    public static void main(String[] args) {
        int val = 0;
        String key = null;
        Integer value = null;
        Random r = new Random();
        TreeMap map = new TreeMap();

        for (int i=0; i<12; i++) {
            // 随机获取一个[0,100)之间的数字
            val = r.nextInt(100);
            
            key = String.valueOf(val);
            value = r.nextInt(5);
            // 添加到TreeMap中
            map.put(key, value);
            System.out.println(" key:"+key+" value:"+value);
        }
        // 通过entrySet()遍历TreeMap的key-value
        iteratorTreeMapByEntryset(map) ;
        
        // 通过keySet()遍历TreeMap的key-value
        iteratorTreeMapByKeyset(map) ;
        
        // 单单遍历TreeMap的value
        iteratorTreeMapJustValues(map);        
    }
    
    /*
     * 通过entry set遍历TreeMap
     * 效率高!
     */
    private static void iteratorTreeMapByEntryset(TreeMap map) {
        if (map == null)
            return ;

        System.out.println("\niterator TreeMap By entryset");
        String key = null;
        Integer integ = null;
        Iterator iter = map.entrySet().iterator();
        while(iter.hasNext()) {
            Map.Entry entry = (Map.Entry)iter.next();
            
            key = (String)entry.getKey();
            integ = (Integer)entry.getValue();
            System.out.println(key+" -- "+integ.intValue());
        }
    }

    /*
     * 通过keyset来遍历TreeMap
     * 效率低!
     */
    private static void iteratorTreeMapByKeyset(TreeMap map) {
        if (map == null)
            return ;

        System.out.println("\niterator TreeMap By keyset");
        String key = null;
        Integer integ = null;
        Iterator iter = map.keySet().iterator();
        while (iter.hasNext()) {
            key = (String)iter.next();
            integ = (Integer)map.get(key);
            System.out.println(key+" -- "+integ.intValue());
        }
    }
    

    /*
     * 遍历TreeMap的values
     */
    private static void iteratorTreeMapJustValues(TreeMap map) {
        if (map == null)
            return ;
        
        Collection c = map.values();
        Iterator iter= c.iterator();
        while (iter.hasNext()) {
            System.out.println(iter.next());
       }
    }
}


© 著作权归作者所有

IT特种兵
粉丝 19
博文 103
码字总数 136362
作品 0
长宁
高级程序员
私信 提问
【Java学习路线】新手该如何一步步的学习 Java

新手该如何一步步的学习 Java? 如果真的想学Java,最好要循序渐进,有章有法的学习它! 今天小慕就不说一些学习方法和技巧了,直接来谈每个阶段要学习的内容。 首先,给大家分享一张以 企业...

Eddie_yang
2018/11/15
2K
0
201709记录(elasticsearch)

1 Easy Go Programming Setup for Windows http://www.wadewegner.com/2014/12/easy-go-programming-setup-for-windows/ 2 本地计算机上的mysql服务启动停止后,某些服务在未由其他服务或程序......

bapleliu
2017/09/01
3
0
一份关于 Java、Kotlin 与 Android 的学习笔记

JavaKotlinAndroidLearn 这是一份关于 Java 、Kotlin 、Android 的学习笔记,既包含对基础知识点的介绍,也包含对一些重要知识点的源码解析,笔记的大纲如下所示: Java 重拾Java(0)-基础知...

叶应是叶
2018/08/08
0
0
JAVA 私塾第八、九章笔记整理

JAVA 私塾第八、九章笔记整理 第八章 异常和断言 一. 异常的分类 java.lang.Throwable类充当所有对象的父类,可以使用异常处理机制将这些对象超出并捕获。有Error和Exception两个基本子类。...

luodis
2011/02/15
157
1
2018年Java编程学习面试最全知识点总结

Java是一种可以撰写跨平台应用软件的面向对象的程序设计语言。Java 技术具有卓越的通用性、高效性、平台移植性和安全性,广泛应用于PC、数据中心、游戏控制台、科学超级计算机、移动电话和互...

Java小辰
2018/05/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周五乱弹 ——不知道假装开心,装的像么

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @巴拉迪维 :天黑了 你很忧愁, 你说世界上, 找不到四块五的妞, 行走在凌晨两点的马路上, 你疲倦地拿着半盒黄鹤楼。#今日歌曲推荐# 《四块...

小小编辑
今天
2.3K
18
64.监控平台介绍 安装zabbix 忘记admin密码

19.1 Linux监控平台介绍 19.2 zabbix监控介绍 19.3/19.4/19.6 安装zabbix 19.5 忘记Admin密码如何做 19.1 Linux监控平台介绍: 常见开源监控软件 ~1.cacti、nagios、zabbix、smokeping、ope...

oschina130111
昨天
69
0
当餐饮遇上大数据,嗯真香!

之前去开了一场会,主题是「餐饮领袖新零售峰会」。认真听完了餐饮前辈和新秀们的分享,觉得获益匪浅,把脑子里的核心纪要整理了一下,今天和大家做一个简单的分享,欢迎感兴趣的小伙伴一起交...

数澜科技
昨天
34
0
DNS-over-HTTPS 的下一代是 DNS ON BLOCKCHAIN

本文作者:PETER LAI ,是 Diode 的区块链工程师。在进入软件开发领域之前,他主要是在做工商管理相关工作。Peter Lai 也是一位活跃的开源贡献者。目前,他正在与 Diode 团队一起开发基于区块...

红薯
昨天
127
0
CC攻击带来的危害我们该如何防御?

随着网络的发展带给我们很多的便利,但是同时也带给我们一些网站安全问题,网络攻击就是常见的网站安全问题。其中作为站长最常见的就是CC攻击,CC攻击是网络攻击方式的一种,是一种比较常见的...

云漫网络Ruan
昨天
32
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部