(43) 剖析TreeMap / 计算机程序的思维逻辑

40节介绍了HashMap,我们提到,HashMap有一个重要局限,键值对之间没有特定的顺序,我们还提到,Map接口有另一个重要的实现类TreeMap,在TreeMap中,键值对之间按键有序,TreeMap的实现基础是排序二叉树,上节我们介绍了排序二叉树的基本概念和算法,本节我们来详细讨论TreeMap。

除了Map接口,因为有序,TreeMap还实现了更多接口和方法,下面,我们先来看TreeMap的用法,然后探讨其内部实现。

基本用法

构造方法

TreeMap有两个基本构造方法:

public TreeMap()
public TreeMap(Comparator<? super K> comparator)

第一个为默认构造方法,如果使用默认构造方法,要求Map中的键实现Comparabe接口,TreeMap内部进行各种比较时会调用键的Comparable接口中的compareTo方法。

第二个接受一个比较器对象comparator,如果comparator不为null,在TreeMap内部进行比较时会调用这个comparator的compare方法,而不再调用键的compareTo方法,也不再要求键实现Comparable接口。

应该用哪一个呢?第一个更为简单,但要求键实现Comparable接口,且期望的排序和键的比较结果是一致的,第二个更为灵活,不要求键实现Comparable接口,比较器可以用灵活复杂的方式进行实现。

需要强调的是,TreeMap是按键而不是按值有序,无论哪一种,都是对键而非值进行比较。

除了这两个基本构造方法,TreeMap还有如下构造方法:

public TreeMap(Map<? extends K, ? extends V> m)

public TreeMap(SortedMap<K, ? extends V> m) 

关于SortedMap接口,它扩展了Map接口,表示有序的Map,它有一个comparator()方法,返回其比较器,待会我们会进一步介绍。

这两个构造方法都是接受一个已有的Map,将其所有键值对添加到当前TreeMap中来,区别在于,第一个构造方法中,比较器会设为null,而第二个,比较器会设为和参数SortedMap中的一样。

接下来,我们来看一些简单的使用TreeMap的例子。

基本例子

代码为:

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()+" ");
}

创建了一个TreeMap,但只是当做Map使用,不过迭代时,其输出却是按键排序的,输出为:

T=tree a=abstract b=basic c=call 

T排在最前面,是因为大写字母都小于小写字母。如果希望忽略大小写呢?可以传递一个比较器,String类有一个静态成员CASE_INSENSITIVE_ORDER,它就是一个忽略大小写的Comparator对象,替换第一行代码为:

Map<String, String> map = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);

输出就会变为:

a=abstract b=basic c=call T=tree

正常排序是从小到大,如果希望逆序呢?可以传递一个不同的Comparator对象,第一行代码可以替换为:

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),两个对象翻过来,自然就是逆序了,Collections类有一个静态方法reverseOrder()可以返回一个逆序比较器,也就是说,上面代码也可以替换为:

Map<String, String> map = new TreeMap<>(Collections.reverseOrder());

如果希望逆序且忽略大小写呢?第一行可以替换为:

Map<String, String> map  = new TreeMap<>(
        Collections.reverseOrder(String.CASE_INSENSITIVE_ORDER));

需要说明的是,TreeMap使用键的比较结果对键进行排重,即使键实际上不同,但只要比较结果相同,它们就会被认为相同,键只会保存一份。比如,如下代码:

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"和"t",但因为比较器忽略大小写,所以只会有一个,输出会是:

T=try

键为第一次put时的,这里即"T",而值为最后一次put时的,这里即"try"。

日期例子

我们再来看一个例子,键为字符串形式的日期,值为一个统计数字,希望按照日期输出,代码为:

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.println(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。

怎么解决呢?可以使用一个自定义的比较器,将字符串转换为日期,按日期进行比较,第一行代码可以改为:

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

基本用法小结

以上就是TreeMap的基本用法,与HashMap相比:

  • 相同的是,它们都实现了Map接口,都可以按Map进行操作。
  • 不同的是,迭代时,TreeMap按键有序,为了实现有序,它要求:要么键实现Comparable接口,要么创建TreeMap时传递一个Comparator对象。

不过,由于TreeMap按键有序,它还支持更多接口和方法,具体来说,它还实现了SortedMap和NavigableMap接口,而NavigableMap接口扩展了SortedMap,我们来看一下这两个接口。

高级用法

SortedMap接口

SortedMap接口的定义为:

public interface SortedMap<K,V> extends Map<K,V> {
    Comparator<? super K> comparator();
    SortedMap<K,V> subMap(K fromKey, K toKey);
    SortedMap<K,V> headMap(K toKey);
    SortedMap<K,V> tailMap(K fromKey);
    K firstKey();
    K lastKey();
}

firstKey返回第一个键,而lastKey返回最后一个键。

headMap/tailMap/subMap都返回一个视图,视图中包括一部分键值对,它们的区别在于键的取值范围:

  • headMap:为小于toKey的所有键
  • tailMap:为大于等于fromKey的所有键
  • subMap:为大于等于fromKey且小于toKey的所有键。

NavigableMap接口

NavigableMap扩展了SortedMap,主要增加了一些查找邻近键的方法,比如:

Map.Entry<K,V> floorEntry(K key);
Map.Entry<K,V> lowerEntry(K key);
Map.Entry<K,V> ceilingEntry(K key);
Map.Entry<K,V> higherEntry(K key);

参数key对应的键不一定存在,但这些方法可能都有返回值,它们都返回一个邻近键值对,它们的区别在于,这个邻近键与参数key的关系。

  • floorEntry:邻近键是小于等于key的键中最大的
  • lowerEntry:邻近键是严格小于key的键中最大的
  • ceilingEntry:邻近键是大于等于key的键中最小的
  • higherEntry:邻近键是严格大于key的键中最小的

如果没有对应的邻近键,返回值为null。这些方法也都有对应的只返回键的方法:

K floorKey(K key);
K lowerKey(K key);
K ceilingKey(K key);
K higherKey(K key);

相比SortedMap中的方法headMap/tailMap/subMap,NavigableMap也增加了一些方法,以更为明确的方式指定返回值中是否包含边界值,如:

NavigableMap<K,V> headMap(K toKey, boolean inclusive);
NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);
NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
                             K toKey,   boolean toInclusive);

相比SortedMap中对头尾键的基本操作,NavigableMap增加了如下方法:

Map.Entry<K,V> firstEntry();
Map.Entry<K,V> lastEntry();
Map.Entry<K,V> pollFirstEntry();
Map.Entry<K,V> pollLastEntry();

firstEntry返回第一个键值对,lastEntry返回最后一个。pollFirstEntry删除并返回第一个键值对,pollLastEntry删除并返回最后一个。

此外,NavigableMap有如下方法,可以方便的逆序访问:

NavigableMap<K,V> descendingMap();
NavigableSet<K> descendingKeySet();

示例代码

我们看一段简单的示例代码,逻辑比较简单,就不解释了,主要是增强直观感受,其中输出用注释说明了:

NavigableMap<String, String> map  = new TreeMap<>();
map.put("a", "abstract");
map.put("f", "final");
map.put("c", "call");

//输出:a=abstract
System.out.println(map.firstEntry()); 

//输出:f=final
System.out.println(map.lastEntry()); 

//输出:c=call
System.out.println(map.floorEntry("d")); 

//输出:f=final
System.out.println(map.ceilingEntry("d"));

//输出:{c=call, a=abstract}
System.out.println(map.descendingMap()
        .subMap("d", false, "a", true));

了解了TreeMap的用法,接下来,我们来看TreeMap的实现原理。

基本实现原理

TreeMap内部是用红黑树实现的,红黑树是一种大致平衡的排序二叉树,上节我们介绍了排序二叉树的基本概念和算法,本节我们主要看TreeMap的一些代码实现,先来看TreeMap的内部组成。

内部组成

TreeMap内部主要有如下成员:

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的一个内部类,其内部成员和构造方法为:

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;

    /**
     * Make a new cell with given key, value, and parent, and with
     * {@code null} child links, and BLACK color.
     */
    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是用红黑树实现的,每个节点都有一个颜色,非黑即红。

了解了TreeMap的内部组成,我们来看一些主要方法的实现代码。

保存键值对

put方法的代码稍微有点长,我们分段来看,先看第一段,添加第一个节点的情况:

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

当添加第一个节点时,root为null,执行的就是这段代码,主要就是新建一个节点,设置root指向它,size设置为1,modCount++的含义与之前几节介绍的类似,用于迭代过程中检测结构性变化。

令人费解的是compare调用,compare(key, key);,key与key比,有什么意义呢?我们看compare方法的代码:
final int compare(Object k1, Object k2) {
    return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
        : comparator.compare((K)k1, (K)k2);
}

其实,这里的目的不是为了比较,而是为了检查key的类型和null,如果类型不匹配或为null,compare方法会抛出异常。

如果不是第一次添加,会执行后面的代码,添加的关键步骤是寻找父节点,找父节点根据是否设置了comparator分为两种情况,我们先来看设置了的情况,代码为:

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

寻找是一个从根节点开始循环的过程,在循环中,cmp保存比较结果,t指向当前比较节点,parent为t的父节点,循环结束后parent就是要找的父节点。

t一开始指向根节点,从根节点开始比较键,如果小于根节点,就将t设为左孩子,与左孩子比较,大于就与右孩子比较,就这样一直比,直到t为null或比较结果为0。如果比较结果为0,表示已经有这个键了,设置值,然后返回。如果t为null,则当退出循环时,parent就指向待插入节点的父节点。

我们再来看没有设置comparator的情况,代码为:

else {
    if (key == null)
        throw new NullPointerException();
    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);
}

基本逻辑是一样的,当退出循环时parent指向父节点,只是,如果没有设置comparator,则假设key一定实现了Comparable接口,使用Comparable接口的compareTo方法进行比较。

找到父节点后,就是新建一个节点,根据新的键与父节点键的比较结果,插入作为左孩子或右孩子,并增加size和modCount,代码如下:

Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
    parent.left = e;
else
    parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;

代码大部分都容易理解,不过,里面有一行重要调用fixAfterInsertion(e);,它就是在调整树的结构,使之符合红黑树的约束,保持大致平衡,其代码我们就不介绍了。

稍微总结一下,其基本思路就是,循环比较找到父节点,并插入作为其左孩子或右孩子,然后调整保持树的大致平衡。

根据键获取值

代码为:

public V get(Object key) {
    Entry<K,V> p = getEntry(key);
    return (p==null ? null : p.value);
}

就是根据key找对应节点p,找到节点后获取值p.value,来看getEntry的代码:

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

如果comparator不为空,调用单独的方法getEntryUsingComparator,否则,假定key实现了Comparable接口,使用接口的compareTo方法进行比较,找的逻辑也很简单,从根开始找,小于往左边找,大于往右边找,直到找到为止,如果没找到,返回null。getEntryUsingComparator方法的逻辑是类似,就不赘述了。

查看是否包含某个值

TreeMap可以高效的按键进行查找,但如果要根据值进行查找,则需要遍历,我们来看代码:

public boolean containsValue(Object value) {
    for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
        if (valEquals(value, e.value))
            return true;
    return false;
}

主体就是一个循环遍历,getFirstEntry方法返回第一个节点,successor方法返回给定节点的后继节点,valEquals就是比较值,从第一个节点开始,逐个进行比较,直到找到为止,如果循环结束也没找到则返回false。

getFirstEntry的代码为:

final Entry<K,V> getFirstEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.left != null)
            p = p.left;
    return p;
}

代码很简单,第一个节点就是最左边的节点。

上节我们介绍过找后继的算法,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 {
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

上节后继算法所述,有两种情况:

  • 如果有右孩子(t.right!=null),则后继为右子树中最小的节点。
  • 如果没有右孩子,后继为某祖先节点,从当前节点往上找,如果它是父节点的右孩子,则继续找父节点,直到它不是右孩子或父节点为空,第一个非右孩子节点的父亲节点就是后继节点,如果父节点为空,则后继为null。

代码与算法是对应的,就不再赘述了,下面重复一下上节的一个后继图(绿色箭头表示后继)以方便对照:

根据键删除键值对

删除的代码为:

public V remove(Object key) {
    Entry<K,V> p = getEntry(key);
    if (p == null)
        return null;

    V oldValue = p.value;
    deleteEntry(p);
    return oldValue;
}

根据key找到节点,调用deleteEntry删除节点,然后返回原来的值。

上节介绍过节点删除的算法,节点有三种情况:

  1. 叶子节点:这个容易处理,直接修改父节点对应引用置null即可。
  2. 只有一个孩子:就是在父亲节点和孩子节点直接建立链接。
  3. 有两个孩子:先找到后继,找到后,替换当前节点的内容为后继节点,然后再删除后继节点,因为这个后继节点一定没有左孩子,所以就将两个孩子的情况转换为了前面两种情况。

deleteEntry的具体代码也稍微有点长,我们分段来看:

private void deleteEntry(Entry<K,V> p) {
    modCount++;
    size--;

    // If strictly internal, copy successor's element to p and then make p
    // point to successor.
    if (p.left != null && p.right != null) {
        Entry<K,V> s = successor(p);
        p.key = s.key;
        p.value = s.value;
        p = s;
    } // p has 2 children

这里处理的就是两个孩子的情况,s为后继,当前节点p的key和value设置为了s的key和value,然后将待删节点p指向了s,这样就转换为了一个孩子或叶子节点的情况。

再往下看一个孩子情况的代码:

// Start fixup at replacement node, if it exists.
Entry<K,V> replacement = (p.left != null ? p.left : p.right);

if (replacement != null) {
    // Link replacement to parent
    replacement.parent = p.parent;
    if (p.parent == null)
        root = replacement;
    else if (p == p.parent.left)
        p.parent.left  = replacement;
    else
        p.parent.right = replacement;

    // Null out links so they are OK to use by fixAfterDeletion.
    p.left = p.right = p.parent = null;

    // Fix replacement
    if (p.color == BLACK)
        fixAfterDeletion(replacement);
} else if (p.parent == null) { // return if we are the only node.

p为待删节点,replacement为要替换p的孩子节点,主体代码就是在p的父节点p.parent和replacement之间建立链接,以替换p.parent和p原来的链接,如果p.parent为null,则修改root以指向新的根。fixAfterDeletion重新平衡树。

最后来看叶子节点的情况:

} else if (p.parent == null) { // return if we are the only node.
    root = null;
} else { //  No children. Use self as phantom replacement and unlink.
    if (p.color == BLACK)
        fixAfterDeletion(p);

    if (p.parent != null) {
        if (p == p.parent.left)
            p.parent.left = null;
        else if (p == p.parent.right)
            p.parent.right = null;
        p.parent = null;
    }
}

再具体分为两种情况,一种是删除最后一个节点,修改root为null,否则就是根据待删节点是父节点的左孩子还是右孩子,相应的设置孩子节点为null。

实现原理小结

以上就是TreeMap的基本实现原理,与上节介绍的排序二叉树的基本概念和算法是一致的,只是TreeMap用了红黑树。

TreeMap特点分析

与HashMap相比,TreeMap同样实现了Map接口,但内部使用红黑树实现,红黑树是统计效率比较高的大致平衡的排序二叉树,这决定了它有如下特点:

  • 按键有序,TreeMap同样实现了SortedMap和NavigableMap接口,可以方便的根据键的顺序进行查找,如第一个、最后一个、某一范围的键、邻近键等。
  • 为了按键有序,TreeMap要求键实现Comparable接口或通过构造方法提供一个Comparator对象。
  • 根据键保存、查找、删除的效率比较高,为O(h),h为树的高度,在树平衡的情况下,h为log2(N),N为节点数。

应该用HashMap还是TreeMap呢?不要求排序,优先考虑HashMap,要求排序,考虑TreeMap。

小结

本节介绍了TreeMap的用法和实现原理,在用法方面,它实现了Map接口,但按键有序,同样实现了SortedMap和NavigableMap接口,在内部实现上,它使用红黑树,整体效率比较高。

HashMap有对应的TreeMap,HashSet也有对应的TreeSet,下节,我们来看TreeSet。

原文发布于微信公众号 - 老马说编程(laoma_shuo)

原文发表时间:2016-10-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏互扯程序

Java集合深度解析之ArrayList

KS Knowledge Sharing 知识分享 现在是资源共享的时代,同样也是知识分享的时代,如果你觉得本文能学到知识,请把知识与别人分享。 转自:...

2106
来自专栏Android研究院

数据结构-线性表(顺序表与链表的基本知识 以及ArrayList 源码分析)

比如:美女和野兽,抽象的事物表示美女:头发长 前凸后翘。。。 可以表示为一个数据单元,野兽也是一个数据单元。

2201
来自专栏恰同学骚年

剑指Offer面试题:22.二叉搜索树的后序遍历序列

  在后序遍历得到的序列中,最后一个数字是树的根结点的值。数组中前面的数字可以分为两部分:第一部分是左子树结点的值,它们都比根结点的值小;第二部分是右子树结点的...

882
来自专栏与神兽党一起成长

说一说java.util.Arrays.ArrayList

java.util.Arrays.ArrayList(下文:Arrays.ArrayList)是java.util.Arrays的私有静态内部类,他实现的接口,...

1113
来自专栏Java帮帮-微信公众号-技术文章全总结

14(02)正则表达式,Pattern,Mactcher,Math,BigInteger,BigDeximal,System等

5:BigInteger(理解) (1)针对大整数的运算 (2)构造方法 A:BigInteger(String s) package cn.itcas...

3677
来自专栏有趣的Python

算法与数据结构(五)二叉搜索树

二叉搜索树 (Binary Search Tree) 核心是解决问题。高效解决问题。 查找问题 Searching Problem: 查找问题是计算机中非常重...

3146
来自专栏向治洪

数据结构之线性表

基本概念 线性表(List):由零个或多个数据元素组成的有限序列。 特征: 1.线性表是一个序列。 2.0个元素构成的线性表是空表。 3.线性表中的第一个元素无...

2049
来自专栏Java爬坑系列

【Java入门提高篇】Day28 Java容器类详解(十)LinkedHashMap详解

  今天来介绍一下容器类中的另一个哈希表———》LinkedHashMap。这是HashMap的关门弟子,直接继承了HashMap的衣钵,所以拥有HashMap...

892
来自专栏有趣的Python

7-玩转数据结构-集合与映射

上一章我们详细的介绍了二分搜索树的底层实现。这章我们介绍两个高层的数据结构,集合和映射。这种高层的数据结构,更像是我们定义好了使用接口规则,但是具体的底层实现可...

2571
来自专栏LanceToBigData

Java集合源码分析(一)ArrayList

前言   在前面的学习集合中只是介绍了集合的相关用法,我们想要更深入的去了解集合那就要通过我们去分析它的源码来了解它。希望对集合有一个更进一步的理解!   既然...

2496

扫码关注云+社区

领取腾讯云代金券