文档章节

TreeMap浅析(一)

清尘V
 清尘V
发布于 2016/05/09 23:18
字数 596
阅读 34
收藏 3

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

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


© 著作权归作者所有

共有 人打赏支持
上一篇: java的NIO
下一篇: LinkedList浅析
清尘V
粉丝 41
博文 107
码字总数 47780
作品 0
青岛
程序员
私信 提问
Java集合框架:总结

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

u013256816
2016/03/18
0
0
hashMap 1.8.0_91 浅析

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

锦语冰
2016/11/23
2
0
Spring Boot之浅析配置项解析

Spring Boot之浅析配置项解析 木叶之荣,2018年01月 Spring Boot之浅析配置项解析(一) Spring Boot之浅析配置项解析(二) Spring Boot之浅析配置项解析(三) Spring Boot之浅析配置项解析...

单农
06/09
0
0
openfire xmpp sasl 浅析

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

今幕明
2016/08/26
33
0
Java集合容器系列09 - TreeSet

一、TreeSet介绍 TreeMap是底层基于TreeMap的NavigableSet实现,容器的元素存储在TreeMap键值对映射的key中,它使用元素的自然顺序或者传入的比较器Comparator对元素进行排序。它为基本操作例...

老韭菜
08/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

dubbo 搭建与使用

官网:http://dubbo.apache.org/en-us/ 一,安装监控中心(可以不安装) admin管理控制台,monitor监控中心 下载 bubbo ops 这个是新版的,需要node.js环境,我没有就用老版的了...

小兵胖胖
1分钟前
0
0
mac 下 mysql 8.0.13 安装并记录遇到的问题 以便以后查看

安装 官网mysql 下载地址 安装过程 省去 安装好之后 下载navicat 错误1 链接 遇到 mysql 2003 - Can't connect to MySQL server 错误, 解决方案 重启mysql 服务 #错误2 ERROR 1045: Acces...

杭州-IT攻城狮
昨天
5
0

中国龙-扬科
昨天
1
0
[Spring4.x]基于spring4.x纯注解的Web工程搭建

在前文中已经说明了如何基于 Spring4.x+ 版本开发纯注解的非web项目,链接如下: https://my.oschina.net/morpheusWB/blog/2985600 本文则主要说明,如何在Web项目中,"基于spring纯注解方式...

morpheusWB
昨天
16
0
基础编程题目集-7-13 日K蜡烛图

股票价格涨跌趋势,常用蜡烛图技术中的K线图来表示,分为按日的日K线、按周的周K线、按月的月K线等。以日K线为例,每天股票价格从开盘到收盘走完一天,对应一根蜡烛小图,要表示四个价格:开...

niithub
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部