電腦程式的思維邏輯 (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
  • WPF 已知問題 監聽 WMI 事件導致觸摸失效
    示例項目結構 在 Visual Studio 中創建一個 WinForms 應用程式後，項目結構如下所示： MyWinFormsApp/ │ ├───Properties/ │ └───Settings.settings │ ├───bin/ │ ├───Debug/ │ └───Release/ ...
  • [STAThread]特性
    [STAThread] 特性用於需要與 COM 組件交互的應用程式，尤其是依賴單線程模型（如 Windows Forms 應用程式）的組件。在 STA 模式下，線程擁有自己的消息迴圈，這對於處理用戶界面和某些 COM 組件是必要的。 [STAThread] static void Main(stri ...
  • UWP WinUI3 傳入 AddHandler 的 RoutedEventHandler 類型與事件所需不匹配將拋出參數異常
    在WinForm中使用全局異常捕獲處理 在WinForm應用程式中，全局異常捕獲是確保程式穩定性的關鍵。通過在Program類的Main方法中設置全局異常處理，可以有效地捕獲並處理未預見的異常，從而避免程式崩潰。 註冊全局異常事件 [STAThread] static void Main() { / ...
  • .NET 多版本 WinForm 開源控制項庫 SunnyUI
    前言 給大家推薦一款開源的 Winform 控制項庫，可以幫助我們開發更加美觀、漂亮的 WinForm 界面。 項目介紹 SunnyUI.NET 是一個基於 .NET Framework 4.0+、.NET 6、.NET 7 和 .NET 8 的 WinForm 開源控制項庫，同時也提供了工具類庫、擴展 ...
  • .net core8 使用Swagger（附當前源碼）
    說明 該文章是屬於OverallAuth2.0系列文章，每周更新一篇該系列文章（從0到1完成系統開發）。 該系統文章，我會儘量說的非常詳細，做到不管新手、老手都能看懂。 說明：OverallAuth2.0 是一個簡單、易懂、功能強大的許可權+可視化流程管理系統。 有興趣的朋友，請關註我吧(*^▽^*) ...
  • WPF 什麼時候 VisualTreeHelper.GetDescendantBounds 將返回無窮大
    一、下載安裝 1.下載git 必須先下載並安裝git，再TortoiseGit下載安裝 git安裝參考教程：https://blog.csdn.net/mukes/article/details/115693833 2.TortoiseGit下載與安裝 TortoiseGit，Git客戶端，32/6 ...
  • C# 開源教程帶你輕鬆掌握數據結構與演算法
    前言 在項目開發過程中，理解數據結構和演算法如同掌握蓋房子的秘訣。演算法不僅能幫助我們編寫高效、優質的代碼，還能解決項目中遇到的各種難題。 給大家推薦一個支持C#的開源免費、新手友好的數據結構與演算法入門教程：Hello演算法。 項目介紹 《Hello Algo》是一本開源免費、新手友好的數據結構與演算法入門 ...
  • 第22篇 生成proto文件bat腳本
    1.生成單個Proto.bat內容 @rem Copyright 2016, Google Inc. @rem All rights reserved. @rem @rem Redistribution and use in source and binary forms, with or with ...
  • 記一次 .NET某上位機視覺程式 卡死分析
    一：背景 1. 講故事 前段時間有位朋友找到我，說他的窗體程式在客戶這邊出現了卡死，讓我幫忙看下怎麼回事？dump也生成了，既然有dump了那就上 windbg 分析吧。 二：WinDbg 分析 1. 為什麼會卡死 窗體程式的卡死，入口門檻很低，後續往下分析就不一定了，不管怎麼說先用 !clrsta ...
  • 醫學DICOM文件與PACS系統進行數據傳輸
    前言 人工智慧時代，人臉識別技術已成為安全驗證、身份識別和用戶交互的關鍵工具。 給大家推薦一款.NET 開源提供了強大的人臉識別 API，工具不僅易於集成，還具備高效處理能力。 本文將介紹一款如何利用這些API，為我們的項目添加智能識別的亮點。 項目介紹 GitHub 上擁有 1.2k 星標的 C# ...
所有分類