Java集合-TreeMap源码解析-JDK1.8

忘是亡心i 2024-04-18 20:26 87阅读 0赞

◆

TreeMap简介

◆

推荐查看此篇文章之前首先查看[ HashMap源码分析][HashMap] 效果更佳哦

TreeMap在jdk 1.8中使用用的是红黑树的结构来进行存储的，一个典型的红黑树就如下图所示：

![640?wx\_fmt=png][640_wx_fmt_png]

而这个结构在代码中表现是这样的：

/**	
         * 红黑树节点	
         */	
        static final class Entry<K,V> implements Map.Entry<K,V> {	
            K key;	
            V value;	
            TreeMap.Entry<K,V> left;	
            TreeMap.Entry<K,V> right;	
            TreeMap.Entry<K,V> parent;	
            boolean color = BLACK;	
            	
            Entry(K key, V value, TreeMap.Entry<K,V> parent) {	
                this.key = key;	
                this.value = value;	
                this.parent = parent;	
            }	
        }

◆

TreeMap的属性

◆

TreeMap的一些基础属性：

// 比较器对象	
        private final Comparator<? super K> comparator;	
        //根节点对象	
        private transient TreeMap.Entry<K,V> root;	
        //集合的大小	
        private transient int size = 0;	
        //结构被修改的次数	
        private transient int modCount = 0;

◆

TreeMap的构造方法

◆

/**	
         * 使用默认比较器	
         * key的类型是什么	
         * 就采用该类型的compareTo方法来比较大小	
         * 例如key为String类型，就会用String类的compareTo方法比对大小	
         */	
        public TreeMap() {	
            comparator = null;	
        }	
    
    	
        /**	
         * 指定比较器	
         */	
        public TreeMap(Comparator<? super K> comparator) {	
            this.comparator = comparator;	
        }	
    
    	
        /**	
         * 添加集合	
         */	
        public TreeMap(Map<? extends K, ? extends V> m) {	
            comparator = null;	
            putAll(m);	
        }	
    
    	
        /**	
         * 将m转换为TreeMap，使用m的比较器	
         */	
        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) {	
            }	
        }

◆

HashMap的添加方法

◆

/**	
         * 添加方法	
         */	
        public V put(K key, V value) {	
            TreeMap.Entry<K,V> t = root;	
            //如果跟节点为空，把此节点置为跟节点	
            if (t == null) {	
                compare(key, key); // type (and possibly null) check	
    
    	
                root = new TreeMap.Entry<>(key, value, null);	
                size = 1;	
                modCount++;	
                return null;	
            }	
            int cmp;	
            TreeMap.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);	
            }	
            // 如果比较器对象为空，使用默认的比较机制	
            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);	
            }	
            // 根据key找到父节点后新建一个节点	
            TreeMap.Entry<K,V> e = new TreeMap.Entry<>(key, value, parent);	
            // 根据比较的结果来确定放在左子树还是右子树	
            if (cmp < 0)	
                parent.left = e;	
            else	
                parent.right = e;	
            // 插入完成，红黑树的结构会被破坏，执行红黑树的恢复操作	
            fixAfterInsertion(e);	
            //集合大小增加	
            size++;	
            //修改次数增加	
            modCount++;	
            return null;	
        }

◆

TreeMap的查找

◆

/**	
         * 根据key获取	
         */	
        public V get(Object key) {	
            TreeMap.Entry<K,V> p = getEntry(key);	
            return (p==null ? null : p.value);	
        }	
        /**	
         * 根据key获取Entry对象	
         */	
        final TreeMap.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;	
            TreeMap.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;	
        }

◆

TreeMap的删除

◆

/**	
         * 删除节点	
         */	
        public V remove(Object key) {	
            //查找元素是否存在	
            TreeMap.Entry<K,V> p = getEntry(key);	
            if (p == null)	
                return null;	
            V oldValue = p.value;	
            //调用具体的删除方法	
            deleteEntry(p);	
            return oldValue;	
        }	
         /**	
         * 具体的删除方法	
         */	
        private void deleteEntry(TreeMap.Entry<K,V> p) {	
            modCount++;	
            size--;	
    
    	
            // 如果待删除节点有两个子节点	
            if (p.left != null && p.right != null) {	
                TreeMap.Entry<K,V> s = successor(p);	
                p.key = s.key;	
                p.value = s.value;	
                p = s;	
            } // p has 2 children	
    
    	
            // Start fixup at replacement node, if it exists.	
            TreeMap.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 { //  没有子节点	
                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;	
                }	
            }	
        }

鉴于篇幅有限，本篇文章仅列出上方部分代码，TreeMap完整源码解析请 点击下方“阅读原文”查看！！！

![640?wx\_fmt=gif][640_wx_fmt_gif]

不得不看

1.[SpringCloud系列博客汇总][SpringCloud]

2.[Java多线程面试必备基础知识汇总][Java]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

万水千山总是情，点个 “在看” 行不行！！！

![640?wx\_fmt=png][640_wx_fmt_png 1]

[HashMap]: http://mp.weixin.qq.com/s?__biz=MzU5MDgzOTYzMw==&mid=2247484058&idx=1&sn=03b310383954e5c2fcdf6532fd47ca6d&chksm=fe3968a4c94ee1b2b0ded04688df352f03611007c24735e1e27c6f5d95012ef01d167a42ce79&scene=21#wechat_redirect
[640_wx_fmt_png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/cae554996bc74eae93818214f3d9630a.png
[640_wx_fmt_gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/e31a822b25764f7f9a73d655626c755f.gif
[SpringCloud]: http://mp.weixin.qq.com/s?__biz=MzU5MDgzOTYzMw==&mid=2247484030&idx=1&sn=7ad29239aca876e29155f5b1439281bb&chksm=fe396840c94ee156adfcd44c63a3b5c1cf93805cf592ad7d45bc5222c349ba6f552b553a5c09&scene=21#wechat_redirect
[Java]: http://mp.weixin.qq.com/s?__biz=MzU5MDgzOTYzMw==&mid=2247484030&idx=2&sn=ddf120fcbfc45238e64662fd183156de&chksm=fe396840c94ee156a80b744033ac34d67e331545193d2f9d4f2943995aa4412a53fec023d599&scene=21#wechat_redirect
[640_wx_fmt_jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/3d87114e0a7140b18ce4b2b8f0e59372.png
[640_wx_fmt_png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/090972ecb76f4504890469712378c6a9.png