電腦程式的思維邏輯 (44) - 剖析TreeSet

来源:http://www.cnblogs.com/swiftma/archive/2016/10/24/5992093.html
-Advertisement-
Play Games

本節介紹TreeSet，相比HashSet，它有什麼不同？除了Set介面，它實現的SortedSet和NavigatableSet介面有哪些方法？它內部是如何實現的？... ...


41節介紹了HashSet，我們提到，HashSet有一個重要局限，元素之間沒有特定的順序，我們還提到，Set介面還有另一個重要的實現類TreeSet，它是有序的，與HashSet和HashMap的關係一樣，TreeSet是基於TreeMap的，上節我們介紹了TreeMap，本節我們來詳細討論TreeSet。

下麵，我們先來看TreeSet的用法，然後看實現原理，最後總結分析TreeSet的特點。

基本用法

構造方法

TreeSet的基本構造方法有兩個：

public TreeSet()
public TreeSet(Comparator<? super E> comparator)

預設構造方法假定元素實現了Comparable介面，第二個使用傳入的比較器，不要求元素實現Comparable。

基本例子

TreeSet經常也只是當做Set使用，只是希望迭代輸出有序，如下麵代碼所示：

Set<String> words = new TreeSet<String>();
words.addAll(Arrays.asList(new String[]{
    "tree", "map", "hash", "map",     
}));
for(String w : words){
    System.out.print(w+" ");
}

輸出為：

hash map tree

TreeSet實現了兩點：排重和有序。

如果希望不同的排序，可以傳遞一個Comparator，如下所示：

Set<String> words = new TreeSet<String>(new Comparator<String>(){

    @Override
    public int compare(String o1, String o2) {
        return o1.compareToIgnoreCase(o2);
    }});
words.addAll(Arrays.asList(new String[]{
    "tree", "map", "hash", "Map",     
}));
System.out.println(words);

忽略大小寫進行比較，輸出為：

[hash, map, tree]

需要註意的是，Set是排重的，排重是基於比較結果的，結果為0即視為相同，"map"和"Map"雖然不同，但比較結果為0，所以只會保留第一個元素。

以上就是TreeSet的基本用法，簡單易用。不過，因為有序，TreeSet還實現了NavigableSet和SortedSet介面，NavigableSet擴展了SortedSet，此外，TreeSet還有幾個構造方法，我們來看下。

高級用法

SortedSet介面

SortedSet介面與SortedMap介面類似，具體定義為：

public interface SortedSet<E> extends Set<E> {
    Comparator<? super E> comparator();
    SortedSet<E> subSet(E fromElement, E toElement);
    SortedSet<E> headSet(E toElement);
    SortedSet<E> tailSet(E fromElement);
    E first();
    E last();
}

first()返回第一個元素，last()返回最後一個，headSet/tailSet/subSet都返回一個視圖，包括原Set中的一定取值範圍的元素，區別在於範圍：

  • headSet：嚴格小於toElement的所有元素
  • tailSet: 大於等於fromElement的所有元素
  • subSet: 大於等於fromElement，且小於toElement的所有元素 

與之前介紹的視圖概念一樣，對返回視圖的操作會直接影響原Set。

comparator()返回使用的比較器，如果沒有自定義的比較器，返回值為null。

我們來看一段簡單的示例代碼，以增強直觀感受，輸出用註釋說明：

SortedSet<String> set = new TreeSet<String>();
set.addAll(Arrays.asList(new String[]{
    "c", "a", "b", "d","f"    
}));

System.out.println(set.first()); //a
System.out.println(set.last()); //f
System.out.println(set.headSet("b"));//[a]
System.out.println(set.tailSet("d"));//[d, f]
System.out.println(set.subSet("b", "e")); //[b, c, d]
set.subSet("b", "e").clear(); //會從原set中刪除
System.out.println(set); //[a, f]

NavigableSet介面

與NavigableMap類似，NavigableSet介面擴展了SortedSet，主要增加了一些查找鄰近元素的方法，比如：

E floor(E e); //返回小於等於e的最大元素
E lower(E e); // 返回小於e的最大元素
E ceiling(E e); //返回大於等於e的最小元素
E higher(E e); //返回大於e的最小元素

相比SortedSet中的視圖方法，NavigableSet增加了一些方法，以更為明確的方式指定返回值中是否包含邊界值，如：

NavigableSet<E> headSet(E toElement, boolean inclusive);
NavigableSet<E> tailSet(E fromElement, boolean inclusive);
NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                           E toElement,   boolean toInclusive);

NavigableSet也增加了兩個對頭尾的操作：

E pollFirst(); //返回並刪除第一個元素
E pollLast(); //返回並刪除最後一個元素

此外，NavigableSet還有如下方法，以方便逆序訪問：

NavigableSet<E> descendingSet();
Iterator<E> descendingIterator();

我們來看一段簡單的示例代碼，以增強直觀感受，輸出用註釋說明：

NavigableSet<String> set = new TreeSet<String>();
set.addAll(Arrays.asList(new String[]{
    "c", "a", "b", "d","f"    
}));
System.out.println(set.floor("a")); //a
System.out.println(set.lower("b")); //a
System.out.println(set.ceiling("d"));//d
System.out.println(set.higher("c"));//d
System.out.println(set.subSet("b", true, "d", true)); //[b, c, d]
System.out.println(set.pollFirst()); //a
System.out.println(set.pollLast()); //f
System.out.println(set.descendingSet()); //[d, c, b]

其他構造方法

TreeSet的其他構造方法為：

public TreeSet(Collection<? extends E> c)
public TreeSet(SortedSet<E> s)
TreeSet(NavigableMap<E,Object> m)

前兩個都是以一個已有的集合為參數，將其中的所有元素添加到當前TreeSet，區別在於，在第一個中，比較器為null，假定元素實現了Comparable介面，而第二個中，比較器設為和參數SortedSet中的一樣。

第三個不是public的，是內部用的。

基本實現原理

41節介紹過，HashSet是基於HashMap實現的，元素就是HashMap中的鍵，值是一個固定的值，TreeSet是類似的，它是基於TreeMap實現的，我們具體來看一下代碼，先看其內部組成。

內部組成

TreeSet的內部有如下成員：

private transient NavigableMap<E,Object> m;
private static final Object PRESENT = new Object();

m就是背後的那個TreeMap，這裡用的是更為通用的介面類型NavigableMap，PRESENT就是那個固定的共用值。

TreeSet的方法實現主要就是調用m的方法，我們具體來看下。

構造方法

幾個構造方法的代碼為：

TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}

public TreeSet() {
    this(new TreeMap<E,Object>());
}

public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}

public TreeSet(Collection<? extends E> c) {
    this();
    addAll(c);
}

public TreeSet(SortedSet<E> s) {
    this(s.comparator());
    addAll(s);
}

代碼都比較簡單，就不解釋了。

添加元素

add方法的代碼為：

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

就是調用map的put方法，元素e用作鍵，值就是固定值PRESENT，put返回null表示原來沒有對應的鍵，添加成功了。

檢查是否包含元素

代碼為：

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

就是檢查map中是否包含對應的鍵。

刪除元素

代碼為：

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

就是調用map的remove方法，返回值為PRESENT表示原來有對應的鍵且刪除成功了。

子集視圖

subSet方法的代碼：

public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                              E toElement,   boolean toInclusive) {
    return new TreeSet<>(m.subMap(fromElement, fromInclusive,
                                   toElement,   toInclusive));
}

先調用subMap方法獲取NavigatebleMap的子集，然後調用內部的TreeSet構造方法。

頭尾操作

代碼為：

public E first() {
    return m.firstKey();
}

public E last() {
    return m.lastKey();
}

 

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

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

代碼都比較簡單，就不解釋了。

逆序遍歷

代碼為：

public Iterator<E> descendingIterator() {
    return m.descendingKeySet().iterator();
}

public NavigableSet<E> descendingSet() {
    return new TreeSet<>(m.descendingMap());
}

也很簡單。

實現原理小結

TreeSet的實現代碼都比較簡單，主要就是調用內部NavigatableMap的方法。

TreeSet特點分析

與HashSet相比，TreeSet同樣實現了Set介面，但內部基於TreeMap實現，而TreeMap基於大致平衡的排序二叉樹 - 紅黑樹，這決定了它有如下特點：

  • 沒有重覆元素
  • 添加、刪除元素、判斷元素是否存在，效率比較高，為O(log2(N))，N為元素個數。
  • 有序，TreeSet同樣實現了SortedSet和NavigatableSet介面，可以方便的根據順序進行查找和操作，如第一個、最後一個、某一取值範圍、某一值的鄰近元素等。
  • 為了有序，TreeSet要求元素實現Comparable介面或通過構造方法提供一個Comparator對象。

小結

本節介紹了TreeSet的用法和實現原理，在用法方面，它實現了Set介面，但有序，同樣實現了SortedSet和NavigatableSet介面，在內部實現上，它使用了TreeMap，代碼比較簡單。

至此，我們已經介紹完了Java中主要常見的容器介面和實現類，介面主要有隊列(Queue)，雙端隊列(Deque)，列表(List)，Map和Set，實現類有ArrayList, LinkedList, HashMap, TreeMap, HashSet和TreeSet。

關於介面Queue, Deque, Map和Set，Java容器類中還有其他一些實現類，它們各有特點，讓我們在接下來的幾節中繼續探索。

---------------

未完待續，查看最新文章，敬請關註微信公眾號“老馬說編程”(掃描下方二維碼)，從入門到高級，深入淺出，老馬和你一起探索Java編程及電腦技術的本質。用心原創，保留所有版權。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 魔獸世界之一：備戰
    來源: POJ 註意： 總時間限制: 1000ms 記憶體限制: 65536kB 描述 魔獸世界的西面是紅魔軍的司令部，東面是藍魔軍的司令部。兩個司令部之間是依次排列的若幹城市。 紅司令部，City 1，City 2，……，City n，藍司令部 兩軍的司令部都會製造武士。武士一共有 dragon 、 ...
  • 關於C語言結構體，指針，聲明的詳細講解。——Arvin
    關於結構體的詳細分析 只定義結構體 是結構體的名字 定義結構體變數 定義結構體並同時定義結構體變數 關於指針的詳細分析 定義指針變數： 定義指針的指針變數： 賦初值： 關於 和`int p`區別： 如果是c,我推薦 這樣的寫法因為變數定義需要放在函數開始的地方. 如果是c++,我推薦 分行寫並初始化 ...
  • Python開發程式：選課系統-改良版
    程式名稱: 選課系統 角色:學校、學員、課程、講師要求:1. 創建北京、上海 2 所學校2. 創建linux , python , go 3個課程 ， linux\py 在北京開， go 在上海開3. 課程包含，周期，價格，通過學校創建課程 4. 通過學校創建班級， 班級關聯課程、講師5. 創建學員 ...
  • Java --ClassLoader創建、載入class、卸載class
    一、java提供了三種ClassLoader對Class進行載入： 1.BootStrap ClassLoader：稱為啟動類載入器，是Java類載入層次中最頂層的類載入器，負責載入JDK中的核心類庫，如：rt.jar、resources.jar、charsets.jar等，可通過如下程式獲得該類加 ...
  • 【Java每日一題】20161024
    20161021問題解析請點擊今日問題下方的“【Java每日一題】20161024”查看 今日問題： 請問主程式輸出結果是？（點擊以下“【Java每日一題】20161024”查看20161021問題解析） 題目原發佈於公眾號、簡書：【Java每日一題】20161024，【Java每日一題】20161 ...
  • php中 === 的使用
    當比較簡單類型時(如String int float bool),判斷的是"相等 && 類型一樣" 比較對象時，判斷的是"是否指向同一個對象" ...
  • 【leetcode❤python】 257. Binary Tree Paths
    深度優先搜索 # Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: ...
  • (二）OJ的主要文件
    OJ搭建好了後，我們要熟悉一下OJ項目下的文件及文件夾。 首先，安裝好的OJ是在目錄var/www/html下。 html下的php文件 這些php文件都是些主要跳轉頁面。 admin文件夾 登錄管理員賬號後管理的管理界面 bootstrap文件夾 css樣式和圖片，如果要修改某些頁面的小地方請到w ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類