深入淺出的分析 Set集合

作者：炸雞可樂 2019-11-14 09:53:30

關(guān)于 Set 接口，在實際開發(fā)中，其實很少用到，但是如果你出去面試，它可能依然是一個繞不開的話題。

01. 摘要

“關(guān)于 Set 接口，在實際開發(fā)中，其實很少用到，但是如果你出去面試，它可能依然是一個繞不開的話題。

言歸正傳，廢話咱們也不多說了，相信使用過 Set 集合類的朋友都知道，Set集合的特點主要有：元素不重復(fù)、存儲無序的特點。

啥意思呢?你可以理解為，向一個瓶子里面扔東西，這些東西沒有記號是第幾個放進去的，但是有一點就是這個瓶子里面不會有重樣的東西。

細細思考，你會發(fā)現(xiàn)， Set 集合的這些特性正處于 List 集合和 Map 集合之間，為什么這么說呢?之前的集合文章中，咱們了解到，List 集合的特點就是存取有序，本質(zhì)是一個有序數(shù)組，每個元素依次按照順序存儲;Map 集合主要用于存放鍵值對，雖然底層也是用數(shù)組存放，但是元素在數(shù)組中的下標是通過哈希算法計算出來的，數(shù)組下標無序。

而 Set 集合，在元素存儲方面，注重獨立無二的特性，如果某個元素在集合中已經(jīng)存在，不會存儲重復(fù)的元素，同時，集合存儲的是元素，不像 Map 集合那樣存儲的是鍵值對。

具體的分析，咱們慢慢道來，打開 Set 集合，主要實現(xiàn)類有 HashSet、LinkedHashSet 、TreeSet 、EnumSet( RegularEnumSet、JumboEnumSet )等等，總結(jié) Set 接口實現(xiàn)類，圖如下：

由圖中的繼承關(guān)系，可以知道，Set 接口主要實現(xiàn)類有 AbstractSet、HashSet、LinkedHashSet 、TreeSet 、EnumSet( RegularEnumSet、JumboEnumSet )，其中 AbstractSet、EnumSet 屬于抽象類，EnumSet 是在 jdk1.5 中新增的，不同的是 EnumSet 集合元素必須是枚舉類型。

HashSet 是一個輸入輸出無序的集合，集合中的元素基于 HashMap 的 key 實現(xiàn)，元素不可重復(fù);
LinkedHashSet 是一個輸入輸出有序的集合，集合中的元素基于 LinkedHashMap 的 key 實現(xiàn)，元素也不可重復(fù);
TreeSet 是一個排序的集合，集合中的元素基于 TreeMap 的 key 實現(xiàn)，同樣元素不可重復(fù);
EnumSet 是一個與枚舉類型一起使用的專用 Set 集合，其中 RegularEnumSet 和 JumboEnumSet 不能單獨實例化，只能由 EnumSet 來生成，同樣元素不可重復(fù);

下面咱們來對各個主要實現(xiàn)類進行一一分析!

02. HashSet

HashSet 是一個輸入輸出無序的集合，底層基于 HashMap 來實現(xiàn)，HashSet 利用 HashMap 中的key元素來存放元素，這一點我們可以從源碼上看出來，閱讀源碼如下：

public class HashSet<E> 
    extends AbstractSet<E> 
    implements Set<E>, Cloneable, java.io.Serializable{ 
     
    // HashMap 變量 
    private transient HashMap<E,Object> map; 
     
    /**HashSet 初始化*/ 
    public HashSet() { 
        //默認實例化一個 HashMap 
        map = new HashMap<>(); 
    } 
}

add方法

打開HashSet的add()方法，源碼如下：

public boolean add(E e) { 
    //向 HashMap 中添加元素 
    return map.put(e, PRESENT)==null; 
}

其中變量PRESENT，是一個非空對象，源碼部分如下：

private static final Object PRESENT = new Object();

可以分析出，當進行add()的時候，等價于

HashMap map = new HashMap<>(); 
map.put(e, new Object());//e 表示要添加的元素

在之前的集合文章中，咱們了解到 HashMap 在添加元素的時候，通過equals()和hashCode()方法來判斷傳入的key是否相同，如果相同，那么 HashMap 認為添加的是同一個元素，反之，則不是。

從源碼分析上可以看出，HashSet 正是使用了 HashMap 的這一特性，實現(xiàn)存儲元素下標無序、元素不會重復(fù)的特點。

remove方法

HashSet 的刪除方法，同樣如此，也是基于 HashMap 的底層實現(xiàn)，源碼如下：

public boolean remove(Object o) { 
    //調(diào)用HashMap 的remove方法，移除元素 
    return map.remove(o)==PRESENT; 
}

查詢方法

HashSet 沒有像 List、Map 那樣提供 get 方法，而是使用迭代器或者 for 循環(huán)來遍歷元素，方法如下：

public static void main(String[] args) { 
    Set<String> hashSet = new HashSet<String>(); 
    System.out.println("HashSet初始容量大小："+hashSet.size()); 
    hashSet.add("1"); 
    hashSet.add("2"); 
    hashSet.add("3"); 
    hashSet.add("3"); 
    hashSet.add("2"); 
    hashSet.add(null); 
 
    //相同元素會自動覆蓋 
    System.out.println("HashSet容量大小："+hashSet.size()); 
    //迭代器遍歷 
    Iterator<String> iterator = hashSet.iterator(); 
    while (iterator.hasNext()){ 
        String str = iterator.next(); 
        System.out.print(str + ","); 
    } 
 
    System.out.println("\n==========="); 
    //增強for循環(huán) 
    for (String str : hashSet) { 
        System.out.print(str + ","); 
    } 
}

輸出結(jié)果：

HashSet初始容量大小：0 
HashSet容量大小：4 
null,1,2,3, 
=========== 
null,1,2,3,

需要注意的是，HashSet 允許添加為null的元素。

03. LinkedHashSet

LinkedHashSet 是一個輸入輸出有序的集合，繼承自 HashSet，但是底層基于 LinkedHashMap 來實現(xiàn)。

如果你之前了解過 LinkedHashMap，那么你一定知道，它也繼承自 HashMap，唯一有區(qū)別的是，LinkedHashMap 底層數(shù)據(jù)結(jié)構(gòu)基于循環(huán)鏈表實現(xiàn)，并且數(shù)組指定了頭部和尾部，雖然數(shù)組的下標存儲無序，但是卻可以通過數(shù)組的頭部和尾部，加上循環(huán)鏈表，依次可以查詢到元素存儲的過程，從而做到輸入輸出有序的特點。

如果還不了解 LinkedHashMap 的實現(xiàn)過程，可以參閱集合系列中關(guān)于 LinkedHashMap 的實現(xiàn)過程文章。

閱讀 LinkedHashSet 的源碼，類定義如下：

public class LinkedHashSet<E> 
    extends HashSet<E> 
    implements Set<E>, Cloneable, java.io.Serializable { 
 
    public LinkedHashSet() { 
        //調(diào)用 HashSet 的方法 
        super(16, .75f, true); 
    } 
}

查詢源碼，super調(diào)用的方法，源碼如下：

HashSet(int initialCapacity, float loadFactor, boolean dummy) { 
    //初始化一個 LinkedHashMap 
    map = new LinkedHashMap<>(initialCapacity, loadFactor); 
}

add方法

LinkedHashSet沒有重寫add方法，而是直接調(diào)用HashSet的add()方法，因為map的實現(xiàn)類是LinkedHashMap，所以此處是向LinkedHashMap中添加元素，當進行add()的時候，等價于

HashMap map = new LinkedHashMap<>(); 
map.put(e, new Object());//e 表示要添加的元素

remove方法

LinkedHashSet也沒有重寫remove方法，而是直接調(diào)用HashSet的刪除方法，因為LinkedHashMap沒有重寫remove方法，所以調(diào)用的也是HashMap的remove方法，源碼如下：

public boolean remove(Object o) { 
    //調(diào)用HashMap 的remove方法，移除元素 
    return map.remove(o)==PRESENT; 
}

查詢方法

同樣的，LinkedHashSet 沒有提供 get 方法，使用迭代器或者 for 循環(huán)來遍歷元素，方法如下：

public static void main(String[] args) { 
    Set<String> linkedHashSet = new LinkedHashSet<String>(); 
    System.out.println("linkedHashSet初始容量大小："+linkedHashSet.size()); 
    linkedHashSet.add("1"); 
    linkedHashSet.add("2"); 
    linkedHashSet.add("3"); 
    linkedHashSet.add("3"); 
    linkedHashSet.add("2"); 
    linkedHashSet.add(null); 
    linkedHashSet.add(null); 
 
    System.out.println("linkedHashSet容量大小："+linkedHashSet.size()); 
    //迭代器遍歷 
    Iterator<String> iterator = linkedHashSet.iterator(); 
    while (iterator.hasNext()){ 
        String str = iterator.next(); 
        System.out.print(str + ","); 
    } 
 
    System.out.println("\n==========="); 
    //增強for循環(huán) 
    for (String str : linkedHashSet) { 
        System.out.print(str + ","); 
    } 
}

輸出結(jié)果：

linkedHashSet初始容量大小：0 
linkedHashSet容量大小：4 
1,2,3,null, 
=========== 
1,2,3,null,

可見，LinkedHashSet 與 HashSet 相比，LinkedHashSet 輸入輸出有序。

04. TreeSet

TreeSet 是一個排序的集合，實現(xiàn)了NavigableSet、SortedSet、Set接口，底層基于 TreeMap 來實現(xiàn)。TreeSet 利用 TreeMap 中的key元素來存放元素，這一點我們也可以從源碼上看出來，閱讀源碼，類定義如下：

public class TreeSet<E> extends AbstractSet<E> 
implements NavigableSet<E>, Cloneable, java.io.Serializable { 
     
    //TreeSet 使用NavigableMap接口作為變量 
    private transient NavigableMap<E,Object> m; 
     
    /**對象初始化*/ 
    public TreeSet() { 
        //默認實例化一個 TreeMap 對象 
        this(new TreeMap<E,Object>()); 
    } 
     
    //對象初始化調(diào)用的方法 
    TreeSet(NavigableMap<E,Object> m) { 
        this.m = m; 
    } 
}

new TreeSet<>()對象實例化的時候，表達的意思，可以簡化為如下：

NavigableMap<E,Object> m = new TreeMap<E,Object>();

因為TreeMap實現(xiàn)了NavigableMap接口，所以沒啥問題。

public class TreeMap<K,V> 
    extends AbstractMap<K,V> 
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable{ 
    ...... 
}

add方法

打開TreeSet的add()方法，源碼如下：

public boolean add(E e) { 
    //向 TreeMap 中添加元素 
    return m.put(e, PRESENT)==null; 
}

其中變量PRESENT，也是是一個非空對象，源碼部分如下：

private static final Object PRESENT = new Object();

可以分析出，當進行add()的時候，等價于

TreeMap map = new TreeMap<>(); 
map.put(e, new Object());//e 表示要添加的元素

TreeMap 類主要功能在于，給添加的集合元素，按照一個的規(guī)則進行了排序，默認以自然順序進行排序，當然也可以自定義排序，比如測試方法如下：

public static void main(String[] args) { 
    Map initMap = new TreeMap(); 
    initMap.put("4", "d"); 
    initMap.put("3", "c"); 
    initMap.put("1", "a"); 
    initMap.put("2", "b"); 
    //默認自然排序，key為升序 
    System.out.println("默認 排序結(jié)果:" + initMap.toString()); 
    //自定義排序，在TreeMap初始化階段傳入Comparator 內(nèi)部對象 
    Map comparatorMap = new TreeMap<String, String>(new Comparator<String>() { 
        @Override 
        public int compare(String o1, String o2){ 
            //根據(jù)key比較大小，采用倒敘，以大到小排序 
            return o2.compareTo(o1); 
        } 
    }); 
    comparatorMap.put("4", "d"); 
    comparatorMap.put("3", "c"); 
    comparatorMap.put("1", "a"); 
    comparatorMap.put("2", "b"); 
    System.out.println("自定義 排序結(jié)果:" + comparatorMap.toString()); 
}

輸出結(jié)果：

默認 排序結(jié)果:{1=a, 2=b, 3=c, 4=d} 
自定義 排序結(jié)果:{4=d, 3=c, 2=b, 1=a}

相信使用過TreeMap的朋友，一定知道TreeMap會自動將key按照一定規(guī)則進行排序，TreeSet正是使用了TreeMap這種特性，來實現(xiàn)添加的元素集合，在輸出的時候，其結(jié)果是已經(jīng)排序好的。

如果您沒看過源碼TreeMap的實現(xiàn)過程，可以參閱集合系列文章中TreeMap的實現(xiàn)過程介紹，或者閱讀 jdk 源碼。

remove方法

TreeSet 的刪除方法，同樣如此，也是基于 TreeMap 的底層實現(xiàn)，源碼如下：

public boolean remove(Object o) { 
        //調(diào)用TreeMap 的remove方法，移除元素 
        return m.remove(o)==PRESENT; 
}

查詢方法

TreeSet 沒有重寫 get 方法，而是使用迭代器或者 for 循環(huán)來遍歷元素，方法如下：

public static void main(String[] args) { 
    Set<String> treeSet = new TreeSet<>(); 
    System.out.println("treeSet初始容量大小："+treeSet.size()); 
    treeSet.add("1"); 
    treeSet.add("4"); 
    treeSet.add("3"); 
    treeSet.add("8"); 
    treeSet.add("5"); 
 
    System.out.println("treeSet容量大小："+treeSet.size()); 
    //迭代器遍歷 
    Iterator<String> iterator = treeSet.iterator(); 
    while (iterator.hasNext()){ 
        String str = iterator.next(); 
        System.out.print(str + ","); 
    } 
 
    System.out.println("\n==========="); 
    //增強for循環(huán) 
    for (String str : treeSet) { 
        System.out.print(str + ","); 
    } 
}

輸出結(jié)果：

treeSet初始容量大小：0 
treeSet容量大小：5 
1,3,4,5,8, 
=========== 
1,3,4,5,8,

自定義排序

使用自定義排序，有 2 種方法，第一種在需要添加的元素類，實現(xiàn)Comparable接口，重寫compareTo方法來實現(xiàn)對元素進行比較，實現(xiàn)自定義排序。

方法一

/** 
  * 創(chuàng)建實體類Person實現(xiàn)Comparable接口 
  */ 
public class Person implements Comparable<Person>{ 
    private int age; 
    private String name; 
    public Person(String name, int age){ 
        this.name = name; 
        this.age = age; 
    } 
    @Override 
    public int compareTo(Person o){ 
        //重寫 compareTo 方法，自定義排序算法 
        return this.age-o.age; 
    } 
    @Override 
    public String toString(){ 
        return name+":"+age; 
    } 
}

創(chuàng)建一個Person實體類，實現(xiàn)Comparable接口，重寫compareTo方法，通過變量age實現(xiàn)自定義排序測試方法如下：

public static void main(String[] args) { 
    Set<Person> treeSet = new TreeSet<>(); 
    System.out.println("treeSet初始容量大小："+treeSet.size()); 
    treeSet.add(new Person("李一",18)); 
    treeSet.add(new Person("李二",17)); 
    treeSet.add(new Person("李三",19)); 
    treeSet.add(new Person("李四",21)); 
    treeSet.add(new Person("李五",20)); 
 
    System.out.println("treeSet容量大小："+treeSet.size()); 
    System.out.println("按照年齡從小到大，自定義排序結(jié)果："); 
    //迭代器遍歷 
    Iterator<Person> iterator = treeSet.iterator(); 
    while (iterator.hasNext()){ 
        Person person = iterator.next(); 
        System.out.print(person.toString() + ","); 
    } 
}

輸出結(jié)果：

treeSet初始容量大小：0 
treeSet容量大小：5 
按照年齡從小到大，自定義排序結(jié)果： 
李二:17,李一:18,李三:19,李五:20,李四:21,

方法二

第二種方法是在TreeSet初始化階段，Person不用實現(xiàn)Comparable接口，將Comparator接口以內(nèi)部類的形式作為參數(shù)，初始化進去，方法如下：

public static void main(String[] args) { 
    //自定義排序 
    Set<Person> treeSet = new TreeSet<>(new Comparator<Person>(){ 
        @Override 
        public int compare(Person o1, Person o2) { 
            if(o1 == null || o2 == null){ 
                //不用比較 
                return 0; 
            } 
            //從小到大進行排序 
            return o1.getAge() - o2.getAge(); 
        } 
    }); 
    System.out.println("treeSet初始容量大小："+treeSet.size()); 
    treeSet.add(new Person("李一",18)); 
    treeSet.add(new Person("李二",17)); 
    treeSet.add(new Person("李三",19)); 
    treeSet.add(new Person("李四",21)); 
    treeSet.add(new Person("李五",20)); 
 
    System.out.println("treeSet容量大小："+treeSet.size()); 
    System.out.println("按照年齡從小到大，自定義排序結(jié)果："); 
    //迭代器遍歷 
    Iterator<Person> iterator = treeSet.iterator(); 
    while (iterator.hasNext()){ 
        Person person = iterator.next(); 
        System.out.print(person.toString() + ","); 
    } 
}

輸出結(jié)果：

treeSet初始容量大小：0 
treeSet容量大小：5 
按照年齡從小到大，自定義排序結(jié)果： 
李二:17,李一:18,李三:19,李五:20,李四:21,

需要注意的是，TreeSet不能添加為空的元素，否則會報空指針錯誤!

05. EnumSet

EnumSet 是一個與枚舉類型一起使用的專用 Set 集合，繼承自AbstractSet抽象類。與 HashSet、LinkedHashSet 、TreeSet 不同的是，EnumSet 元素必須是Enum的類型，并且所有元素都必須來自同一個枚舉類型，EnumSet 定義源碼如下：

public abstract class EnumSet<E extends Enum<E>> extends AbstractSet<E> 
    implements Cloneable, java.io.Serializable { 
    ...... 
}

EnumSet是一個虛類，不能直接通過實例化來獲取對象，只能通過它提供的靜態(tài)方法來返回EnumSet實現(xiàn)類的實例。

EnumSet的實現(xiàn)類有兩個，分別是RegularEnumSet、JumboEnumSet兩個類，兩個實現(xiàn)類都繼承自EnumSet。

EnumSet會根據(jù)枚舉類型中元素的個數(shù)，來決定是返回哪一個實現(xiàn)類，當 EnumSet元素中的元素個數(shù)小于或者等于64，就會返回RegularEnumSet實例;當EnumSet元素個數(shù)大于64，就會返回JumboEnumSet實例。

這一點，我們可以從源碼中看出，源碼如下：

public static <E extends Enum<E>> EnumSet<E> noneOf(Class<E> elementType) { 
    Enum<?>[] universe = getUniverse(elementType); 
    if (universe == null) 
        throw new ClassCastException(elementType + " not an enum"); 
    //當元素個數(shù)小于或者等于 64 的時候，返回 RegularEnumSet 
    if (universe.length <= 64) 
        return new RegularEnumSet<>(elementType, universe); 
    else 
        //大于64，返回 JumboEnumSet 
        return new JumboEnumSet<>(elementType, universe); 
}

noneOf是EnumSet中一個靜態(tài)方法，用于判斷是返回哪一個實現(xiàn)類。

我們來看看當元素個數(shù)小于等于64的時候，使用RegularEnumSet的類，源碼如下：

class RegularEnumSet<E extends Enum<E>> extends EnumSet<E> { 
 
    /**元素為long型*/ 
    private long elements = 0L; 
 
    /**添加元素*/ 
    public boolean add(E e) { 
        typeCheck(e); 
 
        long oldElements = elements; 
        //二進制運算，獲取元素 
        elements |= (1L << ((Enum<?>)e).ordinal()); 
        return elements != oldElements; 
    } 
}

RegularEnumSet 通過二進制運算得到結(jié)果，直接使用long來存放元素。

我們再來看看當元素個數(shù)大于64的時候，使用JumboEnumSet的類，源碼如下：

class JumboEnumSet<E extends Enum<E>> extends EnumSet<E> { 
 
    /**元素為long型*/ 
    private long elements = 0L; 
 
    /**添加元素*/ 
    public boolean add(E e) { 
        typeCheck(e); 
 
        int eOrdinal = e.ordinal(); 
        int eWordNum = eOrdinal >>> 6; 
 
        long oldElements = elements[eWordNum]; 
        //二進制運算 
        elements[eWordNum] |= (1L << eOrdinal); 
        //使用數(shù)組來操作元素 
        boolean result = (elements[eWordNum] != oldElements); 
        if (result) 
            size++; 
        return result; 
    } 
}

JumboEnumSet 也是通過二進制運算得到結(jié)果，使用long來存放元素，但是它是使用數(shù)組來存放元素。

二者相比，RegularEnumSet 效率比 JumboEnumSet 高些，因為操作步驟少，大多數(shù)情況下返回的是 RegularEnumSet，只有當枚舉元素個數(shù)超過 64 的時候，會使用 JumboEnumSet。

添加元素

新建一個EnumEntity的枚舉類型，定義2個參數(shù)。

public enum EnumEntity { 
    WOMAN,MAN; 
}

創(chuàng)建一個空的 EnumSet!

//創(chuàng)建一個 EnumSet，內(nèi)容為空 
EnumSet<EnumEntity> noneSet = EnumSet.noneOf(EnumEntity.class); 
System.out.println(noneSet);

輸出結(jié)果：

[]

創(chuàng)建一個 EnumSet，并將枚舉類型的元素全部添加進去!

//創(chuàng)建一個 EnumSet，將EnumEntity 元素內(nèi)容添加到EnumSet中 
EnumSet<EnumEntity> allSet = EnumSet.allOf(EnumEntity.class); 
System.out.println(allSet);

輸出結(jié)果：

[WOMAN, MAN]

創(chuàng)建一個 EnumSet，添加指定的枚舉元素!

//創(chuàng)建一個 EnumSet，添加 WOMAN 到 EnumSet 中 
EnumSet<EnumEntity> customSet = EnumSet.of(EnumEntity.WOMAN); 
System.out.println(customSet);

查詢元素

EnumSet與HashSet、LinkedHashSet、TreeSet一樣，通過迭代器或者 for 循環(huán)來遍歷元素，方法如下：

EnumSet<EnumEntity> allSet = EnumSet.allOf(EnumEntity.class); 
for (EnumEntity enumEntity : allSet) { 
    System.out.print(enumEntity + ","); 
}

輸出結(jié)果：

WOMAN,MAN,

06. 總結(jié)

HashSet 是一個輸入輸出無序的 Set 集合，元素不重復(fù)，底層基于 HashMap 的 key 來實現(xiàn)，元素可以為空，如果添加的元素為對象，對象需要重寫 equals() 和 hashCode() 方法來約束是否為相同的元素。

LinkedHashSet 是一個輸入輸出有序的 Set 集合，繼承自 HashSet，元素不重復(fù)，底層基于 LinkedHashMap 的 key來實現(xiàn)，元素也可以為空，LinkedHashMap 使用循環(huán)鏈表結(jié)構(gòu)來保證輸入輸出有序。

TreeSet 是一個排序的 Set 集合，元素不可重復(fù)，底層基于 TreeMap 的 key來實現(xiàn)，元素不可以為空，默認按照自然排序來存放元素，也可以使用 Comparable 和 Comparator 接口來比較大小，實現(xiàn)自定義排序。

EnumSet 是一個與枚舉類型搭配使用的專用 Set 集合，在 jdk1.5 中加入。EnumSet 是一個虛類，有2個實現(xiàn)類 RegularEnumSet、JumboEnumSet，不能顯式的實例化改類，EnumSet 會動態(tài)決定使用哪一個實現(xiàn)類，當元素個數(shù)小于等于64的時候，使用 RegularEnumSet;大于 64的時候，使用JumboEnumSet類，EnumSet 其內(nèi)部使用位向量實現(xiàn)，擁有極高的時間和空間性能，如果元素是枚舉類型，推薦使用 EnumSet。

07. 參考

1、JDK1.7&JDK1.8 源碼

2、程序園 - java集合-EnumMap與EnumSet

責任編輯：華軒來源： Java極客技術(shù)

Set 集合存儲

成人免费xxxxx在线视频软件_久久精品久久久_亚洲国产精品久久久_天天色天天色_亚洲人成一区_欧美一级欧美三级在线观看

深入淺出的分析 Set集合

01. 摘要

02. HashSet

03. LinkedHashSet

04. TreeSet

05. EnumSet

06. 總結(jié)

07. 參考