treeMap与treeSet

Bertha 。 2022-05-12 14:38 188阅读 0赞

为了理解 TreeMap 的底层实现，必须先介绍排序二叉树和红黑树这两种数据结构。其中红黑树又是一种特殊的排序二叉树。

##### 排序二叉树 #####

排序二叉树是一种特殊结构的二叉树，可以非常方便地对树中所有节点进行排序和检索。
    
    排序二叉树要么是一棵空二叉树，要么是具有下列性质的二叉树：
    
    若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
    若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
    它的左、右子树也分别为排序二叉树。

##### 红黑树 #####

红黑树是一种自平衡排序二叉树，树中每个节点的值，都大于或等于在它的左子树中的所有节点的值，并且小于或等于在它的右子树中的所有节点的值，这确保红黑树运行时可以快速地在树中查找和定位的所需节点。

##### treeMap与treeSet #####

TreeSet 底层实际使用的存储容器就是 TreeMap。
    HashSet 底层实际使用的存储容器就是 HashMap。

对于 TreeMap 而言，由于它底层采用一棵“红黑树”来保存集合中的 Entry，这意味这 TreeMap 添加元素、取出元素的性能都比 HashMap 低：当 TreeMap 添加元素时，需要通过循环找到新增 Entry 的插入位置，因此比较耗性能；当从 TreeMap 中取出元素时，需要通过循环才能找到合适的 Entry，也比较耗性能。但 TreeMap、TreeSet 比 HashMap、HashSet 的优势在于：TreeMap 中的所有 Entry 总是按 key 根据指定排序规则保持有序状态，TreeSet 中所有元素总是根据指定排序规则保持有序状态。例如对于如下程序而言：

public class TreeMapTest { 
        public static void main(String[] args) { 
            TreeMap<String , Double> map = 
                new TreeMap<String , Double>(); 
            map.put("ccc" , 89.0); 
            map.put("aaa" , 80.0); 
            map.put("zzz" , 80.0); 
            map.put("bbb" , 89.0); 
            System.out.println(map); 
        } 
     }

当程序执行 map.put(“ccc” , 89.0); 时，系统将直接把 “ccc”-89.0 这个 Entry 放入 Map 中，这个 Entry 就是该“红黑树”的根节点。接着程序执行 map.put(“aaa” , 80.0); 时，程序会将 “aaa”-80.0 作为新节点添加到已有的红黑树中。

以后每向 TreeMap 中放入一个 key-value 对，系统都需要将该 Entry 当成一个新节点，添加成已有红黑树中，通过这种方式就可保证 TreeMap 中所有 key 总是由小到大地排列。例如我们输出上面程序，将看到如下结果（所有 key 由小到大地排列）：\{aaa=80.0, bbb=89.0, ccc=89.0, zzz=80.0\}