Java TreeMap源码分析
7 minutes read (About 1051 words) 0 visits

Java TreeMap源码分析

前言

A Red-Black tree based {@link NavigableMap} implementation. The map is sorted according to the {@linkplain Comparable natural ordering} of its keys, or by a {@link Comparator} provided at map creation time, depending on which constructor is used.

This implementation provides guaranteed log(n) time cost for the {@code containsKey}, {@code get}, {@code put} and {@code remove} operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest’s Introduction to Algorithms.

上面是一段关于TreeMap的官方Javadoc描述，简单来说就是，TreeMap底层是基于红黑树，保持了key的大小有序性，因此查找等操作的时间复杂度为O(logn)；

在这篇文章中我主要分析Java中是如何利用红黑树实现TreeMap的，关于红黑树的详细原理介绍可以参考这篇文章《教你透彻了解红黑树》。

put方法

Associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the old value is replaced.

put函数如果存在相同的key，则会替换原来的旧值；

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
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); //设置root
        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
                return t.setValue(value); //如果存在相同的key，则直接替换旧值
        } while (t != null);
    }
    else { //否则使用Comparable（key得继承这个类）
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
        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); //如果存在相同的key，则直接替换旧值
        } 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;
}

put函数其实也比较好理解，跟平衡二叉树的逻辑差不多，难点在于进行红黑树变化；

get()方法

Returns the value to which the specified key is mapped, or {@code null} if this map contains no mapping for the key.

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
public V get(Object key) {
    Entry<K,V> p = getEntry(key);
    return (p==null ? null : p.value); //如果key不存在则返回null
}

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();
    @SuppressWarnings("unchecked")
    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;
}

迭代遍历

看一个Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @author Shuai Junlan[shuaijunlan@gmail.com].
 * @since Created in 1:41 PM 1/18/19.
 */
public class TreeMapTest {
    public static void main(String[] args) {
        TreeMap<Integer, String> treeMap = new TreeMap<>();
        treeMap.put(5, "green");
        treeMap.put(1, "red");
        treeMap.put(3, "yellow");
        treeMap.put(4, "white");
        treeMap.put(2, "black");
        for (Map.Entry<Integer, String> entry : treeMap.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

这个迭代遍历过程是一个有序的遍历，通过getFirstEntry()方法获取最小的子节点，每次调用next()方法时，它会调用successor(Entry<K,V> t)方法来获取下一个节点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
     * Returns the successor of the specified Entry, or null if no such.
     */
//该方法主要实现获取当前节点的下一个节点
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;
    }
}

实现逻辑如下：

  • 有右子树的节点，节点的下一个节点，肯定在右子树中，而右子树中“最左”的那个节点则是右子树中最小的一个，那么当然是右子树的“最左节点”，就好像下图所示：

  • 无右子树的节点，先找到这个节点所在的左子树(右图)，那么这个节点所在的左子树的父节点(绿色节点)，就是下一个节点，如下图所示：

REFERENCE

# ,
Java NIO核心组件：Selector
Java编程如何高效利用CPU缓存？

Comments

Follow

Tag Cloud

AQS Algorithm B+Tree CentOS DirectIO KVM LRU LeetCode Linux Micro Service MutliThread MyBatis3 MySQL Netty SPI Spring Spring Cloud TreeMap WebSystem cache cpu dubbo http java javassist log4j mmap nio zookeeper 网络配置 虚拟化

Links

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×