Java TreeMap

Java

有序哈希表

有序依靠key比较机制

底层是一个比较器和树的根节点

TreeMap.java
1
2
3
4
5
6
7
8
9
public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
    private final Comparator<? super K> comparator;
    private transient Entry<K,V> root;

    private transient int size = 0;
    private transient int modCount = 0;
    //...
}

SortedMap是有序接口
接口要求内含比较器，key有序存在最大最小，可根据key范围返回子视图，

SortedMap.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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();

    Set<K> keySet();
    Collection<V> values();
    Set<Map.Entry<K, V>> entrySet();
}

NavigableMap是SortedMap的子接口，更加丰富了功能

NavigableMap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public interface NavigableMap<K,V> extends SortedMap<K,V> {
    //小于
    Map.Entry<K,V> lowerEntry(K key);
    K lowerKey(K key);

    //小于等于
    Map.Entry<K,V> floorEntry(K key);
    K floorKey(K key);

    //大于等于
    Map.Entry<K,V> ceilingEntry(K key);
    K ceilingKey(K key);

    //大于
    Map.Entry<K,V> higherEntry(K key);
    K higherKey(K key);

    //首尾查询
    Map.Entry<K,V> firstEntry();
    Map.Entry<K,V> lastEntry();

    //首尾查询后移除
    Map.Entry<K,V> pollFirstEntry();
    Map.Entry<K,V> pollLastEntry();

    //反向顺序
    NavigableMap<K,V> descendingMap();

    NavigableSet<K> navigableKeySet();
    NavigableSet<K> descendingKeySet();

    //扩展可指定是否包含边界
    NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey,   boolean toInclusive);
    NavigableMap<K,V> headMap(K toKey, boolean inclusive);
    NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);

    //SortedMap接口相同方法
    SortedMap<K,V> subMap(K fromKey, K toKey);
    SortedMap<K,V> headMap(K toKey);
    SortedMap<K,V> tailMap(K fromKey);
}

比较器并不是必须的，可以无参构造
如果不提供比较器，那么key本身必须是可比较的，否则强转会报错

TreeMap.java
1
2
3
4
5
6
7
8
9
10
11
12
public TreeMap() {
    comparator = null;
}
public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

final int compare(Object k1, Object k2) {
    //无比较器传入时就会进行强转
    return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
        : comparator.compare((K)k1, (K)k2);
}

树是红黑树实现，树节点除了引用左右子树外，还引用父节点，默认是黑色

TreeMap.java
1
2
3
4
5
6
7
8
9
10
11
12
13
private static final boolean RED   = false;
private static final boolean BLACK = true;

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;

    //...
}

插入操作

TreeMap.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
public V put(K key, V value) {
    Entry<K,V> t = root;
    //空树，直接创建根节点
    if (t == null) {
        //验证确保可比较
        compare(key, key);

        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
                //key在树中已存在，替换掉value
                return t.setValue(value);
        } while (t != null);
    }
    else {
        //使用key自身比较，限定了key不能是null，并且可强转Comparable
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
        //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;
}

调整红黑树算法

TreeMap.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
private void fixAfterInsertion(Entry<K,V> x) {
    //新节点标红
    x.color = RED;

    //父节点也是红，两红相邻开始调整
    while (x != null && x != root && x.parent.color == RED) {
        //父节点位于左边
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            //取父节点右侧兄弟
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                //兄弟是红色，则进行颜色调整，父节点和兄弟都变黑，祖父变红
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                //跳至祖父节点开始判断
                x = parentOf(parentOf(x));
            } else {
                //兄弟是黑色，进行旋转调整
                //当前节点位于左侧，开始左旋父节点
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateLeft(x);
                }
                //当前节点位于右侧，父节点置黑，祖父置红
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                //开始右旋祖父节点
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            //和上面左右反向操作
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateRight(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    //保证根节点是黑
    root.color = BLACK;
}

版权声明

This site by Linest is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由Linest创作并维护的博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。

本文永久链接：http://linest.github.io/2018/04/01/java-treemap/