美文网首页
Java1.8-TreeMap源码解析

Java1.8-TreeMap源码解析

作者: 骑着乌龟去看海 | 来源:发表于2018-01-14 13:06 被阅读35次

    概述

      从API文档上我们可以知道,TreeMap是基于红黑树(Red-Black tree)来实现的,该数据结构最重要的特点就是可排序。默认情况下根据key的自然顺序进行排序,不过我们也可以自定义排序的顺序。
      至于红黑树的相关实现,就先不讲了,由于有些复杂,并且本人对红黑树还没有完成吃透,但红黑树的性质大家起码还是要知道的。

    继承关系
    public class TreeMap<K,V>
        extends AbstractMap<K,V>
        implements NavigableMap<K,V>, Cloneable, java.io.Serializable
    
    // NavigableMap接口继承了SortedMap
    public interface NavigableMap<K,V> extends SortedMap<K,V> {
    

      TreeMap实现了NavigableMap接口,而通过查看NavigableMap则是继承了SortedMap接口。由此我们可以知道,TreeMap排序的功能是基于NavigableMap也就是SortedMap的。

    NavigableMap,这个接口翻译过来可以理解为导航相关,该接口提供了许多个导航相关的方法,比如lowerKey,ceilingKey,higherKey等,同样,TreeMap实现该接口后,除了实现这些方法,也自定义类了一些导航相关的方法,大家可自行根据API进行查看。

    而这些排序相关的操作,基本上都离不开JDK排序相关的两个接口:Comparator和Comparable。

    属性
    /**
     * 比较器
     */
    private final Comparator<? super K> comparator;
    
    /**
     * 红黑树的红黑节点
     */
    private transient Entry<K,V> root;
    
    /**
     * 容量大小
     */
    private transient int size = 0;
    
    /**
     * 结构性修改
     */
    private transient int modCount = 0;
    
    /**
     * 红黑树节点类型
     */
    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;
    }
    
    // 红黑树节点-红颜色
    private static final boolean RED   = false;
    // 红黑树节点-黑颜色
    private static final boolean BLACK = true;
    
    构造方法
    /**
     * 默认构造器,使用默认排序机制
     */
    public TreeMap() {
        comparator = null;
    }
    /**
     * 自定义比较器的构造方法
     */
    public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }
    
    /**
     * 将Map构造为TreeMap
     */
    public TreeMap(Map<? extends K, ? extends V> m) {
        comparator = null;
        putAll(m);
    }
    /**
     * 构造SortedMap对象为TreeMap,并使用SortedMap的比较器
     */
    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) {
        }
    }
    
    

    方法

    put方法
    /**
     * 红黑树的put操作大体上分为两步:构建二叉排序树,平衡二叉排序树
     * 构建的时候,如果用户自定义了比较器,则会按照用户定义的规则来,否则将按照默认的比较规则来插入数据;
     */
    public V put(K key, V value) {
        // 二叉树当前节点
        Entry<K,V> t = root;
        // 如果二叉树为null,直接插入
        if (t == null) {
            compare(key, key); // type (and possibly null) check
    
            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        // 使用cmp来表示排序返回的结果
        int cmp;
        // 父节点
        Entry<K,V> parent;
        // 比较器
        Comparator<? super K> cpr = comparator;
        // 如果比较器不为空,按照用户指定比较器进行循环比较,确定元素插入位置
        if (cpr != null) {
            do {
                parent = t;
                // 对key进行比较
                cmp = cpr.compare(key, t.key);
                // 比较结果小于0,表示新增节点的key小于当前节点的key,则以当前节点的左子节点作为新的当前节点
                if (cmp < 0)
                    t = t.left;
                // 比较结果大于0,表示新增节点的key大于当前节点的key,则以当前节点的右子节点作为新的当前节点
                else if (cmp > 0)
                    t = t.right;
                // 比较结果等于0,说明key相等,覆盖旧值,返回新值
                else
                    return t.setValue(value);
            } while (t != null);
        }
        // 如果比较器为null
        else {
            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);
            } while (t != null);
        }
        // 新增节点设为parent的子节点
        Entry<K,V> e = new Entry<>(key, value, parent);
        // 如果新增节点的key小于parent的key,则当做左子节点
        if (cmp < 0)
            parent.left = e;
        // 否则,右子节点
        else
            parent.right = e;
        // 插入完成,对二叉树进行平衡操作
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }
    
    get方法
    /**
     * get方法相对简单些,只是对二叉树的比较遍历而已
     */
    final Entry<K,V> getEntry(Object key) {
        // 如果比较器不为空,则按照自定义规则遍历二叉树
        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;
    }
    
    remove方法
    /**
     * 这里删除操作其实很微妙,并不是直接删除,而是用被删除节点的后继节点来代替被删掉的节点,然后修复被删除节点的结构来进行操作的
     */
    private void deleteEntry(Entry<K,V> p) {
        modCount++;
        size--;
    
        // p节点为要删除的节点,如果p节点的左右子节点都不为空
        if (p.left != null && p.right != null) {
            // 找到p节点的后继节点,这里不是直接删除p节点,而是将p的后继节点来代替要删除的节点,然后再进行修复操作
            Entry<K,V> s = successor(p);
            p.key = s.key;
            p.value = s.value;
            p = s;
        } // p has 2 children
    
        // 开始修复操作
        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.
            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;
            }
        }
    }
    
    /**
     * 获取后继节点,其实这是一个类似中序遍历的方式
     */
    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;
        }
    }
    

    获取后继节点可参考:
    Java TreeMap工作原理及实现

      如果要深入理解TreeMap的红黑树实现,可以搜索《史上最简单清晰的红黑树讲解》系列博客。

    文章参考自:
    TreeMap源码分析(jdk1.8)

    相关文章

      网友评论

          本文标题:Java1.8-TreeMap源码解析

          本文链接:https://www.haomeiwen.com/subject/egrkoxtx.html