9.5TreeMap设计思想

目录介绍

01.TreeMap特点
02.何时用TreeMap
03.TreeMap简单使用
04.案例训练

01.TreeMap特点

TreeMap集合结构特点
- 键的数据结构是红黑树,可保证键的排序和唯一性
- 排序分为自然排序和比较器排序，如果使用的是自然排序,对元素有要求,要求这个元素需要实现 Comparable 接口
- 线程是不安全的效率比较高
```
public TreeMap(): 自然排序
public TreeMap(Comparator<? super K> comparator):  使用的是比较器排序
```

02.何时用TreeMap

之前已经学习过HashMap和LinkedHashMap了，HashMap不保证数据有序，LinkedHashMap保证数据可以保持插入顺序，而如果我们希望Map可以保持key的大小顺序的时候，我们就需要利用TreeMap了。

03.TreeMap简单使用

普通添加数据

代码如下所示

TreeMap<Integer, String> tmap = new TreeMap<Integer, String>();
tmap.put(1, "语文");
tmap.put(3, "英语");
tmap.put(2, "数学");
tmap.put(4, "政治");
tmap.put(5, "历史");
tmap.put(6, "地理");
tmap.put(7, "生物");
tmap.put(8, "化学");
for(Entry<Integer, String> entry : tmap.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

使用红黑树的好处是能够使得树具有不错的平衡性，这样操作的速度就可以达到log(n)的水平了。

TreeMap集合键是String值是String的案例

- TreeMap: 键的数据结构是红黑树,可保证键的排序和唯一性

public static void main(String[] args) {
    /**使用TreeMap集合存储元素,键是Integer类型 , 值是String类型*/
    // 创建TreeMap集合对象
    TreeMap<Integer , String> hm = new TreeMap<Integer , String> () ;
    // 添加元素
    hm.put(23, "乔丹") ;
    hm.put(24, "科比") ;
    hm.put(1, "麦迪") ;
    hm.put(3, "艾弗森") ;
    // 遍历
    Set<Entry<Integer,String>> entrySet = hm.entrySet() ;
    for(Entry<Integer,String> en : entrySet) {
        // 获取键
        Integer integer = en.getKey() ;
        // 获取值
        String value = en.getValue() ;
        // 输出
        System.out.println(integer + "---" + value);
    }
}

TreeMap集合键是Student值是String的案例

public static void main(String[] args) {
    /**
     * 需求: 使用TreeMap集合存储元素,键是Student类型, 值是String类型
     * 按照年龄大小进行排序
     */
    // 创建自定义对象
    Student s1 = new Student("郭靖" , 24) ;
    Student s2 = new Student("杨过" , 18) ;
    Student s3 = new Student("乔峰" , 25) ;
    Student s4 = new Student("令狐冲" , 16) ;
    // 创建TreeMap集合对象
    TreeMap<Student ,String> tm = new TreeMap<Student , String>(new Comparator<Student>() {
        @Override
        public int compare(Student s1, Student s2) {
            int num = s1.getAge() - s2.getAge() ;
            int num2 = (num == 0) ? s1.getName().compareTo(s2.getName()) : num ;
            return num2;
        }
    }) ;
    // 添加元素
    tm.put(s1, "哈哈") ;
    tm.put(s2, "呵呵") ;
    tm.put(s3, "打酱油") ;
    tm.put(s4, "给力") ;
    // 遍历
    Set<Entry<Student,String>> entrySet = tm.entrySet() ;
    for(Entry<Student,String> en : entrySet) {
        // 获取键
        Student student = en.getKey() ;
        // 获取值
        String value = en.getValue() ;
        // 输出
        System.out.println("key: [name: " + student.getName() + " , age: " + student.getAge() + "] , value: " + value );
    }
}

04.案例训练

"aababcabcdabcde",获取字符串中每一个字母出现的次数要求结果:a(5)b(4)c(3)d(2)e(1)
- "aababcabcdabcde" 按照键值对的形式存储到TreeMap集合中
- 分析:
- 1，遍历字符串,获取每一个字符,然后将当前的字符作为键 , 上map集合中查找对应的值
- 2，如果返回的值不是null 对值进行+1 , 在把当前的元素作为键 , 值是+1以后的结果存储到集合中
- 3，如果返回的是是null , 不存在 , 就把当前遍历的元素作为键 , 1 作为值,添加到集合中

代码如下

public static void main(String[] args) {
    // 定义字符串
    String s = "aababcabcdabcde" ;
    // 创建TreeMap集合对象
    TreeMap<Character , Integer> tm = new TreeMap<Character , Integer>() ;
    // 遍历字符串
    for(int x = 0 ; x < s.length() ; x++) {
        // 获取当前索引出对应的字符
        char ch = s.charAt(x) ;
        // 找值
        Integer value = tm.get(ch) ;
        // 判断
        if(value == null) {
            tm.put(ch, 1) ;
        }else {
            value += 1 ;
            tm.put(ch, value) ;
        }
    }       
    // 遍历Map集合按照指定的形式拼接字符串
    StringBuilder sb = new StringBuilder() ;
    Set<Entry<Character,Integer>> entrySet = tm.entrySet() ;
    for(Entry<Character,Integer> en : entrySet) {
        // 获取键
        Character key = en.getKey() ;
        // 获取值
        Integer value = en.getValue() ;
        // a(5)b(4)c(3)d(2)e(1)
        // 拼接
        sb.append(key).append("(").append(value).append(")") ;
    }
    // 把sb转换成String
    String result = sb.toString() ;
    // 输出
    System.out.println(result);
}

01.构造函数和成员变量
02.put插入函数源码
03.get获取函数源码
04.如何保证有序性

好消息

博客笔记大汇总【16年3月到至今】，包括Java基础及深入知识点，Android技术博客，Python学习笔记等等，还包括平时开发中遇到的bug汇总，当然也在工作之余收集了大量的面试题，长期更新维护并且修正，持续完善……开源的文件是markdown格式的！同时也开源了生活博客，从12年起，积累共计N篇[近100万字，陆续搬到网上]，转载请注明出处，谢谢！
链接地址：https://github.com/yangchong211/YCBlogs
如果觉得好，可以star一下，谢谢！当然也欢迎提出建议，万事起于忽微，量变引起质变！

02.put函数源码

如果存在的话，old value被替换；如果不存在的话，则新添一个节点，然后对做红黑树的平衡操作。

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

03.get获取函数源码

get函数则相对来说比较简单，以log(n)的复杂度进行get。

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) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0)
            p = p.left;
        else if (cmp > 0)
            p = p.right;
        else
            return p;
    }
    return null;
}
public V get(Object key) {
    Entry<K,V> p = getEntry(key);
    return (p==null ? null : p.value);
}

04.如何保证有序性

TreeMap是如何保证其迭代输出是有序的呢？

其实从宏观上来讲，就相当于树的中序遍历(LDR)。我们先看一下迭代输出的步骤

for(Entry<Integer, String> entry : tmap.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

for语句会做如下转换为：

for(Iterator<Map.Entry<String, String>> it = tmap.entrySet().iterator() ; tmap.hasNext(); ) {
    Entry<Integer, String> entry = it.next();
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

在it.next()的调用中会使用nextEntry调用successor这个是过的后继的重点。

然后看一下successor函数

static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.right != null) {
        // 有右子树的节点，后继节点就是右子树的“最左节点”
        // 因为“最左子树”是右子树的最小节点
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        // 如果右子树为空，则寻找当前节点所在左子树的第一个祖先节点
        // 因为左子树找完了，根据LDR该D了
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        // 保证左子树
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

怎么理解这个successor呢？只要记住，这个是中序遍历就好了，L-D-R。具体细节如下：
- a. 空节点，没有后继
- b. 有右子树的节点，后继就是右子树的“最左节点”
- c. 无右子树的节点，后继就是该节点所在左子树的第一个祖先节点
a.好理解，不过b, c，有点像绕口令啊，没关系，上图举个例子就懂了！
- 有右子树的节点，节点的下一个节点，肯定在右子树中，而右子树中“最左”的那个节点则是右树中最小的一个，那么当然是右子树的“最左节点”，就好像下图所示：
- image
- 无右子树的节点，先找到这个节点所在的左子树(右图)，那么这个节点所在的左子树的父节点(绿色节点)，就是下一个节点。
- image