TreeMap源码学习

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

这是看过的第一个jdk源码（从立下目标以来）：TreeMap。说实话断断续续的看了有好几天了，我觉得我犯了一个错误，就像一开始说的那样，我打算完完全全看懂TreeMap关于红黑树的实现方式，后来我想了想，相对于花费这个对我的收益并不是特别大，而且看的过程中也有很多困惑，虽然我知道它每一步在做什么，但是我还不知道为什么要这么做，经过权衡，我决定先暂时放下TreeMap中关于对红黑树具体的实现，暂且记下有这回事。

一、简单理解

最近也在看数据结构和算法，对红黑树也有了大致的理解，TreeMap是对红黑树的Java实现完美实现版本。本篇不打算讨论TreeMap是怎么实现红黑树的。

1.1 使用Entry做为基本单元

首先在红黑树中既要保存数据，还要保存数据所处的位置，自然而然就想到用一个对象来包装存储的数据，TreeMap中是用一个静态最终类Entry来实现这个功能的，而这个类是实现自Map的Entry接口：

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;

    }

    public K getKey() {

        return key;

    }

    public V getValue() {

        return value;

    }

    public V setValue(V value) {

        V oldValue = this.value;

        this.value = value;

        return oldValue;

    }

    public boolean equals(Object o) {

        if (!(o instanceof Map.Entry))

            return false;

        Map.Entry<?,?> e = (Map.Entry<?,?>)o;

        return valEquals(key,e.getKey()) && valEquals(value,e.getValue());

    }

    public int hashCode() {

        int keyHash = (key==null ? 0 : key.hashCode());

        int valueHash = (value==null ? 0 : value.hashCode());

        return keyHash ^ valueHash;

    }

    public String toString() {

        return key + "=" + value;

    }

}

可以看到每一个除了包含自己数据的key和value值，同样有左、右、父节点的变量，并包括一个默认的黑色字段，这样，一个红黑树节点的所有信息就包含进去了，通过不断扩充节点的left、right和parent来描述整个树。

另外在equals中为了比较两个值是否相等还新建了一个比较方法：

static final boolean valEquals(Object o1, Object o2) {

    return (o1==null ? o2==null : o1.equals(o2));

}

这个比较方法避免了上层对null值的判断，其实在Objects里面已经有了，不过Objects出现的晚，所以说常用的工具方法就应该集中起来，不然每个类都写一遍可不是我心目中的jdk。

1.2 对transient的疑惑

我对transient还是有基本的了解的，当序列化对象的时候，被transient标记的字段就不会被序列化，因此我看到如下代码时很惊讶：

private transient Entry<K,V> root;

private transient int size = 0;

我认为根节点和容量是两个很重要的属性，序列化时为什么要去除呢，去除后会有错误的，为了验证我的想法我写了个测试代码：

TreeMap<Integer, Integer> map=new TreeMap<>();

map.put(1, 1);

map.put(2, 1);

ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("a.txt"));

oos.writeObject(map);

oos.flush();

oos.close();

ObjectInputStream ois = new ObjectInputStream(new FileInputStream("a.txt"));

TreeMap<Integer, Integer> mapClone = (TreeMap<Integer, Integer>) ois.readObject();

ois.close();

mapClone.put(3, 1);

System.out.println(mapClone);

并在反序列化对象put新数据的时候，打断点进去看，发现root居然不是null，而size也不是0，也是真实容量2，我晕了，超出了我的理解。经过测试和查找没有解决问题，在这留个坑，希望有人能帮到我。

1.3 对吞异常的反感

之前我写过一篇博客，是讲解异常的，可以去看一下：Java异常体系简析。所以我对把异常捕获而不做任何处理非常反感，因此看到以下代码，觉得非常不适：

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

    comparator = m.comparator();

    try {

        buildFromSorted(m.size(), m.entrySet().iterator(), null, null);

    } catch (java.io.IOException cannotHappen) {

    } catch (ClassNotFoundException cannotHappen) {

    }

}

什么叫做cannotHappen，不可能发生那异常还有必要存在吗，我还是认为应该抛一个虚拟机异常。不理解的可以去看我上面说的那篇博客。

1.4 遍历时防止另外线程的修改

TreeMap不是一个线程安全的类，当你在遍历一个TreeMap的时候，如果有另外一个线程修改了TreeMap，会立即抛异常，是通过一个变量来实现的：

private transient int modCount = 0;

每次修改都会让这个数加一，然后遍历时每次都会判断这个数是否发生变化：

@Override

public void forEach(BiConsumer<? super K, ? super V> action) {

    Objects.requireNonNull(action);

    int expectedModCount = modCount;

    for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) {

        action.accept(e.key, e.value);

        if (expectedModCount != modCount) {

            throw new ConcurrentModificationException();

        }

    }

}

这个可以在一定程度上防止遍历时被修改，只是被动防御，但是真要想达到随意的增删改查还是要使用ConcurrentSkipListMap。

1.5 创建时没有值的做法

当我们需要遍历集合的时候，有一种做法是先获取entrySet，然后遍历entrySet的Entry并获取key和value，在看到下面获取entrySet的代码时：

public Set<Map.Entry<K,V>> entrySet() {

    EntrySet es = entrySet;

    return (es != null) ? es : (entrySet = new EntrySet());

}

产生了疑惑，当获取时若为null就去创建一个new EntrySet()，而它的构造方法就是一个空的？？？，也就是说返回的确实是空的一个EntrySet，但是使用它的时候确实也有值：

TreeMap<Integer,Integer> map=new TreeMap<>();

map.put(1, 1);

Set<Entry<Integer, Integer>> set = map.entrySet();

System.out.println(set);

我在map.entrySet()这一行，debug进去一步一步看，确实是没有值，找了好一阵子，后来在debug这System.out.println(set)的时候才发现玄机。

简单来说，当你获得entrySet的时候确实是没有值的，但是它内部持有一个TreeMap的一个遍历器，而在真正使用的时候才去遍历关联的TreeMap，感觉和jdk1.5的Stream一样，因此方法的注释也都说明是一个view。而TreeMap中大量应用了这种方式，我觉得其他集合应该也是这么实现的。

这就给我们一种编程思路，不是说所有数据在获取的时候都需要给它准备好，等他真正使用的时候再给也不晚。

1.6 对常用方法的封装

TreeMap值有一些这样的方法：

private static <K,V> boolean colorOf(Entry<K,V> p) {

    return (p == null ? BLACK : p.color);

}

private static <K,V> Entry<K,V> parentOf(Entry<K,V> p) {

    return (p == null ? null: p.parent);

}

private static <K,V> void setColor(Entry<K,V> p, boolean c) {

    if (p != null)

        p.color = c;

}

private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {

    return (p == null) ? null: p.left;

}

private static <K,V> Entry<K,V> rightOf(Entry<K,V> p) {

    return (p == null) ? null: p.right;

}