来,进来的小伙伴们,我们认识一下。

我是俗世游子,在外流浪多年的Java程序猿

前面我们已经介绍了HashMap,今天我们来看看Map的另外一个子类:TreeMap

前置知识

首先在介绍TreeMap之前,我们先了解一些前置知识,往下看

申博太阳城直属官网六合彩登入:排序方式

在了解排序方式之前,我们先来聊一聊什么是:有序,无序,排序

有序

保证插入的顺序和在容器中存储的顺序是一致的,典型代表:

  • List

无序

插入的顺序和在容器中存储的顺序不一致的,典型代表:

  • Set
  • Map

排序

基于某种规则在迭代的时候输出符合规则的元素顺序, 比如:

  • TreeMap
  • TreeSet

那么我们来看具体的排序方式

那么,现在有一种需求,就是我们按照一定顺序将集合中的元素进行输出,那么我们该怎么做呢?基于这种方式,Java为我们提供了两种实现方式:

Comparable

实现该接口需要一个实体对象,然后重写其compareTo(),我们来看例子:

// 定义一个Student对象
class Student implements Comparable<Student> {

    public int id;
    public String name;
    public int age;

    public Student(int id, String name, int age) {
        this.id = id;
        this.name = name;
        this.age = age;
    }

    /**
     * 对比方法
     */
    @Override
    public int compareTo(Student o) {
        // 按照年龄从小到大的排序方式
        return age - o.age;
    }

    @Override
    public String toString() {
        return "Student{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

// 小案例
ArrayList<Student> students = new ArrayList<Student>(6) {{
    add(new Student(1, "张三", 20));
    add(new Student(2, "里斯", 18));
    add(new Student(3, "王五", 38));
    add(new Student(4, "赵柳", 10));
    add(new Student(5, "天气", 77));
}};

// 排序前的输出
System.out.println("排序前的输出:");
System.out.println(students);

System.out.println("================");
// 排序操作
Collections.sort(students);
System.out.println("排序后的输出:");
System.out.println(students);

/**
排序前的输出
[Student{id=1, name='张三', age=20}, Student{id=2, name='里斯', age=18}, Student{id=3, name='王五', age=38}, Student{id=4, name='赵柳', age=10}, Student{id=5, name='天气', age=77}]
================
[Student{id=4, name='赵柳', age=10}, Student{id=2, name='里斯', age=18}, Student{id=1, name='张三', age=20}, Student{id=3, name='王五', age=38}, Student{id=5, name='天气', age=77}]
**/

可以看到我们已经实现了按照年龄从小到大的顺序进行排序的

这里需要注意一点,在compareTo()中,是传入的对象和当前对象进行对比:

  • 如果对比大于0,说明按照降序排序
  • 如果对比小于0,说明按照升序排序
  • 如果对比等于0,当前不变

Comparator

这种方式是通过外部类的方式进行编写,还是上面的代码,我们改一些地方:

Collections.sort(students, new Comparator<Student>() {
    @Override
    public int compare(Student o1, Student o2) {
        // 按照ID降序排序
        return (int) (o2.id - o1.id);
    }
});

/**
排序前的输出:
[Student{id=1, name='张三', age=20}, Student{id=2, name='里斯', age=20}, Student{id=3, name='王五', age=38}, Student{id=4, name='赵柳', age=10}, Student{id=5, name='天气', age=77}]
================
排序后的输出:
[Student{id=5, name='天气', age=77}, Student{id=4, name='赵柳', age=10}, Student{id=3, name='王五', age=38}, Student{id=2, name='里斯', age=20}, Student{id=1, name='张三', age=20}]
**/

查看,已经实现了需求

compare()中返回值的对比和第一种方式是一样的

大家按照实际的需求选择合理的排序方式吧

树介绍

是一种数据结构,它是由n(n>=1)个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:

  • 每个结点有零个或多个子结点;
  • 没有父结点的结点称为根结点;
  • 每一个非根结点有且只有一个父结点;
  • 除了根结点外,每个子结点可以分为多个不相交的子树

摘抄自:百度百科:Tree

二叉树

二叉树是树形结构中的一种重要类型,是我们在数据结构中最常用的树结构之一,每个节点下最多只有两个子节点

二叉搜索树

顾名思义,二叉搜索树是以二叉树来组织的,对比二叉树,拥有以下特性:

  • 每个节点下最多只拥有两个节点
  • 采用左小右大的规则插入元素节点,如果相等,那么插入到右边
  • 所以在遍历节点的时候可以采用 二分法 来减少元素的查询

二叉搜索树的插入过程

平衡树

也成AVL树,是基于二叉搜索树的一种扩展,也就是说拥有二叉搜索树的全部特性。二叉搜索树存在缺点:

  • 数据插入方式,容易造成两边节点,一边长一边短的问题,这样在通过 二分法来遍历元素的时候也存在性能问题

AVL树针对这一情况进行了改进:

  • AVL树会对不平衡的树进行一个旋转,优化整个数据结构,保证整个树的平衡,保证整个二分查找的效率
  • 旋转规则:每个节点的左右子节点的高度之差的绝对值最多为1, 即平衡因子为范围[-1,1]

红黑树

基于平衡树的一种演进,也存在旋转操作保持二叉树的平衡,同时在此基础上添加变色操作,拥有如下特性:

  • 节点是红色或者黑色
  • 根节点是黑色,每个叶子节点(NUIL节点)是黑色的
  • 如果一个节点是红色的,那么其子节点就是黑色的(也就是说不能存在连续的红色节点)
  • 从任意节点到其每个叶子的所有路径都包含相同数目的黑色节点
  • 最长路径不超过最短路径的2倍

这里没有讲解的很详细,简单的说一下有个概念

源码分析TreeMap

下面我们来看一下TreeMap

之前我说的有些问题:我们遇到一个类,它最重要的是类中的注释,我们先来看TreeMap的注释是如何介绍TreeMap的:

  • 基于红黑树方式实现的Map
  • 按照自然排序或者是指定的方式排序,这取决于我们所使用的的构造方法,所以说,TreeMap是有序的,我们可以指定其排序方式
  • TreeMap是线程不安全的,如果想要实现,需要对TreeMap进行包装
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

构造方法

下面我们来具体看看我们如何使用TreeMap

TreeMap<String, String> treeMap = new TreeMap<>();
new TreeMap<String, Long>(new Comparator<String>() {
    @Override
    public int compare(String o1, String o2) {
        return 0;
    }
});
public TreeMap() {
    comparator = null;
}

public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

第二个构造方法传入一个比较器,这个我们在 排序方式 中就已经说到,也明白了返回的含义

但是这里要注意一点:如果我们没有传入 比较器,默认为null,那么我们需要明白:

  • 传入的Key必须要实现Comparable接口的类型,这一点我们在put()方法中会跟源码说明

put()

在了解该方法之前,我们先来了解一个类:

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK;

    Entry(K key, V value, Entry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }
}

我们已经知道,TreeMap底层是采用红黑树的结构来存储数据,那么对应到代码中的实现就是上面的样子。

下面我们来看具体是如何添加元素的

public V put(K key, V value) {
    Entry<K,V> t = root;
    // 根节点
    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;
    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 {
        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;
}

总结一下,可以分为四步来进行操作:

  • 判断如果当前根节点为null,那么当前插入的第一个元素就为根节点元素

  • 如果存在根节点,那么再添加元素的时候根据排序器进行对比,验证当前元素应该在左侧还是在右侧,如果对比为0,那么说明当前元素存在于TreeMap中,直接将其进行覆盖。这里也就说明了一个问题:在TreeMap中,不会存在重复元素
  • 找到自己所对应的位置,然后进行指针引用
  • 节点变色操作和旋转操作

前面3点都很简单,无非就是通过do..while循环通过排序器进行对比,这里有一点,也就是在构造方法里我提到的一点:

class A {
    public Long id;
}

TreeMap<A, String> map = new TreeMap<>();
map.put(new A(), "11");
map.put(new A(), "11");
System.out.println(map);

// java.lang.ClassCastException: zopx.top.study.jav.maps.A cannot be cast to java.lang.Comparable

在采用默认构造方法的时候,申博太阳城直属官网六合彩登入:这样的方式出现错误:类型转换异常,这也就是为什么TreeMap:Key必须要实现Comparable的原因

下来我们重点看看节点变色和旋转操作

private void fixAfterInsertion(Entry<K,V> x) {
    // 将当前节点标记为红色
    x.color = RED;

    // 当插入元素后出现不平衡,则进行调整
    while (x != null && x != root && x.parent.color == RED) {
        // 判断是否是左边节点
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateLeft(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            // 否则就是右边节点
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateRight(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    // 根节点永远是黑色
    root.color = BLACK;
}

下面我通过画图来进行代码分析吧,这样更容易理解:

这是一个最简单的例子,节点也非常少,大家可以自己按照上面的方式过一下代码,理解下代码的逻辑

右旋操作

private void rotateRight(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> l = p.left;
        p.left = l.right;
        if (l.right != null) l.right.parent = p;
        l.parent = p.parent;
        if (p.parent == null)
            root = l;
        else if (p.parent.right == p)
            p.parent.right = l;
        else p.parent.left = l;
        l.right = p;
        p.parent = l;
    }
}

同样,在红黑树中还包含左旋的操作,大家可以自己看下源代码: rotateLeft(),和右旋很类似

最好是能够边分析源代码,边通过画图的方式加深理解

上面也就是TreeMap基于红黑树的实现方式,大家可以结合上面介绍的红黑树的特性好好理解下

remove(Object key) 方法和put()方法相差不多,大家可以自己看看源码

get()

下面简单来说一下get()方法:

Entry<K,V> p = getEntry(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();

    // 默认构造器
    @SuppressWarnings("unchecked")
    Comparable<? super K> k = (Comparable<? super K>) key;
    Entry<K,V> p = root;
    while (p != null) {
        // 不断对比,如果==0,那么就是当前需要的Entry
        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) {
    @SuppressWarnings("unchecked")
    K k = (K) key;
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        Entry<K,V> p = root;
        while (p != null) {
            // 不断对比,如果==0,那么就是当前需要的Entry
            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;
}

该方法还是比较简单的,也就是在while()循环中通过比较器进行对比

TreeMap更多api方法

更多关于TreeMap使用方法推荐查看其文档:

TreeMap API文档

数据结构可视化网站