当前位置:天才代写 > tutorial > JAVA 教程 > Java荟萃进修(十七) TreeSet具体先容(源码理会)和利用示例

Java荟萃进修(十七) TreeSet具体先容(源码理会)和利用示例

2017-11-02 08:00 星期四 所属: JAVA 教程 浏览:46

副标题#e#

这一章,我们对TreeSet举办进修。
我们先对TreeSet有个整体认识,然后再进修它的源码,最后再通过实例来学会利用TreeSet。

第1部门 TreeSet先容

TreeSet简介

TreeSet 是一个有序的荟萃,它的浸染是提供有序的Set荟萃。它担任于AbstractSet抽象类,实现了NavigableSet<E>, Cloneable, java.io.Serializable接口。
TreeSet 担任于AbstractSet,所以它是一个Set荟萃,具有Set的属性和要领。
TreeSet 实现了NavigableSet接口,意味着它支持一系列的导航要领。好比查找与指定方针最匹配项。
TreeSet 实现了Cloneable接口,意味着它能被克隆。
TreeSet 实现了java.io.Serializable接口,意味着它支持序列化。

TreeSet是基于TreeMap实现的。TreeSet中的元素支持2种排序方法:自然排序 可能 按照建设TreeSet 时提供的 Comparator 举办排序。这取决于利用的结构要领。
TreeSet为根基操纵(add、remove 和 contains)提供受担保的 log(n) 时间开销。
别的,TreeSet长短同步的。 它的iterator 要领返回的迭代器是fail-fast的。

TreeSet的担任干系

java.lang.Object
        java.util.AbstractCollection<E>
              java.util.AbstractSet<E>
                    java.util.TreeSet<E>
     
public class TreeSet<E> extends AbstractSet<E>        
    implements NavigableSet<E>, Cloneable, java.io.Serializable{}

TreeSet与Collection干系如下图:

Java聚集学习(十七) TreeSet详细介绍(源码剖析)和操作示例

TreeSet的结构函数

// 默认结构函数。利用该结构函数,TreeSet中的元素凭据自然排序举办分列。
TreeSet()
     
// 建设的TreeSet包括collection
TreeSet(Collection<? extends E> collection)
     
// 指定TreeSet的较量器
TreeSet(Comparator<? super E> comparator)
     
// 建设的TreeSet包括set
TreeSet(SortedSet<E> set)

TreeSet的API

boolean                   add(E object)
boolean                   addAll(Collection<? extends E> collection)
void                      clear()
Object                    clone()
boolean                   contains(Object object)
E                         first()
boolean                   isEmpty()
E                         last()
E                         pollFirst()
E                         pollLast()
E                         lower(E e)
E                         floor(E e)
E                         ceiling(E e)
E                         higher(E e)
boolean                   remove(Object object)
int                       size()
Comparator<? super E>     comparator()
Iterator<E>               iterator()
Iterator<E>               descendingIterator()
SortedSet<E>              headSet(E end)
NavigableSet<E>           descendingSet()
NavigableSet<E>           headSet(E end, boolean endInclusive)
SortedSet<E>              subSet(E start, E end)
NavigableSet<E>           subSet(E start, boolean startInclusive, E end, boolean endInclusive)
NavigableSet<E>           tailSet(E start, boolean startInclusive)
SortedSet<E>              tailSet(E start)

说明:

(01) TreeSet是有序的Set荟萃,因此支持add、remove、get等要领。
(02) 和NavigableSet一样,TreeSet的导航要领大抵可以区分为两类,一类时提供元素项的导航要领,返回某个元素;另一类时提供荟萃的导航要领,返回某个荟萃。
lower、floor、ceiling 和 higher 别离返回小于、小于便是、大于便是、大于给定元素的元素,假如不存在这样的元素,则返回 null。

第2部门 TreeSet源码理会

为了更相识TreeSet的道理,下面临TreeSet源码代码作出阐明。

package java.util;
     
public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{
    // NavigableMap工具
    private transient NavigableMap<E,Object> m;
     
    // TreeSet是通过TreeMap实现的,
    // PRESENT是键-值对中的值。
    private static final Object PRESENT = new Object();
     
    // 不带参数的结构函数。建设一个空的TreeMap
    public TreeSet() {
        this(new TreeMap<E,Object>());
    }
     
    // 将TreeMap赋值给 "NavigableMap工具m"
    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }
     
    // 带较量器的结构函数。
    public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<E,Object>(comparator));
    }
     
    // 建设TreeSet,并将荟萃c中的全部元素都添加到TreeSet中
    public TreeSet(Collection<? extends E> c) {
        this();
        // 将荟萃c中的元素全部添加到TreeSet中
        addAll(c);
    }
     
    // 建设TreeSet,并将s中的全部元素都添加到TreeSet中
    public TreeSet(SortedSet<E> s) {
        this(s.comparator());
        addAll(s);
    }
     
    // 返回TreeSet的顺序分列的迭代器。
    // 因为TreeSet时TreeMap实现的,所以这里实际上时返回TreeMap的“键集”对应的迭代器
    public Iterator<E> iterator() {
        return m.navigableKeySet().iterator();
    }
     
    // 返回TreeSet的逆序分列的迭代器。
    // 因为TreeSet时TreeMap实现的,所以这里实际上时返回TreeMap的“键集”对应的迭代器
    public Iterator<E> descendingIterator() {
        return m.descendingKeySet().iterator();
    }
     
    // 返回TreeSet的巨细
    public int size() {
        return m.size();
    }
     
    // 返回TreeSet是否为空
    public boolean isEmpty() {
        return m.isEmpty();
    }
     
    // 返回TreeSet是否包括工具(o)
    public boolean contains(Object o) {
        return m.containsKey(o);
    }
     
    // 添加e到TreeSet中
    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }
     
    // 删除TreeSet中的工具o
    public boolean remove(Object o) {
        return m.remove(o)==PRESENT;
    }
     
    // 清空TreeSet
    public void clear() {
        m.clear();
    }
     
    // 将荟萃c中的全部元素添加到TreeSet中
    public  boolean addAll(Collection<? extends E> c) {
        // Use linear-time version if applicable
        if (m.size()==0 && c.size() > 0 &&
            c instanceof SortedSet &&
            m instanceof TreeMap) {
            SortedSet<? extends E> set = (SortedSet<? extends E>) c;
            TreeMap<E,Object> map = (TreeMap<E, Object>) m;
            Comparator<? super E> cc = (Comparator<? super E>) set.comparator();
            Comparator<? super E> mc = map.comparator();
            if (cc==mc || (cc != null && cc.equals(mc))) {
                map.addAllForTreeSet(set, PRESENT);
                return true;
            }
        }
        return super.addAll(c);
    }
     
    // 返回子Set,实际上是通过TreeMap的subMap()实现的。
    public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                                  E toElement,   boolean toInclusive) {
        return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
                                       toElement,   toInclusive));
    }
     
    // 返回Set的头部,范畴是:从新部到toElement。
    // inclusive是是否包括toElement的符号
    public NavigableSet<E> headSet(E toElement, boolean inclusive) {
        return new TreeSet<E>(m.headMap(toElement, inclusive));
    }
     
    // 返回Set的尾部,范畴是:从fromElement到末了。
    // inclusive是是否包括fromElement的符号
    public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
        return new TreeSet<E>(m.tailMap(fromElement, inclusive));
    }
     
    // 返回子Set。范畴是:从fromElement(包罗)到toElement(不包罗)。
    public SortedSet<E> subSet(E fromElement, E toElement) {
        return subSet(fromElement, true, toElement, false);
    }
     
    // 返回Set的头部,范畴是:从新部到toElement(不包罗)。
    public SortedSet<E> headSet(E toElement) {
        return headSet(toElement, false);
    }
     
    // 返回Set的尾部,范畴是:从fromElement到末了(不包罗)。
    public SortedSet<E> tailSet(E fromElement) {
        return tailSet(fromElement, true);
    }
     
    // 返回Set的较量器
    public Comparator<? super E> comparator() {
        return m.comparator();
    }
     
    // 返回Set的第一个元素
    public E first() {
        return m.firstKey();
    }
     
    // 返回Set的最后一个元素
    public E first() {
    public E last() {
        return m.lastKey();
    }
     
    // 返回Set中小于e的最大元素
    public E lower(E e) {
        return m.lowerKey(e);
    }
     
    // 返回Set中小于/便是e的最大元素
    public E floor(E e) {
        return m.floorKey(e);
    }
     
    // 返回Set中大于/便是e的最小元素
    public E ceiling(E e) {
        return m.ceilingKey(e);
    }
     
    // 返回Set中大于e的最小元素
    public E higher(E e) {
        return m.higherKey(e);
    }
     
    // 获取第一个元素,并将该元素从TreeMap中删除。
    public E pollFirst() {
        Map.Entry<E,?> e = m.pollFirstEntry();
        return (e == null)? null : e.getKey();
    }
     
    // 获取最后一个元素,并将该元素从TreeMap中删除。
    public E pollLast() {
        Map.Entry<E,?> e = m.pollLastEntry();
        return (e == null)? null : e.getKey();
    }
     
    // 克隆一个TreeSet,并返回Object工具
    public Object clone() {
        TreeSet<E> clone = null;
        try {
            clone = (TreeSet<E>) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError();
        }
     
        clone.m = new TreeMap<E,Object>(m);
        return clone;
    }
     
    // java.io.Serializable的写入函数
    // 将TreeSet的“较量器、容量,所有的元素值”都写入到输出流中
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        s.defaultWriteObject();
     
        // 写入较量器
        s.writeObject(m.comparator());
     
        // 写入容量
        s.writeInt(m.size());
     
        // 写入“TreeSet中的每一个元素”
        for (Iterator i=m.keySet().iterator(); i.hasNext(); )
            s.writeObject(i.next());
    }
     
    // java.io.Serializable的读取函数:按照写入方法读出
    // 先将TreeSet的“较量器、容量、所有的元素值”依次读出
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // Read in any hidden stuff
        s.defaultReadObject();
     
        // 从输入流中读取TreeSet的“较量器”
        Comparator<? super E> c = (Comparator<? super E>) s.readObject();
     
        TreeMap<E,Object> tm;
        if (c==null)
            tm = new TreeMap<E,Object>();
        else
            tm = new TreeMap<E,Object>(c);
        m = tm;
     
        // 从输入流中读取TreeSet的“容量”
        int size = s.readInt();
     
        // 从输入流中读取TreeSet的“全部元素”
        tm.readTreeSet(size, s, PRESENT);
    }
     
    // TreeSet的序列版本号
    private static final long serialVersionUID = -2479143000061671589L;
}

总结:


#p#副标题#e#

#p#分页标题#e#

(01) TreeSet实际上是TreeMap实现的。当我们结构TreeSet时;若利用不带参数的结构函数,则TreeSet的利用自然较量器;若用户需要利用自界说的较量器,则需要利用带较量器的参数。
(02) TreeSet长短线程安详的。
(03) TreeSet实现java.io.Serializable的方法。当写入到输出流时,依次写入“较量器、容量、全部元素”;当读出输入流时,再依次读取。

第3部门 TreeSet遍历方法

3.1 Iterator顺序遍历

for(Iterator iter = set.iterator(); iter.hasNext(); ) {
   iter.next();
}  

3.2 Iterator顺序遍历

// 假设set是TreeSet工具
for(Iterator iter = set.descendingIterator(); iter.hasNext(); ) {
   iter.next();
}

3.3 for-each遍历HashSet

#p#分页标题#e#

// 假设set是TreeSet工具,而且set中元素是String范例
String[] arr = (String[])set.toArray(new String[0]);
for (String str:arr)
   System.out.printf("for each : %s\n", str);

TreeSet遍历测试措施如下:

import java.util.*;
     
/**
 * @desc TreeSet的遍历措施
 *
 * @author skywang
 * @email [email protected]
 */
public class TreeSetIteratorTest {
     
    public static void main(String[] args) {
        TreeSet set = new TreeSet();
        set.add("aaa");
        set.add("aaa");
        set.add("bbb");
        set.add("eee");
        set.add("ddd");
        set.add("ccc");
     
        // 顺序遍历TreeSet
        ascIteratorThroughIterator(set) ;
        // 逆序遍历TreeSet
        descIteratorThroughIterator(set);
        // 通过for-each遍历TreeSet。不推荐!此要领需要先将Set转换为数组
        foreachTreeSet(set);
    }
     
    // 顺序遍历TreeSet
    public static void ascIteratorThroughIterator(TreeSet set) {
        System.out.print("\n ---- Ascend Iterator ----\n");
        for(Iterator iter = set.iterator(); iter.hasNext(); ) {
            System.out.printf("asc : %s\n", iter.next());
        }
    }
     
    // 逆序遍历TreeSet
    public static void descIteratorThroughIterator(TreeSet set) {
        System.out.printf("\n ---- Descend Iterator ----\n");
        for(Iterator iter = set.descendingIterator(); iter.hasNext(); )
            System.out.printf("desc : %s\n", (String)iter.next());
    }
     
    // 通过for-each遍历TreeSet。不推荐!此要领需要先将Set转换为数组
    private static void foreachTreeSet(TreeSet set) {
        System.out.printf("\n ---- For-each ----\n");
        String[] arr = (String[])set.toArray(new String[0]);
        for (String str:arr)
            System.out.printf("for each : %s\n", str);
    }
}

TreeSet不支持快速随机遍历,只能通过迭代器举办遍历。

查察本栏目

第4部门 TreeSet示例

下面通过实例进修如何利用TreeSet

import java.util.*;
     
/**
 * @desc TreeSet的API测试
 *
 * @author skywang
 * @email [email protected]
 */
public class TreeSetTest {
     
    public static void main(String[] args) {
        testTreeSetAPIs();
    }
         
    // 测试TreeSet的api
    public static void testTreeSetAPIs() {
        String val;
     
        // 新建TreeSet
        TreeSet tSet = new TreeSet();
        // 将元素添加到TreeSet中
        tSet.add("aaa");
        // Set中不答允反复元素,所以只会生存一个“aaa”
        tSet.add("aaa");
        tSet.add("bbb");
        tSet.add("eee");
        tSet.add("ddd");
        tSet.add("ccc");
        System.out.println("TreeSet:"+tSet);
     
        // 打印TreeSet的实际巨细
        System.out.printf("size : %d\n", tSet.size());
     
        // 导航要领
        // floor(小于、便是)
        System.out.printf("floor bbb: %s\n", tSet.floor("bbb"));
        // lower(小于)
        System.out.printf("lower bbb: %s\n", tSet.lower("bbb"));
        // ceiling(大于、便是)
        System.out.printf("ceiling bbb: %s\n", tSet.ceiling("bbb"));
        System.out.printf("ceiling eee: %s\n", tSet.ceiling("eee"));
        // ceiling(大于)
        System.out.printf("higher bbb: %s\n", tSet.higher("bbb"));
        // subSet()
        System.out.printf("subSet(aaa, true, ccc, true): %s\n", tSet.subSet("aaa", true, "ccc", true));
        System.out.printf("subSet(aaa, true, ccc, false): %s\n", tSet.subSet("aaa", true, "ccc", false));
        System.out.printf("subSet(aaa, false, ccc, true): %s\n", tSet.subSet("aaa", false, "ccc", true));
        System.out.printf("subSet(aaa, false, ccc, false): %s\n", tSet.subSet("aaa", false, "ccc", false));
        // headSet()
        System.out.printf("headSet(ccc, true): %s\n", tSet.headSet("ccc", true));
        System.out.printf("headSet(ccc, false): %s\n", tSet.headSet("ccc", false));
        // tailSet()
        System.out.printf("tailSet(ccc, true): %s\n", tSet.tailSet("ccc", true));
        System.out.printf("tailSet(ccc, false): %s\n", tSet.tailSet("ccc", false));
     
     
        // 删除“ccc”
        tSet.remove("ccc");
        // 将Set转换为数组
        String[] arr = (String[])tSet.toArray(new String[0]);
        for (String str:arr)
            System.out.printf("for each : %s\n", str);
     
        // 打印TreeSet
        System.out.printf("TreeSet:%s\n", tSet);
     
        // 遍历TreeSet
        for(Iterator iter = tSet.iterator(); iter.hasNext(); ) {
            System.out.printf("iter : %s\n", iter.next());
        }
     
        // 删除并返回第一个元素
        val = (String)tSet.pollFirst();
        System.out.printf("pollFirst=%s, set=%s\n", val, tSet);
     
        // 删除并返回最后一个元素
        val = (String)tSet.pollLast();
        System.out.printf("pollLast=%s, set=%s\n", val, tSet);
     
        // 清空HashSet
        tSet.clear();
     
        // 输出HashSet是否为空
        System.out.printf("%s\n", tSet.isEmpty()?"set is empty":"set is not empty");
    }
}

 

    关键字:


天才代写-代写联系方式