文档章节

TreeMap浅析(一)

清尘V
 清尘V
发布于 2016/05/09 23:18
字数 596
阅读 34
收藏 3
点赞 2
评论 0

现在看一些基本属性和方法

private final Comparator<? super K> comparator;

  • key值比较器:查找或者存储数据都要通过比较器来完成

   final Entry<K,V> getEntry(Object key) {
        // Offload comparator-based version for sake of performance
        if (comparator != null)
            return getEntryUsingComparator(key);
        if (key == null)
            throw new NullPointerException();
        Comparable<? super K> k = (Comparable<? super K>) key;
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = k.compareTo(p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
        return null;
    }

    final Entry<K,V> getEntryUsingComparator(Object key) {
        K k = (K) key;
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            Entry<K,V> p = root;
            while (p != null) {
                int cmp = cpr.compare(k, p.key);
                if (cmp < 0)
                    p = p.left;
                else if (cmp > 0)
                    p = p.right;
                else
                    return p;
            }
        }
        return null;
    }

  • 以上两个方法根据key获取Entry:从root节点开始循环查找,如果比较值<0,则从左树查找,如果>0则从右树查找

final Entry<K,V> getCeilingEntry(K key) {
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = compare(key, p.key);
            if (cmp < 0) {
                if (p.left != null)
                    p = p.left;
                else
                    return p;
            } else if (cmp > 0) {
                if (p.right != null) {
                    p = p.right;
                } else {
                    Entry<K,V> parent = p.parent;
                    Entry<K,V> ch = p;
                    while (parent != null && ch == parent.right) {
                        ch = parent;
                        parent = parent.parent;
                    }
                    return parent;
                }
            } else
                return p;
        }
        return null;
    }

  • 查找>=key的最小Entry:



  1.     第5行:key<p.key,则从左子树查找,如果左子树存在,则p=p.left,否则直接返回p;简单理解:key<p.key,那么需要的Entry要么就在左子树要么就是p

  2.     第10行:key>p.key,如果右子树存在,则p=p.right,这是因为右子树可能会有左子树节点,而该节点或许最接近key

  3.     第16行:可以看图理解

 final Entry<K,V> getFloorEntry(K key) {
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = compare(key, p.key);
            if (cmp > 0) {
                if (p.right != null)
                    p = p.right;
                else
                    return p;
            } else if (cmp < 0) {
                if (p.left != null) {
                    p = p.left;
                } else {
                    Entry<K,V> parent = p.parent;
                    Entry<K,V> ch = p;
                    while (parent != null && ch == parent.left) {
                        ch = parent;
                        parent = parent.parent;
                    }
                    return parent;
                }
            } else
                return p;

        }
        return null;
    }

  • 查找<=key的最大Entry

final Entry<K,V> getHigherEntry(K key) {
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = compare(key, p.key);
            if (cmp < 0) {
                if (p.left != null)
                    p = p.left;
                else
                    return p;
            } else {
                if (p.right != null) {
                    p = p.right;
                } else {
                    Entry<K,V> parent = p.parent;
                    Entry<K,V> ch = p;
                    while (parent != null && ch == parent.right) {
                        ch = parent;
                        parent = parent.parent;
                    }
                    return parent;
                }
            }
        }
        return null;
    }

  • 查找>key的最小Entry:

 final Entry<K,V> getLowerEntry(K key) {
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = compare(key, p.key);
            if (cmp > 0) {
                if (p.right != null)
                    p = p.right;
                else
                    return p;
            } else {
                if (p.left != null) {
                    p = p.left;
                } else {
                    Entry<K,V> parent = p.parent;
                    Entry<K,V> ch = p;
                    while (parent != null && ch == parent.left) {
                        ch = parent;
                        parent = parent.parent;
                    }
                    return parent;
                }
            }
        }
        return null;
    }

  • 查找<key的最大Entry


© 著作权归作者所有

共有 人打赏支持
清尘V
粉丝 43
博文 107
码字总数 47780
作品 0
青岛
程序员
Java集合框架:总结

最近博主对于Java集合框架这个系列做了一个整理,主要包括: Map系:HashMap, LinkedHashMap, TreeMap, WeakHashMap, EnumMap; List系:ArrayList, LinkedList, Vector, Stack; Set系:HashS...

u013256816 ⋅ 2016/03/18 ⋅ 0

hashMap 1.8.0_91 浅析

我对红黑树不是很了解,所以解说不是很好。还有remove等方法没写,以后再说。linkedHashMap,treeMap,也在说 hashMap由数组、链表、红黑树组成。 why? 数组,查找快!只要知道下标,Array...

锦语冰 ⋅ 2016/11/23 ⋅ 0

openfire xmpp sasl 浅析

SASL全称Simple Authentication and Security Layer,是一种用来扩充C/S模式验证能力的机制。在Postfix可以利用SASL来判断用户是否有权使用转发服务,或是辨认谁在使用你的服务器。 SASL提供...

今幕明 ⋅ 2016/08/26 ⋅ 0

java treeMap信息

最新看啦一篇文章,深有感触,所以又吧treeMap细节重新学习啦一下! treeMap本身就是默认排序的!他是添加内容的时候进行排序的; 出现这个情况的原因是源码中的[每次如果他的key比较为0的时...

sanshao ⋅ 2016/11/14 ⋅ 0

Java Map 按key排序和按Value排序

Java Map 按key排序和按Value排序 一.理论准备 Map是键值对的集合接口,它的实现类主要包括:HashMap,TreeMap,Hashtable以及LinkedHashMap等。 TreeMap:基于红黑树(Red-Black tree)的 Na...

writeademo ⋅ 2016/10/12 ⋅ 0

Java 容器 & 泛型:五、HashMap 和 TreeMap的自白

Writer:BYSocket(泥沙砖瓦浆木匠) 微博:BYSocket 豆瓣:BYSocket Java 容器的文章这次应该是最后一篇了:Java 容器 系列。 今天泥瓦匠聊下 Maps。 一、Map回顾 Map,又称映射表,是将键映...

泥沙砖瓦浆木匠 ⋅ 2015/05/05 ⋅ 0

java集合框架总结(六)

一、Map 简介 Map 用于保存具有映射关系的数据,因此 Map 集合里保存着两组值,一组值用于保存 Map 里的 Key,另外一组用于保存 Map 里的 Value Map 中的 key 和 value 都可以是任何引用类型...

hapier ⋅ 2016/09/09 ⋅ 0

Java集合浅析

Java集合类框架图 Collection List | 类型 | 数据结构 | 查询速度 | 插入速度 | 是否线程安全 || ArrayList | 数组 | 快 | 慢 | 否 || LinkList | 双向链表,| 慢 | 快 | 否 | Vector 数组 ...

wjk_snail ⋅ 2016/01/19 ⋅ 0

终于等到你——ggplot2树状图

感谢关注天善智能,走好数据之路↑↑↑ 欢迎关注天善智能,我们是专注于商业智能BI,人工智能AI,大数据分析与挖掘领域的垂直社区,学习,问答、求职一站式搞定! 本文作者:天善智能社区专家...

天善智能 ⋅ 2017/12/06 ⋅ 0

TreeMap实现原理

在用TreeMap之前我们要对TreeMap有个整体的认识。 1、TreeMap介绍 TreeMap是一个通过红黑树实现有序的key-value集合。 TreeMap继承AbstractMap,也即实现了Map,它是一个Map集合 TreeMap实现...

kukudeku ⋅ 2016/08/24 ⋅ 2

没有更多内容

加载失败,请刷新页面

加载更多

下一页

MySQL主从复制原理、半同步操作步骤及原理

1.1 企业Linux运维场景数据同步方案 1.1.1 文件级别的异机同步方案 1、scp/sftp/nc 命令可以实现远程数据同步。 2、搭建ftp/http/svn/nfs 服务器,然后在客户端上也可以把数据同步到服务器。...

xiaomin0322 ⋅ 19分钟前 ⋅ 0

Oracle10g 数据及文件迁移过程[原]

QL*Plus: Release 10.2.0.1.0 - Production on 星期三 5月 11 10:22:35 2011 Copyright (c) 1982, 2005, Oracle. All rights reserved. 连接到: Oracle Database 10g Enterprise Edition Re......

harrypotter ⋅ 25分钟前 ⋅ 0

nginx安装

1:安装工具包 wget、vim和gcc yum install -y wget yum install -y vim-enhanced yum install -y make cmake gcc gcc-c++ 2:下载nginx安装包 wget http://nginx.org/download/nginx-1......

壹丶贰 ⋅ 28分钟前 ⋅ 0

ideaVim安装及配置

1.安装插件 File-Settings-Plugins,Browse Repositories,输入ideavim,安装。 重启后,在Tools-Vim Emulator启用。 2.快捷键设置 ideaViim键与idea快捷键有冲突,可以在Settings-Other Se...

Funcy1122 ⋅ 32分钟前 ⋅ 0

MySQL中B+Tree索引原理

B+树索引是B+树在数据库中的一种实现,是最常见也是数据库中使用最为频繁的一种索引。B+树中的B代表平衡(balance),而不是二叉(binary),因为B+树是从最早的平衡二叉树演化而来的。在讲B...

浮躁的码农 ⋅ 47分钟前 ⋅ 0

两道面试题,带你解析Java类加载机制

在许多Java面试中,我们经常会看到关于Java类加载机制的考察,例如下面这道题: class Grandpa{ static { System.out.println("爷爷在静态代码块"); }} cl...

1527 ⋅ 51分钟前 ⋅ 0

SpringCloud(Data Flow)

dataflow-server

赵-猛 ⋅ 今天 ⋅ 0

深入理解Java虚拟机

这本书我读到第8章,之后就是在读不下去了。 读到后面是一种痛苦的体验,太多的东西是不全面的,大量的专有名词是没有解释的,读到最后很多东西仅仅是一个侧面,所以我觉得,这本书不适合初学...

颖伙虫 ⋅ 今天 ⋅ 0

NanoPi NEO core/ Ubuntu16.04单网卡配置3个IP地址(2个静态,1个动态)

配置 root@NanoPi-NEO-Core:/etc/network# cat interfacesauto loiface lo inet loopbackallow-hotplug eth0iface eth0 inet static address 172.31.188.249 netmask 255.......

SamXIAO ⋅ 今天 ⋅ 0

三步为你的App集成LivePhoto功能

摘要:LivePhoto是iOS9新推出的一种拍照方式,类似于拍摄Gif图或录制视频片段生成图片。如果没有画面感,可以联想《哈利波特》霍格沃茨城堡的壁画,哈哈,很炫酷有木有,但坑爹的是只有iphone6S以...

壹峰 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部