首页 > 基础资料博客日记

13-TreeSet和TreeMap基本介绍

2024-07-13 13:00:04基础资料围观128次

这篇文章介绍了13-TreeSet和TreeMap基本介绍，分享给大家做个参考，收藏Java资料网收获更多编程知识

13-TreeSet和TreeMap基本介绍

介绍汇总：

TreeSet基本介绍
TreeMap基本介绍

1-TreeSet基本介绍

TreeSet 类用于存储一组对象，并将对象按照自然规则（实现 Comparator 接口的）或者指定 Comparator 对象的比较器进行排序。
TreeSet 类中的底层是 TreeMap 。
key 值不可以为 null ，也不可以重复。
自然规则排序和指定比较器排序

// 无参构造器，使用元素的自然规则排序
public TreeSet() {
        this(new TreeMap<E,Object>());
    }

// 指定比较器的构造器，按照该比较器中的规则进行排序
public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));
    }

使用自然规则的话，就需要注意元素需实现 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 + "====");
    }
}

指定比较器

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 + "====");
    }
}

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

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基本介绍

TreeMap 类用于存储一组键值对，并将键值对按照自然规则（实现 Comparator 接口的）或者指定 Comparator 对象的比较器将 Key 值排序，并以此顺序决定键值对的顺序。
TreeMap 底层是红黑树。
Key 值不可以重复，也不可以为 null，而 Value 可以重复，也可以为 null。
使用自然规则的话，就需要注意元素需实现 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 符合比较器，可以进行相互的比较。

指定比较器

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 + "====");
    }
}

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;
    }

文章来源:https://www.cnblogs.com/Yao-happy/p/18299449
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！

标签：

上一篇：“爆炸性更新！JDK 17携全新语法特性强势来袭，开发者必看的升级亮点“（1）
下一篇：2024年Java最新Java学习路线总结，搬砖工逆袭Java架构师（全网最强），Java开发快速上手

首页 > 基础资料博客日记

13-TreeSet和TreeMap基本介绍

13-TreeSet和TreeMap基本介绍

1-TreeSet基本介绍

2-TreeMap基本介绍

相关文章

最新发布

点击排行

本站推荐

标签云

首页 > 基础资料 博客日记

13-TreeSet和TreeMap基本介绍

13-TreeSet和TreeMap基本介绍

1-TreeSet基本介绍

2-TreeMap基本介绍

相关文章

最新发布

点击排行

本站推荐

标签云

首页 > 基础资料博客日记