文档章节

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


© 著作权归作者所有

共有 人打赏支持
清尘V
粉丝 42
博文 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

没有更多内容

加载失败,请刷新页面

加载更多

GO冒泡,二分查找

package mainimport("fmt")func main() {var arr [5]int = [5]int{11,13,9,2,25}maopao(&arr)fmt.Println("arr = ", arr) //[2 9 11 13 25]findIndex := binaryFind(&arr, 0......

汤汤圆圆
27分钟前
1
0
工作2年半跳槽面试阿里,成功拿到offer,凭什么?

2015年刚毕业的我,进入了一家小小的公司实习工作,在学校学了三年软件开发的我,还是想去寻找一份互联网行业的工作,这样更能学以致用发挥自己的特长。一直到18年三月份,我辞掉已有的工作,...

java知识分子
32分钟前
1
0
讲述下:Linux的10个最危险的命令

导读 Linux命令行佷有用、很高效,也很有趣,但有时候也很危险,尤其是在你不确定你自己在正在做什么时候。这篇文章将会向你介绍十条命令,但你最好不要尝试着去使用。 当然,以下命令通常都...

问题终结者
36分钟前
1
0
分库分表后如何部署上线?

引言 我们先来讲一个段子 面试官:“有并发的经验没?” 应聘者:“有一点。” 面试官:“那你们为了处理并发,做了哪些优化?” 应聘者:“前后端分离啊,限流啊,分库分表啊。。” 面试官:...

Java烂猪皮
41分钟前
1
0
Redis源码阅读笔记-快速列表

快速列表 快速列表(quicklist)是由压缩列表(ziplist)组成的一个双向链表,链表中,每一个节点都是以压缩列表(ziplist)的结构保存。 在 Redis3.2 后加入的新数据结构,在列表键中取代了双向链...

Jian_Ming
59分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部