2023-01-14  阅读(247)
原文作者: HelloWorld_EE 原文地址:https://blog.csdn.net/u010412719/category_6159934_2.html

TreeSet源码分析

功能:将Set中的元素按照一定的规则进行排序存储。

在其源码的内部实现中(如下),可以看到TreeSet时借助了TreeMap来实现的。

        public TreeSet() {
            this(new TreeMap<E,Object>());
        }
    
        TreeSet(NavigableMap<E,Object> m) {
            this.m = m;
        }

TreeSet.add方法

        public boolean add(E e) {
                //    private static final Object PRESENT = new Object();
            return m.put(e, PRESENT)==null;
        }

从add方法中可以看到直接将e其作为key,value = new Object() 保存在了TreeMap中。

下面来看一下TreeMap类中put方法的内部实现哈

        public TreeMap() {
            comparator = null;
        }

TreeMap.put(key,value)的实现思想比较简单:

1)就是实现了一个二叉排序树:要么是空树,要么满足以下条件:若左子树不空,则左子树所有结点的值均小于根结点的值,若右子树不空,右子树所有结点的值均大于根结点的值;左子树和右子树也是一颗二叉排序树。

2)具体为:从root节点开始遍历,利用比较器comparator来比较node.key与key的大小来确定此key应该存放的位置。注意:comparator可能为null,如果为null,则使用key的natural ordering(自然顺序),例如:没有指定comparator的String 类型key 的结果就是字典排序。

           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);
                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);
                } 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);
            }
            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;
        }

TreeSet for-each方法的原理

经常我们会这里来遍历已经排好序的TreeSet

            for (String key : treeSet) {
               //...
            }

那么,里面是如何来实现从最小的元素开始依次开始取元素的呢?

简单来说:由于存储是使用的二叉树排序的思想,因此对二叉树进行中序遍历即可得到有序的结果集。

从源码来分析,具体这就要看TreeMap中的keySet()方法的内部实现了

        public Set<K> keySet() {
            return navigableKeySet();
        }
    
        public NavigableSet<K> navigableKeySet() {
            KeySet<K> nks = navigableKeySet;
            return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this));
        }

这里的KeySet这个类就是关键了。

        static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
            private final NavigableMap<E, ?> m;
            KeySet(NavigableMap<E,?> map) { m = map; }
    
            public Iterator<E> iterator() {
                if (m instanceof TreeMap)
                    return ((TreeMap<E,?>)m).keyIterator();
                else
                    return ((TreeMap.NavigableSubMap<E,?>)m).keyIterator();
            }
        //...省略了不需要关注的代码    
        }

从上面KeySet的iterator的实现中可以看到,通过如下的方法得到了类型为KeyIterator的迭代器。

            Iterator<K> keyIterator() {
                return new KeyIterator(getFirstEntry());
            }
    
            /**
             * Returns the first Entry in the TreeMap (according to the TreeMap's
             * key-sort function).  Returns null if the TreeMap is empty.
             */
            final Entry<K,V> getFirstEntry() {
                Entry<K,V> p = root;
                if (p != null)
                    while (p.left != null)
                        p = p.left;
                return p;
            }

getFirstEntry函数的功能:找到排序结果中最小的那个元素。

下面主要看下 KeyIterator 这个类

这个类的next方法就是用来获取TreeSet中的下一个排好序的元素的。

具体实现思路为:由于上面讲解的put方法中我们知道是根据“左根右”的思想来存储的[最小值,中间值,最大值],因此这里的获取最小值的思路也是如此。

         final class KeyIterator extends PrivateEntryIterator<K> {
            KeyIterator(Entry<K,V> first) {
                super(first);
            }
            public K next() {
                return nextEntry().key;
            }
        }
    
            final Entry<K,V> nextEntry() {
                Entry<K,V> e = next;
                if (e == null)
                    throw new NoSuchElementException();
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
                next = successor(e);
                lastReturned = e;
                return e;
            }                  
    
        /**
         * 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) {//判断t节点的右边还有没有元素,如果有取出最小的。
                Entry<K,V> p = t.right;
                while (p.left != null)
                    p = p.left;
                return p;
            } else {//如果此时t的右边没有元素可遍历了,则遍历t的父节点的父节点
                Entry<K,V> p = t.parent;
                Entry<K,V> ch = t;
                while (p != null && ch == p.right) {
                    ch = p;
                    p = p.parent;
                }
                return p;
            }
        }

小结

比较简单哈,就是根据顺序存储,然后按照一定的顺序取出。

阅读全文
  • 点赞