java集合(四)Map集合之TreeMap 详解

Wesley13
• 阅读 736

一、继承与实现

public class TreeMap<K,V> extends AbstractMap<K,V>  implements NavigableMap<K,V>, Cloneable, java.io.Serializable
  1. TreeMap<K,V>:TreeMap是以key-value形式存储数据的。

  2. extends AbstractMap<K,V>:继承了AbstractMap,实现Map接口时需要实现的工作量大大减少了。

  3. implements NavigableMap:实现了NavigableMap,可以返回特定条件最近匹配的导航方法。方法 lowerEntry、floorEntry、ceilingEntry 和 higherEntry 分别返回与小于、小于等于、大于等于、
    大于给定键的键关联的 Map.Entry 对象,如果不存在这样的键,则返回 null。

  4. implements Cloneable:表明其可以调用clone()方法来返回实例的field-for-field拷贝。

  5. implements Serializable:表明该类是可以序列化的。

二、类属性及说明

/**
 * treeMap的排序规则,如果为null,则根据键的自然顺序进行排序
 */
private final Comparator<? super K> comparator; /** * 红黑数的根节点 */ private transient Entry<K,V> root; /** * 红黑树节点的个数 */ private transient int size = 0; /** * treeMap的结构性修改次数。实现fast-fail机制的关键。 */ private transient int modCount = 0; /** * 视图只有在第一次请求时创建并只创建一个 */ private transient EntrySet entrySet; private transient KeySet<K> navigableKeySet; private transient NavigableMap<K,V> descendingMap;

三、构造函数及说明

  1. TreeMap():使用key的自然排序来构造一个空的treeMap。

  2. TreeMap(Comparator<? super K> comparator):使用给定的比较器来构造一个空的treeMap。

  3. TreeMap(Map<? extends K, ? extends V> m):使用key的自然排序来构造一个treeMap,treeMap包含给定map中所有的键值对

    public TreeMap(Map<? extends K, ? extends V> m) { comparator = null; putAll(m); }
    
  4. TreeMap(SortedMap<K, ? extends V> m):使用指定的sortedMap来构造treeMap。treeMap中含有sortedMap中所有的键值对,键值对顺序和sortedMap中相同。使用一个有序的map构造新的treemap。这个方法需要线性时间

四、主要方法及说明

  1. get方法:

    /**
     * 通用二叉树的查找算法。提供log2(n)的复杂度
     * @param key
     * @return
     */
    final Entry<K,V> getEntry(Object key) {
        // Offload comparator-based version for sake of performance
        // 直接使用指定的比较器查找
        if (comparator != null)
            return getEntryUsingComparator(key);// 与当前方法类似,只是使用compare(o1,o2)比较
        // 不允许null
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
        Entry<K,V> p = root;
        // 查找
        while (p != null) {
            int cmp = k.compareTo(p.key);
            // key小于当前节点取左节点比较
            if (cmp < 0)
                p = p.left;
            // key大于当前节点取右节点比较
            else if (cmp > 0)
                p = p.right;
            // 找到
            else
                return p;
        }
        // 没有找到
        return null;
    }
    
     /**
     * 返回大于等于key的最小键。如果不存在就返回null。
     * 算法:
     * 1.如果key < 当前节点p,寻找左子树,若左子树不存在,p就是最小大于key的
     * 2.如果key > 当前节点p,寻找右子树,若右子树不存在,需要向上回溯第一个大于key的键
     * 即key < 节点p,使用左链接(一个大于等于key的键的左子树中不存在更小的大于等于key的键)
     * @param key
     * @return
     */
    final Entry<K,V> getCeilingEntry(K key) {
        Entry<K,V> p = root;
        while (p != null) {
            // 静态方法,比较器comparator为空就是用默认的比较
            int cmp = compare(key, p.key);
            // key比当前节点小
            if (cmp < 0) {
                // 当前节点存在更小的子节点
                if (p.left != null)
                    p = p.left;
                // 没有更小的子节点,当前节点就是树中最小大于key的节点
                else
                    return p;
            } 
            // key比当前节点大
            else if (cmp > 0) {
                // 当前节点存在更大的子节点
                if (p.right != null) {
                    p = p.right;
                }
                // 当前节点没有更大的节点能大于key,即子树中不存在大于key的键。只能向上回溯第一个使用左链接比较的节点
                // 即当一个节点p大于key时,仍然在左子树中寻找小于p大于key的键,那么第一个左链接节点必定是最小大于key的
                else {
                    Entry<K,V> parent = p.parent;
                    Entry<K,V> ch = p;
                    // parent.left连接时退出循环或不存在大于等于key的键
                    while (parent != null && ch == parent.right) {
                        ch = parent;
                        parent = parent.parent;
                    }
                    return parent;
                }
            } 
            // 找到key相等节点p
            else
                return p;
        }
        return null;
    }
    
     /**
     * 取小于等于key的最大键。遇到第一个key.compareTo(p) > 0的就会到右子树中取最小值
     * 算法:
     * 1.如果key < 当前节点p,若p的左子树存在,就查找左子树,如果不存在,就回溯找第一个小于key的键
     * 即k > 节点p,使用右连接的父节点(原理是当一个节点小于key,就会查找右子树是否有大一点的节点小于key)
     * 2.如果key > 当前节点p,寻找右子树,若右子树不存在就返回p最小大于等于key的
     * @param key
     * @return
     */
    final Entry<K,V> getFloorEntry(K key) {
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = compare(key, p.key);
            // key比当前节点大
            if (cmp > 0) {
                if (p.right != null)
                    p = p.right;
                // 找不到比key更大的键,就返回当前键是小于key的最大键
                else
                    return p;
            } 
            // key比当前节点小
            else if (cmp < 0) {
                if (p.left != null) {
                    p = p.left;
                } 
                // 找不到
                else {
                    // 如果左子树中不存在跟接近key的节点就返回第一个右链接的父节点
                    Entry<K,V> parent = p.parent;
                    Entry<K,V> ch = p;
                    // 当parent使用右链接时退出循环或不存在小于等于key的键
                    while (parent != null && ch == parent.left) {
                        ch = parent;
                        parent = parent.parent;
                    }
                    return parent;
                }
            } 
            // 相等
            else
                return p;
    
        }
        return null;
    }
    
  2. put方法:

    /**
     * 在map中关联指定的键值对。不允许插入null。只对插入操作进行红黑树修复。提供log(n)复杂度
     */
    public V put(K key, V value) {
        Entry<K,V> t = root;
        // 根节点为null就直接插入新键
        if (t == null) {
            compare(key, key); // type (and possibly null) check
    
            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        // 引用放在循环外。是否感觉可以改善自己的代码啦啦???等到知道具体机制可能就不会这样想了。手动滑稽
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        // 使用比较器查找到key进行替换操作
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                // 相等就直接替换值
                else
                    return t.setValue(value);
            } while (t != null);
        }
        // 使用默认的顺序查找到key进行替换操作
        else {
            // 不允许为null
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        // 将新节点插入到父节点
        Entry<K,V> e = new Entry<>(key, value, parent);
        // 判断父节点应用哪个连接新节点
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        // 修复操作
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }
    
    /**
     * 将指定映射中的所有映射关系复制到此映射中。如果已经存在的映射会被替换新的值
     * 对于空treemap使用putAll提供线性时间。好于非空treemap的n*logn
     * @author Navy D
     */
    public void putAll(Map<? extends K, ? extends V> map) {
        int mapSize = map.size();
        // treemap是空的  参数map是sortedMap
        if (size==0 && mapSize!=0 && map instanceof SortedMap) {
            Comparator<?> c = ((SortedMap<?,?>)map).comparator();
            // 比较器一样为null或同一个对象
            if (c == comparator || (c != null && c.equals(comparator))) {
                ++modCount;
                try {
                    // 使用迭代器通过key构建排序数据,需要线性时间 这个方法暂时没用到就不看了,用到再更新吧
                    buildFromSorted(mapSize, map.entrySet().iterator(),
                                    null, null);
                } catch (java.io.IOException cannotHappen) {
                } catch (ClassNotFoundException cannotHappen) {
                }
                return;
            }
        }
        // abstractMap.putAll方法采用for调用put方法
        super.putAll(map);
    }
    
  3. delete方法:

    /**
     * 在map中删除指定的键和关联的值
     */
    public V remove(Object key) {
        // 查找
        Entry<K,V> p = getEntry(key);
        if (p == null)
            return null;
    
        V oldValue = p.value;
        // 删除键值对
        deleteEntry(p);
        return oldValue;
    }
    
     /**
     * 删除节点p且平衡树
     * 对于有两个子节点的删除节点p,使用右子树的最小节点替换,
     * 然后根据这个最小节点是叶子结点就先修复再删除,若有一个右子树就使用右子树中节点与父节点连接
     * 对于有一个子节点的删除节点p,使用删除节点的子节点与父节点连接
     * 对于没右子节点就修复后再删除
     * @param p
     */
    private void deleteEntry(Entry<K,V> p) {
        modCount++;
        size--;
        // If strictly internal, copy successor's element to p and then make p
        // point to successor.
        // 待删除结点有两个孩子用中序后继覆盖删除节点
        if (p.left != null && p.right != null) {
            // 返回p的右子树中的最小节点
            Entry<K,V> s = successor(p);
            // 将后继的键值覆盖删除点p的键值  没有更换颜色
            p.key = s.key;
            p.value = s.value;
            // 将p引用为后继节点 注意不是覆盖到删除节点 删除点p已经被替换为后继
            p = s;
        } // p has 2 children
    
        // Start fixup at replacement node, if it exists.
        // 如果删除节点只有一个孩子就返回这个孩子。注意如果进入上一个if,返回的p如果是叶节点,即replacement=null
        // p如果不是叶节点,只会存在右子节点
        Entry<K,V> replacement = (p.left != null ? p.left : p.right);
        // 删除节点存在一个子节点(左或右),父节点链接删除节点的子节点
        if (replacement != null) {
            // Link replacement to parent
            // 连接p的父节点与替换节点  删除p
            replacement.parent = p.parent;
            if (p.parent == null)
                root = replacement;
            // 替换父节点的左链接
            else if (p == p.parent.left)
                p.parent.left  = replacement;
            // 替换右链接
            else
                p.parent.right = replacement;
    
            // Null out links so they are OK to use by fixAfterDeletion.
            p.left = p.right = p.parent = null;
    
            // Fix replacement
            // 只有删除点是BLACK的时候,才会触发删除修复,因为删除RED节点不会破坏红黑树的任何约束,而删除BLACK节点会导致有不同个数的黑色节点
            if (p.color == BLACK)
                fixAfterDeletion(replacement);
        }
        // 只有root一个节点
        else if (p.parent == null) { // return if we are the only node.
            root = null;
        }
        // 没有孩子节点 p是叶子结点
        else { //  No children. Use self as phantom replacement and unlink.
            if (p.color == BLACK)
                fixAfterDeletion(p);
            // 将连接删除
            if (p.parent != null) {
                if (p == p.parent.left)
                    p.parent.left = null;
                else if (p == p.parent.right)
                    p.parent.right = null;
                p.parent = null;
            }
        }
    }
    
  4. iterator方法:

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Easter79 Easter79
3年前
swap空间的增减方法
(1)增大swap空间去激活swap交换区:swapoff v /dev/vg00/lvswap扩展交换lv:lvextend L 10G /dev/vg00/lvswap重新生成swap交换区:mkswap /dev/vg00/lvswap激活新生成的交换区:swapon v /dev/vg00/lvswap
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
4个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Wesley13 Wesley13
3年前
Java爬虫之JSoup使用教程
title:Java爬虫之JSoup使用教程date:201812248:00:000800update:201812248:00:000800author:mecover:https://imgblog.csdnimg.cn/20181224144920712(https://www.oschin
Wesley13 Wesley13
3年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Wesley13 Wesley13
3年前
Java 之 HashMap 集合
一、HashMap概述java.util.HashMap<k,v集合implementsMap<k,v接口HashMap集合的特点:1、HashMap集合底层是哈希表:查询速度特别的快JDK1.8之前:数组单向链表JDK1.8之后:数组单向链表|红黑树(
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
10个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这