学步园

Set和数学中的集合是同一个概念，就是没有重复元素的集合。

这篇文章主要论述了Set是如何实现"没有重复元素"（no duplicate elements）的，以及阐述了什么是“重复”（duplicate），是相同的地址空间？是equals的返回值为true？是compareTo的返回值为0 ？还是有相同的hashCode？本文还给出了在什么情况下使用什么样的Set的建议。

注：本文不涉及范型。

1、树形结构： 

public interface Set  extends Collection  {}
 public abstract class AbstractSet  extends AbstractCollection   implements Set {}
 public class CopyOnWriteArraySet  extends AbstractSet  implements Serializable{}
 public abstract class EnumSet   extends Enum  extends AbstractSet  implements Cloneable, Serializable{}
 public class HashSet  extends AbstractSet  implements Set , Cloneable, Serializable{}
 public final class JobStateReasons  extends HashSet<JobStateReason>implements PrintJobAttribute{}
 public class LinkedHashSet  extends HashSet  implements Set , Cloneable, Serializable{}
 public class TreeSet  extends AbstractSet  implements SortedSet , Cloneable, Serializable{}

   可以看出，可以实例化的类为：CopyOnWriteArraySet，HashSet，LinkedHashSet，TreeSet。
2、Set是如何实现元素唯一性的
   javadoc中对Set的描述第一段如下：“A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 
   and e2 such that e1.equals(e2), and at most one null element. As implied by its name, this interface models the mathematical set abstraction.”
   这段话是对是错，请看下面分析。
   要进行下面的论述，我们先了解一下Map。Map中的元素是“键－值”对，其中“键”必须是唯一的。TreeSet和HashSet就是利用这个特性实现“no duplicate    elements”。它把set中的元素作为Map中的“键”，从而保持元素的唯一性。这些键在Map中又是如何区分的呢？不同的Map有不同的做法，而且区别很大。
   下面我们分别就TreeSet、HashSet和CopyOnWriteArraySet进行论述：
2.1、TreeSet部分：
   以下以TreeSet为例进行分析。
   请看TreeSet的部分实体：

public class TreeSet  extends AbstractSet   implements SortedSet, Cloneable, java.io.Serializable
 {
  // The backing Map
      private transient SortedMap ,Object m; 
      // The keySet view of the backing Map
      private transient Set  keySet; 
      // Dummy value to associate with an Object in the backing Map
      //这是每个键所指的对像
      private static final Object PRESENT = new Object();
      //constructor
      private TreeSet(SortedMap ,Object  m) {
          this.m = m;
           keySet = m.keySet();
      }
      public TreeSet() {
         this(new TreeMap ,Object());
      }
      //以下省略.
 }

    可以看到TreeSet使用了SortedMap作为其Map保存“键－值”对，而这个SortedMap的真正实体是TreeMap。
    
    请看示例程序1： 

import java.util.*;
 public class SetTest1
 {
         public static void main(String[] args)
        {
           Set set = new TreeSet();
           set.add(new SetElement1("aa"));
           set.add(new SetElement1("bb"));
         }
      static class SetElement1
      {
           String s;
           public SetElement1(String s)
            {
                this.s =  s;
            }
             public String toString()
             {
                    return s;
             }
           public boolean equals(Object obj) 
            {
                return s.equals(((SetElement1)obj).s);
           }
     }
 }

    该程序能够正常编译，但是运行时会抛出异常java.lang.ClassCastException。为什么？
    
    请看示例程序2：

import java.util.*;
 public class SetTest2
{
          public static void main(String[] args)
          {
               Set set = new TreeSet();
               set.add(new SetElement2("aa"));
               set.add(new SetElement2("aa"));
               set.add(new SetElement2("bb"));
               System.out.println(set);
          }
      static class SetElement2 implements Comparable
      {
               String s;
               public SetElement2(String s){
                this.s =  s;
                  }
                   public String toString(){
                    return s;
                   }
                   public int compareTo(Object o){
                    return s.compareTo(((SetElement2)o).s);
                   }
                   public boolean equals(Object obj) {
                    return s.equals(((SetElement2)obj).s);
                   }
          }
 }

   运行结果：
   [aa, bb]
   这正是我们所期望的结果。那“示例程序1”和“示例程序2”有什么区别？
   是因为SetElement2实现了Comparable接口，而SetElement1没有。SetElement2实现Comparable接口有什么用呢？因为在TreeSet的add方法中需要比较两个 元素的“值”。请看TreeMap中的compare方法： 

  private int compare(K k1, K k2) {
        return (comparator==null ? ((Comparable<K>)k1).compareTo(k2)
                                 : comparator.compare((K)k1, (K)k2));
   }

   可见这个方法先把要比较的元素down cast成Comparable类型。这里就可以解释“示例程序1”中为什么会抛出异常java.lang.ClassCastException，因SetElement1没有实现Comparable接口，当然就不能down cast成Comparable。可见，要用TreeSet来做为你的Set，那么Set中所装的元素都必须实现了Comparable接口。
   说到这里，你是不是想到了TreeSet中是采用Comparable接口中的compareTo方法来判断元素是否相同（duplicate），而不是采用其他类似equals之类的东东来判断。
   
   请看示例程序3：
   

 import java.util.Set;
 import java.util.*;
 public class SetTest3 
{
      public static void main(String[] args)
     {
           Set set = new HashSet();
           set.add(new SetElement3("aa"));
           set.add(new SetElement3("aa"));
           set.add(new SetElement3("bb"));
           System.out.println(set);
      }
      static class SetElement3 implements Comparable
      {
           String s;
           public SetElement3(String s){
            this.s =  s;
           }
           public String toString(){
            return s;
           }
           public int compareTo(Object o){
            //return s.compareTo(((SetElement3)o).s);
            return -1;
           }
           public boolean equals(Object obj) {
            return s.equals(((SetElement3)obj).s);
           }
    }
 }

   运行结果：
   [bb, aa, aa]
   看到没有，有两个“aa”！！这是因为compareTo返回值始终是"-1"，也就是说“把任何元素都看成不同”。
   
   综上所述，你是否对javadoc中对Set功能的描述有了怀疑？！

2.2、HashSet部分：
   以下以HashSet为例进行分析。
   从Hashset类的主体部分：
 

public class HashSet  extends AbstractSet  implements Set , Cloneable, java.io.Serializable
 {
      static final long serialVersionUID = -5024744406713321676L;
      private transient HashMap  Object map;
      // Dummy value to associate with an Object in the backing Map
      //这是每个键所指的对像
       private static final Object PRESENT = new Object();  

     public HashSet() 
     {
         map = new HashMap  Object();
      }
     public boolean add(E o)
     {
         return map.put(o, PRESENT)==null;
      }
    //以下省略.
    } 

        public HashSet() { 
          map = new HashMap  Object();
    
     }

   可以看到HashSet使用了HashMap作为其Map保存“键－值”对。
   
   请看示例程序4：

 import java.util.*;
 public class SetTest4 {