0%

Java Map 和 Set（四）：剖析 TreeMap

发表于 更新于 分类于
本文字数： 4.2k 阅读时长 ≈ 4 分钟

1. TreeMap 基本用法之构造方法

  • TreeMap 有两个构造方法
    • public TreeMap()
      • 默认构造方法，要求 Map 中的键实现 Comparable 接口
      • TreeMap 内部进行各种比较时会调用键的 Comparable 接口中的 compareTo() 方法
    • public TreeMap(Comparator<? super K> comparator)
      • 接受一个比较器对象 comparator
      • 如果 comparator 不为 null，在 TreeMap 内部进行比较时会调用这个 comparator 的 compare() 方法，而不再调用键的 compareTo() 方法，也不再要求键实现 Comparable 接口
  • TreeMap 是按键而不是按值有序，无论哪一种，都是对键而非值进行比较

2. 下面代码的输出结果是

1
2
3
4
5
6
7
8
9
Map<String, String> map = new TreeMap();
map.put("a", "abstract");
map.put("c", "call");
map.put("b", "basic");
map.put("T", "tree");

for(Entry<String, String> kv : map.entrySet()) {
    System.out.print(kv.getKey() + "=" + kv.getValue() + " ");
}
  • 结果：T=tree a=abstract b=basic c=call
  • 分析：创建了一个 TreeMap，但只是当作 Map 使用，不过迭代时，输出是按键有序的。T 排在最前面，是因为大写字母的 ASCII 码都小于小写字母

3. 接上题，如果希望忽略大小写呢

  • 可以传递一个比较器，String 类有一个静态成员 CASE_INSENSITIVE_ORDER，它就是一个忽略大小写的 Comparator 对象
  • 替换第一行代码为：Map<String, String> map = new TreeMap<> (String.CASE_INSENSITIVE_ORDER);。输出为：a=abstract b=basic c=call T=tree

4. 接上题，正常排序是从小到大，如果希望逆序呢

  • 可以传递一个自定义的 Comparator 对象，替换第一行代码为

    1
    2
    3
    4
    5
    6
    Map<String, String> map = new TreeMap<> (new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            return o2.compareTo(o1);
        }    
    };
    • 结果：c=call b=basic a=abstract T=tree
    • 分析：因为正常排序中，compare() 方法内是 o1.compareTo(o2)，两个对象翻过来，自然就是逆序了

  • Collection 类有一个静态方法 reverseOrder() 可以返回一个逆序比较器，所以，上面代码也可以替换为：Map<String, Sttring> map = new TreeMap<> (Collections.reverseOrder());

5. 接上题，如果希望逆序且忽略大小写呢

  • 组合 Collection 的逆序和 String 的忽略大小写
  • 第一行可以替换为：Map<String, String> map = new TreeMap<> (Colleciton.reverseOrder(String.CASE_INSENSITIVE_ORDER));

6. 下面代码的输出结果是

1
2
3
4
5
6
Map<String, String> map = new TreeMap<> (String.CASE_INSENSITIVE_ORDER);
map.put("T", "tree");
map.put("t", "try");
for(Entry<String, String> kv : map.entrySet()) {
    System.out.print(kv.getKey() + "=" + kv.getValue() + "  ");
}
  • 结果：T=try
  • 分析：看上去有两个不同的键 T 和 t，但因为比较器忽略大小写，所以只会有一个。键为第一次 put() 时的值，即 T，而值为最后一次 put() 时覆盖的值，这里即 try

7. 下面代码的输出结果是

1
2
3
4
5
6
7
Map<String, Integer> map = new TreeMap<> ();
map.put("2016-7-3", 100);
map.put("2016-7-10", 120);
map.put("2016-8-1", 90);
for(Entry<String, Integer> kv : map.entrySet()) {
    System.out.print(kv.getKey() + ", " + kv.getValue() + " ");
}
  • 结果：2016-7-10,120 2016-7-3, 100 2016-8-1, 90
  • 分析：7 月 10 号排在了 7 月 3 号 前面，与期望的不符。这是因为，它们是按照字符串比较的。按字符串，2016-7-10 就是小于 2016-7-3，因为第一个不同之处 1 小于 3

8. 接上题，怎样解决使与期望相符

  • 可以使用一个自定义的比较器，将字符串转换为日期，按日期进行比较

  • Demo

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    Map<String, Integer> map = new TreeMap<> (new Comparator<String>() {
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd");
        @Override
        public int compare(String o1, String o2) {
            try {
                return sdf.parse(o1).compareTo(sdf.parse(o2));
            } catch (ParseException e) {
                e.printStackTrace();
                return 0;
            }
        }
    });

    //输出结果
    2016-7-3, 100
    2016-7-10, 120
    2016-8-1, 90

9. TreeMap 实现原理是怎样的

  • TreeMap 内部是用红黑树实现的，红黑树是一种大致平衡的排序二叉树

  • TreeMap 内部主要有如下成员

    1
    2
    3
    private final Comparator<? super K> comparator;
    private transient Entry<K, V> root = null;
    private transient int size = 0;

    • comparator 就是比较器，在构造方法中传递，如果没传，就是 null

    • size 为当前键值对个数

    • root 指向树的根节点，从根节点可以访问到每个节点，节点的类型是 Entry

    • Entry 是 TreeMap 的一个内部类，其内部成员和构造方法为

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      static final class Entry<K, V> implements Map.Entry<K, V> {
          K key;
          V value;
          Entry<K, V> left = null;
          Entry<K, V> right = null;
          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;
          }
      }

  • 每个节点除了键（key）和值（value）之外，还有三个引用，分别指向其左孩子（left）、右孩子（right）和父节点（parent)

    • 对于根节点，父节点为 null；对于叶子节点，孩子节点都为 null
    • 还有一个成员 color 表示颜色，TreeMap 是用红黑树实现的，每个节点都有一个颜色，非黑即红

  • 保存键值对 put(K key, V value) 的基本思路：循环比较找到父节点，并插入作为其左孩子或右孩子，然后调整保持树的大致平衡

  • 根据键获取值 get(Object key) 的基本思路：从根开始找，小于往左边找，大于往右边找，直到找到为止，如果没找到，返回 null

  • 查看是否包含某个值 containsValue(Object value) 的基本思路：主体就是一个循环遍历，从第一个节点开始，逐个进行比较，直到找到为止，如果循环结束也没找到则返回 false

  • 根据键删除键值对 remove(Object key) 的基本思路：与排序二叉树删除节点类似，分三种情况

10. 怎样理解红黑树

  • 定义：红黑树是一种大致平衡的排序二叉树

  • 特征：红黑树除了符合排序二叉树左小右大的基本特征外，还具有下列附加特征

    • 根节点是黑色
    • 其他节点是红色或黑色
    • 每个叶子节点都是黑色的空节点
    • 每个红色节点的两个孩子节点都是黑色（从每个叶子节点到根节点的所有路径上不能有两个连续的红色节点）
    • 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点

  • 举例

    红黑树

  • 调整

    • 变色：红变黑、黑变红
    • 旋转
      • 左旋转：逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子
      • 右旋转：顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子

  • 参考

11. TreeMap 的特点

  • 按键有序，TreeMap 同样实现了 SortedMap 和 NavigableMap 接口，可以方便地根据键的顺序进行查找，如第一个、最后一个、某一范围的键、临近键等
  • 为了按键有序，TreeMap 要求键实现 Comparable 接口或通过构造方法提供一个 Comparator 比较器对象
  • 根据键保存、查找、删除的效率比较高，为 O(h)，h 为树的高度，在树平衡的情况下，h = log2(N)，N 为节点数
  • 不要求排序，优先考虑 HashMap；要求排序，考虑 TreeMap
-------------------- 本文结束感谢您的阅读 --------------------