1、TreeSet-底层数据结构

  1. 1、TreeSet-底层数据结构：
  2.     1-1、TreeSet这个类实现了Set集合，实际为一个TreeMap的实例。
  3.     1-2、TreeSet，它是基于TreeMap实现的，TreeSet底层使用TreeMap来保存所有元素，因此TreeSet的实现比较简单，相关TreeSet的操作，基本上都是直接调用底层TreeMap的相关方法来完成。
  4.     1-3、TreeSet属性字段有：
  5.         /**
  6.          * The backing map.
  7.          * NavigableMap对象
  8.          */
  9.         private transient NavigableMap<E,Object> m;
  10.          //定义一个虚拟的Object对象作为TreeMap的value，将此对象定义为static final。
  11.         //PRESENT是键-值对中的值
  12.         private static final Object PRESENT = new Object();

2、TreeSet-构造函数

  1. 1、TreeSet底层是通过HashSet实现的。
  3. 2、构造方法-源代码：
  4.     /**
  5.      * 将TreeMap赋值给 "NavigableMap对象m"
  6.      */
  7.     TreeSet(NavigableMap<E,Object> m) {
  8.         this.m = m;
  9.     }
  11.     // 不带参数的构造函数。创建一个空的TreeMap
  12.     public TreeSet() {
  13.         this(new TreeMap<E,Object>());
  14.     }
  16.      // 带比较器的构造函数。
  17.     public TreeSet(Comparator<? super E> comparator) {
  18.         this(new TreeMap<>(comparator));
  19.     }
  21.     // 创建TreeSet，并将集合c中的全部元素都添加到TreeSet中
  22.     public TreeSet(Collection<? extends E> c) {
  23.         this();
  24.         addAll(c);
  25.     }
  27.     // 创建TreeSet，并将s中的全部元素都添加到TreeSet中
  28.     public TreeSet(SortedSet<E> s) {
  29.         this(s.comparator());
  30.         addAll(s);
  31.     }

3、TreeSet-添加元素

  1. 1、添加元素：.put()方法
  3. 2、源代码：
  4.     public V put(K key, V value) {
  5.       //定义一个t来保存根元素
  6.         Entry<K,V> t = root;
  7.         //如果t==null，表明是一个空链表
  8.         if (t == null) {
  9.         //如果根节点为null，将传入的键值对构造成根节点（根节点没有父节点，所以传入的父节点为null）
  10.             root = new Entry<K,V>(key, value, null);
  11.             //设置该集合的size为1
  12.             size = 1;
  13.             //修改此时+1
  14.             modCount++;
  15.             return null;
  16.         }
  17.         // 记录比较结果
  18.         int cmp;
  19.         Entry<K,V> parent;
  20.         // 分割比较器和可比较接口的处理
  21.         Comparator<? super K> cpr = comparator;
  22.         // 有比较器的处理，即采用定制排序
  23.         if (cpr != null) {
  24.             // do while实现在root为根节点移动寻找传入键值对需要插入的位置
  25.             /**
  26.                 实现"排序二叉树"的关键算法。
  27.                 1.每当程序希望添加新节点时，总是从树的根节点开始比较，即将根节点当成当前节点。
  28.                     1.1.如果新增节点大于当前节点且当前节点的右子节点存在，则以右子节点作为当前节点。并继续循环
  29.                     1.2.如果新增节点小于当前节点且当前节点的左子节点存在，则以左子节点作为当前节点。并继续循环
  30.                     1.3.如果新增节点等于当前节点，则新增节点覆盖当前节点，并结束循环。
  31.             */
  32.             do {
  33.                 //使用parent上次循环后的t所引用的Entry
  34.                 // 记录将要被掺入新的键值对将要节点(即新节点的父节点)
  35.                 parent = t;
  36.                 // 使用比较器比较父节点和插入键值对的key值的大小
  37.                 cmp = cpr.compare(key, t.key);
  38.                 // 插入的key较大
  39.                 if (cmp < 0)
  40.                     t = t.left;
  41.                 // 插入的key较小
  42.                 else if (cmp > 0)
  43.                     t = t.right;
  44.                 // key值相等，替换并返回t节点的value(put方法结束)
  45.                 else
  46.                     return t.setValue(value);
  47.             } while (t != null);
  48.         }
  49.         // 没有比较器的处理
  50.         else {
  51.             // key为null抛出NullPointerException异常
  52.             if (key == null)
  53.                 throw new NullPointerException();
  54.             Comparable<? super K> k = (Comparable<? super K>) key;
  55.             // 与if中的do while类似，只是比较的方式不同
  56.             do {
  57.                 parent = t;
  58.                 cmp = k.compareTo(t.key);
  59.                 if (cmp < 0)
  60.                     t = t.left;
  61.                 else if (cmp > 0)
  62.                     t = t.right;
  63.                 else
  64.                     return t.setValue(value);
  65.             } while (t != null);
  66.         }
  67.         // 没有找到key相同的节点才会有下面的操作
  68.         // 根据传入的键值对和找到的“父节点”创建新节点
  69.         Entry<K,V> e = new Entry<K,V>(key, value, parent);
  70.         // 根据最后一次的判断结果确认新节点是“父节点”的左孩子还是又孩子
  71.         if (cmp < 0)
  72.             parent.left = e;
  73.         else
  74.             parent.right = e;
  75.         // 对加入新节点的树进行调整
  76.         fixAfterInsertion(e);
  77.         // 记录size和modCount
  78.         size++;
  79.         modCount++;
  80.         // 因为是插入新节点，所以返回的是null
  81.         return null;
  82.     }

4、TreeSet-获取元素

  1. 1、获取元素：.get()方法
  3. 2、源代码：
  4.     public V get(Object key) {
  5.      //根据key取出Entry
  6.      Entry<K,V> p = getEntry(key);
  7.      //取出Entry所包含的value
  8.      return (p==null ? null : p.value);
  9.      }
  11.     /**
  12.         利用排序二叉树的特性来搜索目标Entry: 从二叉数的根节点开始，如果被搜索节点大于当前节点，程序向"右子树"搜索，如果小于，则向"左子树"搜索。如果相等则说明找到了指定节点。
  13.     */
  14.     final Entry<K,V> getEntry(Object key) {
  15.         // 如果有比较器，返回getEntryUsingComparator(Object key)的结果
  16.         if (comparator != null)
  17.             return getEntryUsingComparator(key);
  18.         // 查找的key为null，抛出NullPointerException
  19.         if (key == null)
  20.             throw new NullPointerException();
  21.         // 如果没有比较器，而是实现了可比较接口
  22.         //将key强制转换为Comparable接口
  23.         Comparable<? super K> k = (Comparable<? super K>) key;
  24.         // 获取根节点
  25.         Entry<K,V> p = root;
  26.         // 从根节点开始对树进行遍历查找节点
  27.         while (p != null) {
  28.             // 把key和当前节点的key进行比较
  29.             int cmp = k.compareTo(p.key);
  30.             // key小于当前节点的key
  31.             if (cmp < 0)
  32.                 // p “移动”到左节点上
  33.                 p = p.left;
  34.             // key大于当前节点的key
  35.             else if (cmp > 0)
  36.             // p “移动”到右节点上
  37.         p = p.right;
  38.             // key值相等则当前节点就是要找的节点
  39.             else
  40.                 // 返回找到的节点
  41.                 return p;
  42.             }
  43.         // 没找到则返回null
  44.         return null;
  45.     }
  47.     //在采用定制排序的方式下，TreeMap采用getEntryUsingComparator(key)方法来根据key获取Entry。
  48.     final Entry<K,V> getEntryUsingComparator(Object key) {
  49.         K k = (K) key;
  50.         // 获取比较器
  51.         Comparator<? super K> cpr = comparator;
  52.         // 其实在调用此方法的get(Object key)中已经对比较器为null的情况进行判断，这里是防御性的判断
  53.         if (cpr != null) {
  54.             // 获取根节点
  55.                 Entry<K,V> p = root;
  56.                 // 遍历树
  57.                 while (p != null) {
  58.                     // 获取key和当前节点的key的比较结果
  59.                     int cmp = cpr.compare(k, p.key);
  60.                     // 查找的key值较小
  61.                     if (cmp < 0)
  62.                         // p“移动”到左孩子
  63.                         p = p.left;
  64.                     // 查找的key值较大
  65.                     else if (cmp > 0)
  66.                         // p“移动”到右节点
  67.                         p = p.right;
  68.                     // key值相等
  69.                     else
  70.                         // 返回找到的节点
  71.                         return p;
  72.                 }
  73.         }
  74.         // 没找到key值对应的节点，返回null
  75.             return null;
  76.         }

5、TreeSet-其他方法-简介

  1. public class TreeSet<E> extends AbstractSet<E>
  2.     implements NavigableSet<E>, Cloneable, java.io.Serializable
  3. {
  4.     // NavigableMap对象
  5.     private transient NavigableMap<E,Object> m;
  7.     // TreeSet是通过TreeMap实现的，
  8.     // PRESENT是键-值对中的值。
  9.     private static final Object PRESENT = new Object();
  11.     // 不带参数的构造函数。创建一个空的TreeMap
  12.     public TreeSet() {
  13.         this(new TreeMap<E,Object>());
  14.     }
  16.     // 将TreeMap赋值给 "NavigableMap对象m"
  17.     TreeSet(NavigableMap<E,Object> m) {
  18.         this.m = m;
  19.     }
  21.     // 带比较器的构造函数。
  22.     public TreeSet(Comparator<? super E> comparator) {
  23.         this(new TreeMap<E,Object>(comparator));
  24.     }
  26.     // 创建TreeSet，并将集合c中的全部元素都添加到TreeSet中
  27.     public TreeSet(Collection<? extends E> c) {
  28.         this();
  29.         // 将集合c中的元素全部添加到TreeSet中
  30.         addAll(c);
  31.     }
  33.     // 创建TreeSet，并将s中的全部元素都添加到TreeSet中
  34.     public TreeSet(SortedSet<E> s) {
  35.         this(s.comparator());
  36.         addAll(s);
  37.     }
  39.     // 返回TreeSet的顺序排列的迭代器。
  40.     // 因为TreeSet时TreeMap实现的，所以这里实际上时返回TreeMap的“键集”对应的迭代器
  41.     public Iterator<E> iterator() {
  42.         return m.navigableKeySet().iterator();
  43.     }
  45.     // 返回TreeSet的逆序排列的迭代器。
  46.     // 因为TreeSet时TreeMap实现的，所以这里实际上时返回TreeMap的“键集”对应的迭代器
  47.     public Iterator<E> descendingIterator() {
  48.         return m.descendingKeySet().iterator();
  49.     }
  51.     // 返回TreeSet的大小
  52.     public int size() {
  53.         return m.size();
  54.     }
  56.     // 返回TreeSet是否为空
  57.     public boolean isEmpty() {
  58.         return m.isEmpty();
  59.     }
  61.     // 返回TreeSet是否包含对象(o)
  62.     public boolean contains(Object o) {
  63.         return m.containsKey(o);
  64.     }
  66.     // 添加e到TreeSet中
  67.     public boolean add(E e) {
  68.         return m.put(e, PRESENT)==null;
  69.     }
  71.     // 删除TreeSet中的对象o
  72.     public boolean remove(Object o) {
  73.         return m.remove(o)==PRESENT;
  74.     }
  76.     // 清空TreeSet
  77.     public void clear() {
  78.         m.clear();
  79.     }
  81.     // 将集合c中的全部元素添加到TreeSet中
  82.     public  boolean addAll(Collection<? extends E> c) {
  83.         // Use linear-time version if applicable
  84.         if (m.size()==0 && c.size() > 0 &&
  85.             c instanceof SortedSet &&
  86.             m instanceof TreeMap) {
  87.             SortedSet<? extends E> set = (SortedSet<? extends E>) c;
  88.             TreeMap<E,Object> map = (TreeMap<E, Object>) m;
  89.             Comparator<? super E> cc = (Comparator<? super E>) set.comparator();
  90.             Comparator<? super E> mc = map.comparator();
  91.             if (cc==mc || (cc != null && cc.equals(mc))) {
  92.                 map.addAllForTreeSet(set, PRESENT);
  93.                 return true;
  94.             }
  95.         }
  96.         return super.addAll(c);
  97.     }
  99.     // 返回子Set，实际上是通过TreeMap的subMap()实现的。
  100.     public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
  101.                                   E toElement,   boolean toInclusive) {
  102.         return new TreeSet<E>(m.subMap(fromElement, fromInclusive,
  103.                                        toElement,   toInclusive));
  104.     }
  106.     // 返回Set的头部，范围是：从头部到toElement。
  107.     // inclusive是是否包含toElement的标志
  108.     public NavigableSet<E> headSet(E toElement, boolean inclusive) {
  109.         return new TreeSet<E>(m.headMap(toElement, inclusive));
  110.     }
  112.     // 返回Set的尾部，范围是：从fromElement到结尾。
  113.     // inclusive是是否包含fromElement的标志
  114.     public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
  115.         return new TreeSet<E>(m.tailMap(fromElement, inclusive));
  116.     }
  118.     // 返回子Set。范围是：从fromElement(包括)到toElement(不包括)。
  119.     public SortedSet<E> subSet(E fromElement, E toElement) {
  120.         return subSet(fromElement, true, toElement, false);
  121.     }
  123.     // 返回Set的头部，范围是：从头部到toElement(不包括)。
  124.     public SortedSet<E> headSet(E toElement) {
  125.         return headSet(toElement, false);
  126.     }
  128.     // 返回Set的尾部，范围是：从fromElement到结尾(不包括)。
  129.     public SortedSet<E> tailSet(E fromElement) {
  130.         return tailSet(fromElement, true);
  131.     }
  133.     // 返回Set的比较器
  134.     public Comparator<? super E> comparator() {
  135.         return m.comparator();
  136.     }
  138.     // 返回Set的第一个元素
  139.     public E first() {
  140.         return m.firstKey();
  141.     }
  143.     // 返回Set的最后一个元素
  144.     public E first() {
  145.     public E last() {
  146.         return m.lastKey();
  147.     }
  149.     // 返回Set中小于e的最大元素
  150.     public E lower(E e) {
  151.         return m.lowerKey(e);
  152.     }
  154.     // 返回Set中小于/等于e的最大元素
  155.     public E floor(E e) {
  156.         return m.floorKey(e);
  157.     }
  159.     // 返回Set中大于/等于e的最小元素
  160.     public E ceiling(E e) {
  161.         return m.ceilingKey(e);
  162.     }
  164.     // 返回Set中大于e的最小元素
  165.     public E higher(E e) {
  166.         return m.higherKey(e);
  167.     }
  169.     // 获取第一个元素，并将该元素从TreeMap中删除。
  170.     public E pollFirst() {
  171.         Map.Entry<E,?> e = m.pollFirstEntry();
  172.         return (e == null)? null : e.getKey();
  173.     }
  175.     // 获取最后一个元素，并将该元素从TreeMap中删除。
  176.     public E pollLast() {
  177.         Map.Entry<E,?> e = m.pollLastEntry();
  178.         return (e == null)? null : e.getKey();
  179.     }
  181.     // 克隆一个TreeSet，并返回Object对象
  182.     public Object clone() {
  183.         TreeSet<E> clone = null;
  184.         try {
  185.             clone = (TreeSet<E>) super.clone();
  186.         } catch (CloneNotSupportedException e) {
  187.             throw new InternalError();
  188.         }
  190.         clone.m = new TreeMap<E,Object>(m);
  191.         return clone;
  192.     }
  194.     // java.io.Serializable的写入函数
  195.     // 将TreeSet的“比较器、容量，所有的元素值”都写入到输出流中
  196.     private void writeObject(java.io.ObjectOutputStream s)
  197.         throws java.io.IOException {
  198.         s.defaultWriteObject();
  200.         // 写入比较器
  201.         s.writeObject(m.comparator());
  203.         // 写入容量
  204.         s.writeInt(m.size());
  206.         // 写入“TreeSet中的每一个元素”
  207.         for (Iterator i=m.keySet().iterator(); i.hasNext(); )
  208.             s.writeObject(i.next());
  209.     }
  211.     // java.io.Serializable的读取函数：根据写入方式读出
  212.     // 先将TreeSet的“比较器、容量、所有的元素值”依次读出
  213.     private void readObject(java.io.ObjectInputStream s)
  214.         throws java.io.IOException, ClassNotFoundException {
  215.         // Read in any hidden stuff
  216.         s.defaultReadObject();
  218.         // 从输入流中读取TreeSet的“比较器”
  219.         Comparator<? super E> c = (Comparator<? super E>) s.readObject();
  221.         TreeMap<E,Object> tm;
  222.         if (c==null)
  223.             tm = new TreeMap<E,Object>();
  224.         else
  225.             tm = new TreeMap<E,Object>(c);
  226.         m = tm;
  228.         // 从输入流中读取TreeSet的“容量”
  229.         int size = s.readInt();
  231.         // 从输入流中读取TreeSet的“全部元素”
  232.         tm.readTreeSet(size, s, PRESENT);
  233.     }
  235.     // TreeSet的序列版本号
  236.     private static final long serialVersionUID = -2479143000061671589L;
  237. }