Java中的集合Set – 入門篇

前言

大家好啊，我是湯圓，今天給大家帶來的是《Java中的集合Set – 入門篇》，希望對大家有幫助，謝謝

簡介

前面介紹了集合List，映射Map，最後再簡單介紹下集合Set，相關類如下圖所示

集合

正文

Set從外面看像List（都是存儲單一數據的集合），只不過存儲的數據不會有重複；
但是裡面卻是Map映射（因為它記憶體存儲是基於Map結構實現），這也是為什麼把Set放到Map後面來說的原因。

Set和Map有什麼關係呢？

因為Map的鍵不會有重複，所以Set就利用了Map的這個特點，將其作為內部成員變數來使用
比如我們看下HashSet內部的源碼，可以看到，基本上所有操作都是基於其內部的成員變數HashMap進行的

    
    private transient HashMap<E,Object> map;
    // 這個常量只是為了適配Map的鍵值對結構，無實際意義
    private static final Object PRESENT = new Object();

    public HashSet() {
        map = new HashMap<>();
    }

    public int size() {
        return map.size();
    }

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

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

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

Set的種類

Set的種類類似Map
Set主要有三種類型：HashSet(常用)、TreeSet（樹形結構）、LinkedHashSet（前兩者的結合）

我們先來看一下Set介面主要的幾個方法：

  • boolean add(E e)：往Set中添加元素
  • boolean contains(Object o)：查詢Set是否包含指定對象
  • boolean remove(Object o)：從Set中刪除指定對象
  • int size()：返回Set的元素數量

下面我們簡單看下三者的區別

HashSet TreeSet LinkedHashSet
訪問速度 快 慢 適中
元素是否有序 無序 有序，默認升序 有序，默認按插入的順序
適用場景 為快速查詢而設計（用的最多） 需要排序的場景 需要保證查詢和插入順序一致的場景

接下來我們以HashSet為例，來介紹Set介面

HashSet

HashSet是一個無序集合
因為它內部是基於HashMap實現

上面的源碼我們有看到，HashSet每插入一個元素，就將該元素作為內部hashMap的key，然後常量Object作為hashMap的value，存儲到hashMap中

  • 如果元素的hash值沒有重複，就按照數組的方式依次排列；
  • 如果hash值有重複的，就添加到已有的值對後面，形成鏈表結構；

整體結構 如下圖所示

HashSet結構圖

下面用程式碼示範一下

public class SetDemo {
    public static void main(String[] args) {
        // 初始化
        Set<Integer> set = new HashSet<>();
        // 添加元素
        set.add(10);
        // 元素數量
        int size = set.size();
        System.out.println(size);
        // 查詢元素是否存在
        boolean isContain = set.contains(10);
        System.out.println(set);
        // 刪除
        set.remove(10);
        System.out.println(set);
    }
}

TreeSet

TreeSet在插入的時候，可以按照元素進行排序（默認升序）

它適合用在排序比較多的場景，性能會比HashSet差一些

下面用程式碼示範一下（重點要來了）

public class SetDemo {
    public static void main(String[] args) {
      
        // TreeSet
        B b = new B();
        // 初始化
        Set<B> set2 = new TreeSet<>();
        // 添加元素
        set2.add(b);
        // 元素數量
        int size2 = set2.size();
        System.out.println(size2);
        // 查詢元素是否存在
        boolean isContain2 = set2.contains(b);
        System.out.println(set2);
        // 刪除
        set2.remove(b);
        System.out.println(set2);
    }
}
class B{

}

這段程式碼看似一切正常，實則暗藏玄機

如果你運行這段程式碼，會報出下面的錯誤提示：類B不能轉換為Comparable。

TreeSet報錯 Comparable

可是為什麼要轉換呢？我也沒有轉換啊

那是因為內部自動轉換了

TreeSet啥時候會自動將元素類轉為Comparable呢？

是在你插入第一個數據開始，內部就已經開始在做比較了（第一次先自己跟自己做比較，目的就是檢查你這個數據有沒有實現Comparable介面）；

後面每插一個數據，都要從根節點開始挨個比較排序

這其實也算也是TreeSet內部排序的工作原理

所以上面這段程式碼需要讓B實現Comparable介面，改後如下所示

public class SetDemo {
    public static void main(String[] args) {
        // TreeSet
        B b = new B();
        // 初始化
        Set<B> set2 = new TreeSet<>();
        // 添加元素
        // 此時運行沒問題
        set2.add(b);
        // 元素數量
        int size2 = set2.size();
        System.out.println(size2);
        // 查詢元素是否存在
        boolean isContain2 = set2.contains(b);
        System.out.println(set2);
        // 刪除
        set2.remove(b);
        System.out.println(set2);
    }
}
// 這裡實現了Comparable
class B implements Comparable{
    @Override
    public int compareTo(Object o) {
        return this.hashCode()>o.hashCode() ? 1 : -1;
    }
}

此時運行就沒問題了

那為什麼TreeMap沒有這個問題呢？

其實TreeMap也有這個問題，只是TreeMap的鍵key一般都是字元串或者整型，而字元串和整型對象內部已經實現了Comparable介面，所以問題不大（因為用自定義對象做鍵key的畢竟還是少數）

LinkedHashSet

LinkedHashSet擁有HashSet的大部分優點，且保證了插入的順序，使得在查詢的時候，可以按照插入的順序依次讀取（原理是鏈表）

這裡要注意一點：在Java程式語言設計中，所有的鏈表都是雙向鏈表，即每個節點還存放著一個指向前節點的引用

大致的結構圖如下所示(之前的LinkedHashMap忘記貼圖了，跟這個類似，只是元素內容不同）：

LinkedHashSet結構圖

三者的排序比較

參考上一篇映射Map，Set排序比較表現出來的行為與Map一致

總結

Set一般用到的有HashSet，TreeSet，LinkedHashSet，內部都是無重複元素

  • HashSet的插入和訪問都很快，但是內部是無序排列

  • TreeSet的插入和訪問都很慢，但是內部是有序排列，默認按升序排列

  • LinkedHashSet擁有HashSet的大部分優點，而且還可以按照元素插入的順序來訪問元素，但是性能會比HashSet差

後記

最後，感謝大家的觀看，謝謝

Tags:

VirMach 便宜 VPS

QNews

QNews