Set

List是有序集合的根接口， Set是無(wú)序集合的根接口，無(wú)序也就意味著元素不重復(fù) 。

更嚴(yán)格地說(shuō)，Set集合不包含一對(duì)元素e1和e2 ，使得eequals(e2) ，并且最多一個(gè)空元素。

使用Set存儲(chǔ)的特點(diǎn)與List相反：元素?zé)o序、不可重復(fù)。

常用的實(shí)現(xiàn)方式：HashSet、LinkedHashSet和TreeSet。

當(dāng)向HashSet結(jié)合中存入一個(gè)元素時(shí)，HashSet會(huì)調(diào)用該對(duì)象的hashCode()方法來(lái)得到該對(duì)象的hashCode值，然后根據(jù) hashCode值來(lái)決定該對(duì)象在HashSet中存儲(chǔ)位置。

簡(jiǎn)單的說(shuō)，HashSet集合判斷兩個(gè)元素相等的標(biāo)準(zhǔn)是兩個(gè)對(duì)象通過(guò)equals方法比較相等，并且兩個(gè)對(duì)象的hashCode()方法返回值也相等。

LinkedHashSet集合同樣是根據(jù)元素的hashCode值來(lái)決定元素的存儲(chǔ)位置，但是它同時(shí)使用鏈表維護(hù)元素的次序。

這樣使得元素看起來(lái)像是以插入順序保存的，也就是說(shuō)，當(dāng)遍歷該集合時(shí)候，LinkedHashSet將會(huì)以元素的添加順序訪問(wèn)集合的元素。

在使用Set存儲(chǔ)數(shù)據(jù)時(shí)，為保障元素唯一性，常常要重寫hashCode。

重寫hashCode方法時(shí)，盡量遵循以下原則：

1. 相同的對(duì)象返回相同的hashCode值
2. 不同的對(duì)象返回不同的hashCode值，否則，就會(huì)增加沖突的概率
3. 盡量的讓hashCode值散列開（用異或運(yùn)算可使結(jié)果的范圍更廣）

• HashSet
  • HashSet中沒(méi)有重復(fù)元素，底層由HashMap實(shí)現(xiàn)，不保證元素的順序(此處的沒(méi)有順序是指：元素插入的順序與輸出的順序不一致)，HashSet允許使用Null元素，HashSet是非同步的。
• LinkedHashSet
  • LinkedHashSet繼承自HashSet，其底層是基于LinkedHashMap來(lái)實(shí)現(xiàn)的，有序，非同步。
  • LinkedHashSet在迭代訪問(wèn)Set中的全部元素時(shí)，性能比HashSet好，但是插入時(shí)性能稍微遜色于HashSet。
• TreeSet
  • TreeSet底層是基于TreeMap實(shí)現(xiàn)的，所以元素有序。TreeSet支持兩種排序方式，自然排序和定制排序，其中自然排序?yàn)槟J(rèn)的排序方式。當(dāng)我們構(gòu)造TreeSet時(shí)，若使用不帶參數(shù)的構(gòu)造函數(shù)，則TreeSet的使用
  • 自然比較器；若用戶需要使用自定義的比較器，則需要使用帶比較器的參數(shù)。
  • TreeSet是線程不安全的。
  • 自然排序要求元素必須實(shí)現(xiàn)Compareable接口，并重寫里面的compareTo()方法，元素通過(guò)比較返回的int值來(lái)判斷排序序列，返回0說(shuō)明兩個(gè)對(duì)象相同。
  • 比較器排序需要在TreeSet初始化是時(shí)候傳入一個(gè)實(shí)現(xiàn)Comparator接口的比較器對(duì)象，或者采用匿名內(nèi)部類的方式new一個(gè)Comparator對(duì)象，重寫里面的compare()方法。
  • TreeSet判斷兩個(gè)對(duì)象不相等的方式是兩個(gè)對(duì)象通過(guò)equals方法返回false，或者通過(guò)CompareTo方法比較沒(méi)有返回0。
  • 在使用Set存儲(chǔ)元素時(shí)，元素雖然無(wú)放入順序，但Set的底層實(shí)現(xiàn)其實(shí)是Map，元素在Set中的位置是有該元素的HashCode決定的，所以其位置其實(shí)是固定的。
  • TreeSet是SortedSet接口的唯一實(shí)現(xiàn)類，TreeSet可以確保集合元素處于排序狀態(tài)。TreeSet支持兩種排序方式，自然排序和定制排序，其中自然排序?yàn)槟J(rèn)的排序方式。

至于具體使用哪種集合時(shí)，參考：

在List和Set兩個(gè)分支中，ArrayList和HashSet是對(duì)應(yīng)分支中適應(yīng)性最廣的，兩者再比較，ArrayList則適用性更廣一些。也就是說(shuō)如果要確定用List，但不確定用哪種List，就可以使用ArrayList；如果確定用Set，但不確定用哪種Set，就可以使用HashSet。如果只知道用集合，就用ArrayList 。

HashSet

1 HashSet是什么

HashSet的繼承關(guān)系：

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

HashSet是一個(gè)無(wú)序集合，其底層結(jié)構(gòu)是HashMap，簡(jiǎn)單來(lái)說(shuō)，HashSet是value是固定值（ Object PRESENT = new Object() ）的HashMap。

2 HashSet的特點(diǎn)

• HashSet的 底層實(shí)現(xiàn)是HashMap （HashSet的值存放于HashMap的key上，HashMap的value是一個(gè)統(tǒng)一的值）。
• HashSet中的 元素?zé)o序且不能重復(fù) （從插入HashSet元素的順序和遍歷HashSet的順序?qū)Ρ瓤梢钥闯觯?/li>
• HashSet是 線程不安全 的。如果要保證線程安全，其中一種方法是將其改造成線程安全的類，示例：

Set set = Collections.synchronizedSet(new HashSet(...));

• HashSet 允許存入null 。

3 HashSet如何檢查重復(fù)

當(dāng)你把對(duì)象加入HashSet時(shí)，HashSet會(huì)先計(jì)算對(duì)象的hashcode值來(lái)判斷對(duì)象加入的位置，同時(shí)也會(huì)與其他加入的對(duì)象的hashcode值作比較，如果沒(méi)有相同的hashcode，HashSet會(huì)假設(shè)對(duì)象沒(méi)有重復(fù)出現(xiàn)。但是如果發(fā)現(xiàn)有相同hashcode值的對(duì)象，這時(shí)會(huì)調(diào)用 equals() 方法來(lái)檢查hashcode相等的對(duì)象是否真的相同。如果兩者相同，HashSet就不會(huì)讓加入操作成功。

hashCode()與 equals()的相關(guān)規(guī)定

• 如果兩個(gè)對(duì)象相等，則hashcode一定也是相同的；
• 兩個(gè)對(duì)象相等，對(duì)兩個(gè)equals方法返回true；
• 兩個(gè)對(duì)象有相同的hashcode值，它們也不一定是相等的；
• 如果equals方法被覆蓋過(guò)，則hashCode方法也必須被覆蓋；
• hashCode()的默認(rèn)行為是對(duì)堆上的對(duì)象產(chǎn)生獨(dú)特值。如果沒(méi)有重寫hashCode()，則該 class的兩個(gè)對(duì)象無(wú)論如何都不會(huì)相等（即使這兩個(gè)對(duì)象指向相同的數(shù)據(jù)）。

4 HashSet常用方法

• 構(gòu)造一個(gè)新的空HashSet，默認(rèn)初始容量為16，負(fù)載因子為0.75

public HashSet()

• 構(gòu)造一個(gè)新的空HashSet，指定初始容量，負(fù)載因子為0.75

public HashSet(int initialCapacity)

• 構(gòu)造一個(gè)新的空HashSet，指定初始容量和負(fù)載因子

public HashSet(int initialCapacity, float loadFactor)

• 添加元素

public boolean add(E e)

• 清空集合

public void clear()

• 如果此集合包含指定的元素，則返回 true

public boolean contains(Object o)

• 如果此集合不包含任何元素，則返回 true

public boolean isEmpty()

• 獲取此集合中元素的迭代器

public Iterator<E> iterator()

• 刪除元素

public boolean remove(Object o)

• 返回此集合中的元素?cái)?shù)

public int size()

5 HashSet與HashMap的區(qū)別

HashSet源碼

由于HashSet的底層實(shí)現(xiàn)HashMap，所以其方法的實(shí)現(xiàn)基本都是對(duì)HashMap的操作。

變量：

    //HashSet集合中的內(nèi)容是通過(guò)HashMap數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)的
    private transient HashMap<E,Object> map;
    //向HashSet中添加數(shù)據(jù)，數(shù)據(jù)在上面的map結(jié)構(gòu)是作為key存在的，而value統(tǒng)一都是
    //PRESENT，這樣做是因?yàn)镾et只使用到了HashMap的key，所以此處定義一個(gè)靜態(tài)的常
    //量Object類，來(lái)充當(dāng)HashMap的value
    private static final Object PRESENT = new Object();

1 構(gòu)造方法

• HashSet()

    //直接 new 一個(gè)HashMap對(duì)象出來(lái)，采用無(wú)參的 HashMap 構(gòu)造函數(shù)，
    //HashMap對(duì)象具有默認(rèn)初始容量（16）和加載因子（0.75）
    public HashSet() {
        map = new HashMap<>();
    }

• HashSet(int initialCapacity, float loadFactor)

//指定初始容量和加載因子，創(chuàng)建HashMap實(shí)例
    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }

• HashSet(int initialCapacity)

//指定初始容量，創(chuàng)建HashMap
    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }

• HashSet(int initialCapacity, float loadFactor, boolean dummy)

//以指定的initialCapacity和loadFactor構(gòu)造一個(gè)新的空鏈接哈希集合。 
    //此構(gòu)造函數(shù)為包訪問(wèn)權(quán)限，不對(duì)外公開，實(shí)際只是對(duì)LinkedHashSet的支持。 
    //實(shí)際底層會(huì)以指定的參數(shù)構(gòu)造一個(gè)空LinkedHashMap實(shí)例來(lái)實(shí)現(xiàn)。 
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

加載因子指的是能存儲(chǔ)的元素占總的容量的比例。

在 HashMap 中，能夠存儲(chǔ)元素的數(shù)量就是： 總的容量*加載因子 。

每當(dāng)向HashSet新增元素時(shí)，如果HashMap集合中的元素大于前面公式計(jì)算的結(jié)果，就必須要進(jìn)行擴(kuò)容操作，從時(shí)間和空間考慮，加載因子一般都選默認(rèn)的0.75。

2 添加元素

當(dāng)把對(duì)象加入HashSet時(shí)，HashSet會(huì)先計(jì)算對(duì)象的 hashcode 值來(lái)判斷對(duì)象加入的位置，同時(shí)也會(huì)與其他加入的對(duì)象的hashcode值作比較，如果沒(méi)有相符的hashcode，HashSet會(huì)假設(shè)對(duì)象沒(méi)有重復(fù)出現(xiàn)。

但是如果發(fā)現(xiàn)有相同hashcode 值的對(duì)象，這時(shí)會(huì)調(diào)用 equals()方法來(lái)檢查hashcode相等的對(duì)象是否真的相同。如果兩者相同，則覆蓋舊元素。

//將 e 作為 key，PRESENT 作為 value 插入到 map 集合中，如果 e 
	//不存在，則插入成功返回 true;如果存在，則返回false
	//本質(zhì)上是調(diào)用HashMap的put方法來(lái)實(shí)現(xiàn)的
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

3 刪除元素

//刪除成功返回 true，刪除的元素不存在會(huì)返回 false
	//本質(zhì)上是調(diào)用HashMap的remove方法來(lái)實(shí)現(xiàn)的
    public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }

4 查找元素

//調(diào)用 HashMap 的 containsKey(Object o) 方法，找到了返回 true，找不到返回 false
	//因?yàn)镠ashSet的本質(zhì)上是用HashMap來(lái)存儲(chǔ)元素的，HashSet的值是HashMap中的key，所以
	//此處調(diào)用了HashMap的containsKey方法來(lái)判斷
    public boolean contains(Object o) {
        return map.containsKey(o);
    }

5 清空集合/判斷是否為空/獲取HashSet元素個(gè)數(shù)

這幾個(gè)方法都是直接調(diào)用其底層實(shí)現(xiàn)HashMap的方法的，源碼：

//清空集合
    public void clear() {
        map.clear();
    }
	//判斷是否為空
    public boolean isEmpty() {
        return map.isEmpty();
    }
	//獲取集合元素個(gè)數(shù)
    public int size() {
        return map.size();
    }

6 迭代器

//因?yàn)镠ashSet的本質(zhì)上是用HashMap來(lái)存儲(chǔ)元素的，HashSet的值是HashMap中的key，所以
	//此處調(diào)用了HashMap的keySet方法來(lái)遍歷HashSet中的元素
    public Iterator<E> iterator() {
        return map.keySet().iterator();
    }

LinkedHashSet

1 LinkedHashSet是什么

LinkedHashSet是有序集合，其繼承關(guān)系：

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

LinkedHashSet底層是通過(guò)LinkedHashMap來(lái)實(shí)現(xiàn)的，LinkedHashMap其實(shí)也就是value是固定值的LinkedHashMap。

因此LinkedHashSet中的元素順序是可以保證 的，也就是說(shuō)遍歷序和插入序是一致的。

2 LinkedHashSet的特點(diǎn)

• 底層是用LinkedHashMap來(lái)實(shí)現(xiàn)的。
• 線程不安全 。
• 元素有序，是按照插入的順序排序的。
• 最多只能存一個(gè)Null。

3 LinkedHashSet支持按元素訪問(wèn)順序排序嗎

LinkedHashSet所有的構(gòu)造方法都是調(diào)用HashSet的同一個(gè)構(gòu)造方法：

    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

然后，通過(guò)調(diào)用LinkedHashMap的構(gòu)造方法初始化Map：

    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

可以看出：這里把a(bǔ)ccessOrder寫死為false。所以， LinkedHashSet是不支持按訪問(wèn)順序?qū)υ嘏判虻?，只能按插入順序排?。

4 LinkedHashSet常用方法

1、構(gòu)造一個(gè)具有默認(rèn)初始容量（16）和負(fù)載因子（0.75）的LinkedHashSet

public LinkedHashSet()

2、構(gòu)造一個(gè)具有指定初始容量和默認(rèn)負(fù)載因子（0.75）的LinkedHashSet

public HashSet(int initialCapacity)

3、構(gòu)造具有指定的初始容量和負(fù)載因子的LinkedHashSet

public HashSet(int initialCapacity, float loadFactor)

LinkedHashSet源碼

LinkedHashSet源碼很簡(jiǎn)單，大都和其父類HashSet相同，此處只介紹其構(gòu)造方法。

1、LinkedHashSet(int initialCapacity, float loadFactor)

    public LinkedHashSet(int initialCapacity, float loadFactor) {
    	//調(diào)用其父類HashSet的構(gòu)造器，指定初始容量和增長(zhǎng)因子，構(gòu)造一個(gè)LinkedHashMap
        super(initialCapacity, loadFactor, true);
    }

2、LinkedHashSet(int initialCapacity)

    public LinkedHashSet(int initialCapacity) {
    	//調(diào)用其父類HashSet的構(gòu)造器，指定初始容量，增長(zhǎng)因子為0.75，構(gòu)造一個(gè)LinkedHashMap
        super(initialCapacity, .75f, true);
    }

3、public LinkedHashSet()

    public LinkedHashSet() {
    	//調(diào)用其父類HashSet的構(gòu)造器，初始容量為16，增長(zhǎng)因子為0.75，構(gòu)造一個(gè)LinkedHashMap
        super(16, .75f, true);
    }

TreeSet

1 TreeSet是什么

TreeSet是一個(gè)有序集合，基于TreeMap實(shí)現(xiàn)。

TreeSet的繼承關(guān)系：

public class TreeSet<E> extends AbstractSet<E>
    	implements NavigableSet<E>, Cloneable, java.io.Serializable

2 TreeSet特點(diǎn)

• TreeSet支持元素的自然排序和按照在創(chuàng)建時(shí)指定的Comparator比較器進(jìn)行排序。
  • TreeSet()是使用二叉樹的原理對(duì)新 add()的對(duì)象按照指定的順序排序（升序、降序），每增加一個(gè)對(duì)象都會(huì)進(jìn)行排序，將對(duì)象插入的二叉樹指定的位置。
  • TreeSet中要存儲(chǔ)自定義類的對(duì)象時(shí)， 自己定義的類必須實(shí)現(xiàn) Comparable 接口，并且覆寫相應(yīng)的 compareTo()函數(shù)，才可以正常使用。
  • 當(dāng)自定義對(duì)象之間進(jìn)行比較時(shí)，如果該對(duì)象小于、等于或大于指定對(duì)象，則分別返回負(fù)整數(shù)、零或正整數(shù)。
• TreeSet的基本操作（add、remove 和 contains）的時(shí)間復(fù)雜度是log(n) 。
• TreeSet是非線程安全的。
• TreeSet的迭代器是fail-fast策略的。
• TreeSet中元素不允許為Null，不允許重復(fù)值。

3 TreeSet常用方法

構(gòu)造方法

//創(chuàng)建一個(gè)空的 TreeSet，使用自然排序
	public TreeSet()
	//指定比較器，如果比較器是 null 將使用自然排序
	public TreeSet(Comparator<? super E> comparator)

添加元素

//添加一個(gè)元素
	public boolean add(E e)
	//添加集合中的元素
	public  boolean addAll(Collection<? extends E> c)

刪除元素

    public boolean remove(Object o)

查找元素

    public boolean contains(Object o)

獲取TreeSet元素個(gè)數(shù)/判斷TreeSet是否為空/清空TreeSet

//獲取TreeSet元素個(gè)數(shù)
    public int size()
	//判斷TreeSet是否為空
    public boolean isEmpty()
	//清空TreeSet
    public void clear()

返回此TreeSet中存在的最大元素/最小元素

//返回此TreeSet中存在的最大元素
    public E last() {
        return m.lastKey();
    }
	//返回此TreeSet中存在的最小元素
    public E first() {
        return m.firstKey();
    } 

返回此集合中小于某個(gè)元素的最大的元素

    public E lower(E e)

返回此集合中大于某個(gè)元素的最小的元素

    public E higher(E e)

floor/ceiling

//返回在這個(gè)集合中小于或者等于給定元素的最大元素
    public E floor(E e)
	//返回在這個(gè)集合中大于或者等于給定元素的最小元素
    public E ceiling(E e)

檢索和刪除最?。ǖ谝粋€(gè)）元素

    public E pollFirst()

檢索和刪除最大（最后）元素

    public E pollLast()

TreeSet源碼

//存儲(chǔ)數(shù)據(jù)的底層數(shù)據(jù)結(jié)構(gòu)
    private transient NavigableMap<E,Object> m;
    //由于 TreeSet 只需要使用 Key 進(jìn)行存儲(chǔ)，因此 Value 存儲(chǔ)的是一個(gè)虛擬值
    private static final Object PRESENT = new Object();

1、構(gòu)造方法

    //使用 TreeMap 創(chuàng)建一個(gè)空的 TreeSet，使用自然排序，
    //添加的元素需要實(shí)現(xiàn) Comparable 接口，即是可比較的
    public TreeSet() {
        this(new TreeMap<E,Object>());
    }
    //指定比較器，如果比較器是 null 將使用自然排序
    public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));
    }
    //構(gòu)建一個(gè)treeSet，包含參數(shù)c中的元素，排序是基于元素的自然順序
    public TreeSet(Collection<? extends E> c) {
        this();
        addAll(c);
    }

2、添加元素 調(diào)用TreeMap中的put()方法進(jìn)行添加元素。

    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }

將集合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<?> cc = 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);
    }

3、刪除元素

調(diào)用TreeMap中的remove()方法來(lái)刪除TreeSet中的元素，若set中存在要?jiǎng)h除的元素，刪除，返回true，不存在，返回false。

內(nèi)部調(diào)用navigableMap的remove方法，因?yàn)閠reeMap是其實(shí)現(xiàn)類，所以實(shí)際執(zhí)行的時(shí)候，調(diào)用的是treeMap的remove方法。

    public boolean remove(Object o) {
        return m.remove(o)==PRESENT;
    }

4、查找元素 若set中存在該元素，返回true，不存在，返回false。

    public boolean contains(Object o) {
        return m.containsKey(o);
    }

5、獲取TreeSet元素個(gè)數(shù)/判斷TreeSet是否為空/清空TreeSet

//獲取TreeSet元素個(gè)數(shù)
    public int size() {
        return m.size();
    }
	//判斷TreeSet是否為空
    public boolean isEmpty() {
        return m.isEmpty();
    }
	//清空TreeSet
    public void clear() {
        m.clear();
    }

6、返回此TreeSet中存在的最大元素/最小元素

//返回此TreeSet中存在的最大元素
    public E last() {
        return m.lastKey();
    }
	//返回此TreeSet中存在的最小元素
    public E first() {
        return m.firstKey();
    } 

7、返回此集合中小于某個(gè)元素的最大的元素 返回此集合中最大的元素，該元素嚴(yán)格小于給定的元素。如果此TreeSet集合中不存在這樣的元素，則此方法返回Null。

    public E lower(E e) {
        return m.lowerKey(e);
    }

8、返回此集合中大于某個(gè)元素的最小的元素 從集合中返回指定元素中最接近的最大元素，如果沒(méi)有，則返回Null。

    public E higher(E e) {
        return m.higherKey(e);
    }

9、floor/ceiling

floor(E e)方法返回在這個(gè)集合中小于或者等于給定元素的最大元素，如果不存在這樣的元素，返回null。

ceiling(E e)方法返回在這個(gè)集合中大于或者等于給定元素的最小元素，如果不存在這樣的元素，返回null。

    public E floor(E e) {
        return m.floorKey(e);
    }
    public E ceiling(E e) {
        return m.ceilingKey(e);
    }

10、檢索和刪除最?。ǖ谝粋€(gè)）元素

    public E pollFirst() {
        Map.Entry<E,?> e = m.pollFirstEntry();
        return (e == null) ? null : e.getKey();
    }

11、檢索和刪除最大（最后）元素

    public E pollLast() {
        Map.Entry<E,?> e = m.pollLastEntry();
        return (e == null) ? null : e.getKey();
    }

到此這篇關(guān)于Java集合之Set、HashSet、LinkedHashSet和TreeSet深度解析的文章就介紹到這了,更多相關(guān)Java的set集合內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論