首页 > 其他分享 >13-TreeSet和TreeMap基本介绍

13-TreeSet和TreeMap基本介绍

时间:2024-07-13 13:12:24浏览次数:6  
标签:13 TreeSet TreeMap key null public cmp

13-TreeSet和TreeMap基本介绍

介绍汇总:

  1. TreeSet基本介绍
  2. TreeMap基本介绍

1-TreeSet基本介绍

  1. TreeSet 类用于存储一组对象,并将对象按照自然规则(实现 Comparator 接口的)或者指定 Comparator 对象的比较器进行排序。
  2. TreeSet 类中的底层是 TreeMap 。
  3. key 值不可以为 null ,也不可以重复。
  4. 自然规则排序和指定比较器排序
// 无参构造器,使用元素的自然规则排序
public TreeSet() {
        this(new TreeMap<E,Object>());
    }

// 指定比较器的构造器,按照该比较器中的规则进行排序
public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));
    }
  1. 使用自然规则的话,就需要注意元素需实现 Comparable 接口,并且加入的元素有某种关联,例如,可以进行比较以及同一类元素。
package set.treeset;

import java.util.TreeSet;

public class TreeSetSource {

    @SuppressWarnings({"all"})
    public static void main(String[] args) {

        TreeSet treeSet = new TreeSet();

        treeSet.add("aaa");
        treeSet.add("bca");
        treeSet.add("aba");
        treeSet.add("aac");

        System.out.println("====treeSet中自然元素有" + treeSet + "====");
    }
}

  1. 指定比较器
package set.treeset;

import java.util.Comparator;
import java.util.TreeSet;

public class TreeSetComparator {

    @SuppressWarnings({"all"})
    public static void main(String[] args) {

        TreeSet treeSet = new TreeSet(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {

                // 按照字符串的大小比较 ((String) o1).compareTo((String) o2)
                // 结果为 0 的话,表示相等
                // 还可以根据字符串长度进行排序 ((String) o1).length() - ((String) o2).length()
                // 若结果为 0 ,则说明相等,重复了(TreeMap 的话会更新对应的 value 值)
                return ((String) o1).length() - ((String) o2).length();
            }
        });

        treeSet.add("adk");
        treeSet.add("bkd");
        treeSet.add("kij");
        treeSet.add("a");
        treeSet.add("ccccc");

        System.out.println("====treeSet中自然元素有" + treeSet + "====");
    }
}

注:加入的元素符合比较器,可以进行相互的比较。

  1. TreeSet(TreeMap)部分底层源码分析
// TreeSet.add 添加数据
public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }

// TreeMap.put 存储数据
    public V put(K key, V value) {
        // 获取红黑树的根结点
        Entry<K,V> t = root;
        // 根结点为空,说明为存储数据
        if (t == null) {
            // 主要确认 key 是否为空,为空会抛异常
            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
        // 获取 TreeMap 中的比较器
        Comparator<? super K> cpr = comparator;
        // 比较器不为空,则使用指定的比较器进行插入数据并排序
        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);
        }
        // 比较器未指定,使用元素的自然规则
        else {
            // 确保 key 不为空
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
            // 转换成 Comparable 对象,为了获取 compareTo 方法
                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;
    }

2-TreeMap基本介绍

  1. TreeMap 类用于存储一组键值对,并将键值对按照自然规则(实现 Comparator 接口的)或者指定 Comparator 对象的比较器将 Key 值排序,并以此顺序决定键值对的顺序。
  2. TreeMap 底层是红黑树。
  3. Key 值不可以重复,也不可以为 null,而 Value 可以重复,也可以为 null。
  4. 使用自然规则的话,就需要注意元素需实现 Comparable 接口,并且加入的元素有某种关联,例如,可以进行比较以及同一类元素。
package map.treemap;

import java.util.TreeMap;

public class TreeMapSource {

    @SuppressWarnings({"all"})
    public static void main(String[] args) {

        TreeMap treeMap = new TreeMap();

        treeMap.put("aaa","aaa");
        treeMap.put("bca","bca");
        treeMap.put("aba","aba");
        treeMap.put("aac","aac");

        System.out.println("====treeMap中自然元素有" + treeMap + "====");
    }
}

注:加入的元素的 key 符合比较器,可以进行相互的比较。

  1. 指定比较器
package map.treemap;

import java.util.Comparator;
import java.util.TreeMap;

public class TreeMapComparator {

    @SuppressWarnings({"all"})
    public static void main(String[] args) {

        TreeMap treeMap = new TreeMap(new Comparator() {

            @Override
            public int compare(Object o1, Object o2) {

                // 按照字符串的大小比较 ((String) o1).compareTo((String) o2)
                // 结果为 0 的话,表示相等
                // 还可以根据字符串长度进行排序 ((String) o1).length() - ((String) o2).length()
                // 若结果为 0 ,则说明相等,重复了(TreeMap 的话会更新对应的 value 值)
                return ((String) o1).length() - ((String) o2).length();
            }
        });

        treeMap.put("aaa","aaa");
        treeMap.put("ab","ab");
        treeMap.put("ccc","ccc");
        treeMap.put("aadcb","aadcb");
        treeMap.put("ddddddd","aaa");

        System.out.println("====treeMap中自然元素有" + treeMap + "====");
    }
}

  1. TreeSet(TreeMap)部分底层源码分析
 // TreeSet.add 添加数据
public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }

// TreeMap.put 存储数据
    public V put(K key, V value) {
        // 获取红黑树的根结点
        Entry<K,V> t = root;
        // 根结点为空,说明为存储数据
        if (t == null) {
            // 主要确认 key 是否为空,为空会抛异常
            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
        // 获取 TreeMap 中的比较器
        Comparator<? super K> cpr = comparator;
        // 比较器不为空,则使用指定的比较器进行插入数据并排序
        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);
        }
        // 比较器未指定,使用元素的自然规则
        else {
            // 确保 key 不为空
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
            // 转换成 Comparable 对象,为了获取 compareTo 方法
                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;
    }

标签:13,TreeSet,TreeMap,key,null,public,cmp
From: https://www.cnblogs.com/Yao-happy/p/18299449

相关文章

  • 打卡信奥刷题(313)用Scratch图形化工具信奥P2165[普及组/提高] [AHOI2009] 飞行棋
    [AHOI2009]飞行棋题目描述给出圆周上的若干个点,已知点与点之间的弧长,其值均为正整数,并依圆周顺序排列。请找出这些点中有没有可以围成矩形的,并希望在最短时间内找出所有不重复矩形。输入格式第一行为正整数N......
  • 上网记录20240713
     模块化医学图像处理可视化软件 https://www.mevislab.de/https://github.com/MeVisLabMeVisLabHelpResourceshttps://mevislabdownloads.mevis.de/docs/current/MeVisLab/Resources/Documentation/Publish/index.html  https://www.kitware.com/OpenInventorThe......
  • 大气热力学(13)——强对流指数之二(热力稳定性指数)
    本篇文章继续上篇的内容,介绍了根据预报员多年经验总结的各种强对流预报指数,希望这部分内容能对你有所帮助。目录13.1沙氏指数(ShowalterIndex,SI)13.2抬升指数(LiftedIndex,LI)13.3对流性稳定度指数(IC)13.4K指数(K-Index)13.4.1K指数的定义与计算公式13.4.2使用K指数预报强对......
  • 每日一笑7.13
    #include<bits/stdc++.h>#include<windows.h>usingnamespacestd;intmain(){ printf("盘点全网十大爆笑名字:\n"); printf(" 1.琵燕,多么好听的名字,可惜他姓梅。\n"); Sleep(2000); printf(" 2.拔杰,多么高端的名字,可惜他姓朱。\n"); Sleep(2000); print......
  • 【集训】7.13
    目录逆元线性求逆元递推,复习;离线求逆元,复习;fermat小定理,复习;欧拉定理,复习组合数计算lucas定理,复习;逆元7.13:三种方法复习exgcdfermatlinear线性求逆元递推,复习;离线求逆元,复习;MyLinkfermat小定理,复习;欧拉定理,复习组合数计算pascal恒等式计算前缀积和逆元lucas定理......
  • abc134E - Sequence Decomposing
    abc134E-SequenceDecomposing题意:给定一个序列,将其划分成若干个不相交的严格上升子序列,求划分的最小的子序列数量。题解:我们可以定义严格偏序关系,\(i\precj\)当\(i<j\)且\(a_i<a_j\),也就是我们要将整个序列划分成若干个链。根据Dilworth’stheorem,最小链覆盖数=最大......
  • Visual Studio 2013俄语环境基石:‘mfc120rus.dll’解析与丢失修复全案
    mfc120rus.dll是一个动态链接库(DLL)文件,与MicrosoftFoundationClasses(MFC)相关。MFC是一个广泛使用的C++类库,用于简化Windows应用程序的开发。mfc120rus.dll特别地,是MFC库的俄语版本,用于支持俄语字符集和语言环境,它是MFC12.0版本的一部分,常用于VisualStudio2013中编译的......
  • SQL Server 2022 RTM DGR (CU13+GDR) 发布,修复高危安全漏洞
    SQLServer2022RTMDGR(CU13+GDR)发布,修复高危安全漏洞SQLServerNativeClientOLEDB提供程序远程代码执行漏洞CVE-2024-35272修复请访问原文链接:https://sysin.org/blog/sql-server-2022/,查看最新版。原创作品,转载请保留出处。作者主页:sysin.orgSQLServer2022......
  • HDU 1213 How Many Tables
    题目链接:HDU1213HowManyTables思路    经典并查集,将互相认识的人全部放在一个集合内,然后计算有几个集合就有几个桌子。代码#include<iostream>usingnamespacestd;#definelllonglongconstintN=1e3+10;intfa[N];voidinit(intn){for(i......
  • 【YashanDB知识库】yasql登录报错:YAS-00413
    【问题分类】错误码处理【关键字】yasql,00413【问题描述】使用工具设置不同并发迁移数据的过程中,导致yasql登录报错:YAS-00413【问题原因分析】工具使用与数据库使用资源超过了操作系统配置参数设置【解决/规避方法】●查看操作系统yashan用户当前打开文件文件数SQLlsof|......