13-TreeSet和TreeMap基本介绍

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

热门相关:隐婚365天:江少,高调宠!   我的女友是丧尸   4人4性   天龙邪尊   恶魔总裁霸道宠:老婆,甜似火