转载请注明原文地址：

    Java中的Set主要有：HashSet、TreeSet、LinkedHashSet。

    一：HashSet

    HashSet的底层实际上就是一个HashMap，HashSet上的一系列操作的实现都是调用其底层的map的方法而已。来看部分主要源码：

public class HashSet
     
              extends AbstractSet
      
               implements Set
       
        , Cloneable, java.io.Serializable       {        // 使用 HashMap 的 key 保存 HashSet 中所有元素       private transient HashMap
        
          map;        // 定义一个虚拟的 Object 对象作为 HashMap 的 value        private static final Object PRESENT = new Object();        ...        // 初始化 HashSet，底层会初始化一个 HashMap        public HashSet()        {            map = new HashMap
         
          ();        }        // 以指定的 initialCapacity、loadFactor 创建 HashSet        // 其实就是以相应的参数创建 HashMap        public HashSet(int initialCapacity, float loadFactor)        {            map = new HashMap
          
           (initialCapacity, loadFactor); } public HashSet(int initialCapacity) { map = new HashMap
           
            (initialCapacity); } HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap
            
             (initialCapacity , loadFactor); } // 调用 map 的 keySet 来返回所有的 key public Iterator
             
               iterator() { return map.keySet().iterator(); } // 调用 HashMap 的 size() 方法返回数量，就得到该 Set 里元素的个数 public int size() { return map.size(); } // 调用 HashMap 的 isEmpty() 判断该 HashSet 是否为空， // 当 HashMap 为空时，对应的 HashSet 也为空 public boolean isEmpty() { return map.isEmpty(); } // 调用 HashMap 的 containsKey 判断是否包含指定 key //HashSet 的所有元素就是通过 HashMap 的 key 来保存的 public boolean contains(Object o) { return map.containsKey(o); } // 将指定元素放入 HashSet 中，也就是将该元素作为 key 放入 HashMap public boolean add(E e) { return map.put(e, PRESENT) == null; } // 调用 HashMap 的 remove 方法删除指定 Entry，也就删除了 HashSet 中对应的元素 public boolean remove(Object o) { return map.remove(o)==PRESENT; } // 调用 Map 的 clear 方法清空所有 Entry，也就清空了 HashSet 中所有元素 public void clear() { map.clear(); } ... }
             
            
           
          
         
        
       
      
     

       1：HashSet元素的存储顺序：由于HashSet底层是用hashmap存储元素的，所以元素的存储顺序并不是插入顺序，而是通过元素值的哈希值来访问的。

       2：HashSet如何保证元素不重复：HashSet在调用add(obj)方法插入元素时，首先调用元素的hashcode()方法，如果map中对应索引位还没有内容，则把元素值储存；如果索引位已有内容，则继续调用 元素的equals()方法把新增元素与已有元素值进行比较，如果是相等的，则新值不插入（因为重复了），如果是不相等的，则把新元素插入到该索引位元素列表的末尾。【原因：哈希码是存在冲突的，我们只规定了相等对象必定有相同哈希码，却没有规定不同对象不能有相同哈希码。当不同对象拥有同一哈希码时，就只能在哈希码索引位上建立链表来存放了。】

      

    二：TreeSet

    TreeSet在保持元素唯一性的基础上，更增加了使插入元素有序的特性。TreeSet的底层实际上是TreeMap，在TreeSet上的操作的实现都是调用了底层的TreeMap的方法。

   

package java.util;public class TreeSet
     
       extends AbstractSet
      
           implements NavigableSet
       
        , Cloneable, java.io.Serializable{    // NavigableMap对象    private transient NavigableMap
        
          m;    // TreeSet是通过TreeMap实现的，    // PRESENT是键-值对中的值。    private static final Object PRESENT = new Object();    // 不带参数的构造函数。创建一个空的TreeMap    public TreeSet() {        this(new TreeMap
         
          ());    }    // 将TreeMap赋值给 "NavigableMap对象m"    TreeSet(NavigableMap
          
            m) { this.m = m; } // 带比较器的构造函数。 public TreeSet(Comparator
            comparator) { this(new TreeMap
           
            (comparator)); } // 创建TreeSet，并将集合c中的全部元素都添加到TreeSet中 public TreeSet(Collection
             c) { this(); // 将集合c中的元素全部添加到TreeSet中 addAll(c); } // 创建TreeSet，并将s中的全部元素都添加到TreeSet中 public TreeSet(SortedSet
            
              s) { this(s.comparator()); addAll(s); } // 返回TreeSet的顺序排列的迭代器。 // 因为TreeSet时TreeMap实现的，所以这里实际上时返回TreeMap的“键集”对应的迭代器 public Iterator
             
               iterator() { return m.navigableKeySet().iterator(); } // 返回TreeSet的逆序排列的迭代器。 // 因为TreeSet时TreeMap实现的，所以这里实际上时返回TreeMap的“键集”对应的迭代器 public Iterator
              
                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
                c) { // Use linear-time version if applicable if (m.size()==0 && c.size() > 0 && c instanceof SortedSet && m instanceof TreeMap) { SortedSet
                set = (SortedSet
               ) c; TreeMap
               
                 map = (TreeMap
                
                 ) m; Comparator
                  cc = (Comparator
                 ) set.comparator(); Comparator
                  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
                 
                   subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) { return new TreeSet
                  
                   (m.subMap(fromElement, fromInclusive, toElement, toInclusive)); } // 返回Set的头部，范围是：从头部到toElement。 // inclusive是是否包含toElement的标志 public NavigableSet
                   
                     headSet(E toElement, boolean inclusive) { return new TreeSet
                    
                     (m.headMap(toElement, inclusive)); } // 返回Set的尾部，范围是：从fromElement到结尾。 // inclusive是是否包含fromElement的标志 public NavigableSet
                     
                       tailSet(E fromElement, boolean inclusive) { return new TreeSet
                      
                       (m.tailMap(fromElement, inclusive)); } // 返回子Set。范围是：从fromElement(包括)到toElement(不包括)。 public SortedSet
                       
                         subSet(E fromElement, E toElement) { return subSet(fromElement, true, toElement, false); } // 返回Set的头部，范围是：从头部到toElement(不包括)。 public SortedSet
                        
                          headSet(E toElement) { return headSet(toElement, false); } // 返回Set的尾部，范围是：从fromElement到结尾(不包括)。 public SortedSet
                         
                           tailSet(E fromElement) { return tailSet(fromElement, true); } // 返回Set的比较器 public Comparator
                           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 = m.pollFirstEntry(); return (e == null)? null : e.getKey(); } // 获取最后一个元素，并将该元素从TreeMap中删除。 public E pollLast() { Map.Entry
                           
                             e = m.pollLastEntry(); return (e == null)? null : e.getKey(); } // 克隆一个TreeSet，并返回Object对象 public Object clone() { TreeSet
                            
                              clone = null; try { clone = (TreeSet
                             
                              ) super.clone(); } catch (CloneNotSupportedException e) { throw new InternalError(); } clone.m = new TreeMap
                              
                               (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
                                c = (Comparator
                               ) s.readObject(); TreeMap
                               
                                 tm; if (c==null) tm = new TreeMap
                                
                                 (); else tm = new TreeMap
                                 
                                  (c); m = tm; // 从输入流中读取TreeSet的“容量” int size = s.readInt(); // 从输入流中读取TreeSet的“全部元素” tm.readTreeSet(size, s, PRESENT); } // TreeSet的序列版本号 private static final long serialVersionUID = -2479143000061671589L;}
                                 
                                
                               
                              
                             
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

       1：TreeSet的排序规则制定：

           1）元素自身具备比较性：元素类实现Comparable接口，重写compareTo方法，这种方式叫做元素的自然排序（默认排序）。

           2）在创建TreeSet时指定比较器：定义一个比较器类实现接口Comparator，重写compare方法，在创建TreeSet时把比较器对象传进去。

       2：TreeSet中元素的唯一性保证：通过元素的compareTo方法或者treeset创建时的比较器compare方法，如果return 0则说明有相等元素存在，则新元素不插入。

 

    三：LinkedHashSet

    LinkedHashSet的特性是：记录了元素的插入顺序。在遍历时可以按照元素的插入顺序进行遍历。

    LinkHashSet维护了一个双向链表，记录元素的插入顺序，然后再根据元素值，采用hashcode()、equals()方法来存储元素值并实现元素的唯一性。