進程管理控制

這裏實現的是一個自定義timer用於統計子進程運行的時間。使用方式主要是

timer [-t seconds] command arguments

例如要統計ls的運行時間可以直接輸入timer ls，其後的arguments是指所要運行的程序的參數。如：timer ls -al。如果要指定程序運行多少時間，如5秒鐘，可以輸入timer -t 5 ls -al。需要注意的是，該程序對輸入沒有做異常檢測，所以要確保程序輸入正確。

Linux

程序思路

1. 獲取時間

   時間獲取函數使用gettimeofday，精度可以達到微秒

   struct timeval{
        long tv_sec;*//秒*
        long tv_usec;*//微秒*
   }

2. 子進程創建

   1. fork()函數

      #include <sys/types.h>
      #include <unistd.h>
      pid_t fork(void);

      fork調用失敗則返回-1，調用成功則：

      fork函數會有兩種返回值，一是為0，一是為正整數。若為0，則說明當前進程為子進程；若為正整數，則該進程為父進程且該值為子進程pid。關於進程控制的詳細說明請參考：

   2. exec函數

      用fork創建子進程后執行的是和父進程相同的程序（但有可能執行不同的代碼分支），子進程往往要調用一種exec函數以執行另一個程序。當進程調用一種exec函數時，該進程的用戶空間代碼和數據完全被新程序替換，從新程序的啟動例程開始執行。調用exec並不創建新進程，所以調用exec前後該進程的id並未改變。
      其實有六種以exec開頭的函數，統稱exec函數：

      #include <unistd.h>
      int execl(const char *path, const char *arg, ...);
      int execlp(const char *file, const char *arg, ...);
      int execle(const char *path, const char *arg, ..., char *const envp[]);
      int execv(const char *path, char *const argv[]);
      int execvp(const char *file, char *const argv[]);
      int execve(const char *path, char *const argv[], char *const envp[]);

      這些函數如果調用成功則加載新的程序從啟動代碼開始執行，不再返回，如果調用出錯則返回-1，所以exec函數只有出錯的返回值而沒有成功的返回值。

   3. wait與waitpid

      一個進程在終止時會關閉所有文件描述符，釋放在用戶空間分配的內存，但它的PCB還保留着，內核在其中保存了一些信息：如果是正常終止則保存着退出狀態，如果是異常終止則保存着導致該進程終止的信號是哪個。這個進程的父進程可以調用wait或waitpid獲取這些信息，然後徹底清除掉這個進程。我們知道一個進程的退出狀態可以在Shell中用特殊變量$?查看，因為Shell是它的父進程，當它終止時Shell調用wait或waitpid得到它的退出狀態同時徹底清除掉這個進程。
      如果一個進程已經終止，但是它的父進程尚未調用wait或waitpid對它進行清理，這時的進程狀態稱為殭屍（Zombie）進程。任何進程在剛終止時都是殭屍進程，正常情況下，殭屍進程都立刻被父進程清理了。
      殭屍進程是不能用kill命令清除掉的，因為kill命令只是用來終止進程的，而殭屍進程已經終止了。

   #include <sys/types.h>
   #include <sys/wait.h>
   pid_t wait(int *status);
   pid_t waitpid(pid_t pid, int *status, int options);

   若調用成功則返回清理掉的子進程id，若調用出錯則返回-1。父進程調用wait或waitpid時可能會：

   • 阻塞（如果它的所有子進程都還在運行

   • 帶子進程的終止信息立即返回（如果一個子進程已終止，正等待父進程讀取其終止信息）

   • 出錯立即返回（如果它沒有任何子進程）

   這兩個函數的區別是：

   • 如果父進程的所有子進程都還在運行，調用wait將使父進程阻塞，而調用waitpid時如果在options參數中指定WNOHANG可以使父進程不阻塞而立即返回0
   • wait等待第一個終止的子進程，而waitpid可以通過pid參數指定等待哪一個子進程

​

源代碼

timer源代碼

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <unistd.h>
#include <wait.h>
#include <ctime>
#include <iostream>
#include <cstring>
//程序假定輸入完全正確，沒有做異常處理
//mytime [-t number] 程序
using namespace std;
//調用系統時間
struct timeval time_start;
struct timeval time_end;

void printTime();

void newProcess(const char *child_process, char *argv[], double duration);

int main(int argc, char const *argv[])
{
    double duration = 0;
    char **arg;
    int step = 2;
    if (argc > 3 && (strcmp((char *)"-t", argv[1]) == 0)) //如果指定了運行時間
    {
        step = 4;
        duration = atof(argv[2]); //沒有做異常處理
    }

    arg = new char *[argc - step + 1];
    for (int i = 0; i < argc - step; i++)
    {
        arg[i] = new char[100];
        strcpy(arg[i], argv[i + step]);
    }
    arg[argc - step] = NULL;

    newProcess(argv[step - 1], arg, duration);
    return 0;
}

void printTime()
{
    //用以記錄進程運行的時間
    int time_use = 0;  // us
    int time_left = 0; // us
    int time_hour = 0, time_min = 0, time_sec = 0, time_ms = 0, time_us = 0;
    gettimeofday(&time_end, NULL);

    time_use = (time_end.tv_sec - time_start.tv_sec) * 1000000 + (time_end.tv_usec - time_start.tv_usec);
    time_hour = time_use / (60 * 60 * (int)pow(10, 6));
    time_left = time_use % (60 * 60 * (int)pow(10, 6));
    time_min = time_left / (60 * (int)pow(10, 6));
    time_left %= (60 * (int)pow(10, 6));
    time_sec = time_left / ((int)pow(10, 6));
    time_left %= ((int)pow(10, 6));
    time_ms = time_left / 1000;
    time_left %= 1000;
    time_us = time_left;
    printf("此程序運行的時間為：%d 小時, %d 分鐘, %d 秒, %d 毫秒, %d 微秒\n", time_hour, time_min, time_sec, time_ms, time_us);
}

void newProcess(const char* child_process, char **argv, double duration)
{
    pid_t pid = fork();
    if (pid < 0) //出錯
    {
        printf("創建子進程失敗！");
        exit(1);
    }
    if (pid == 0) //子進程
    {
        execvp(child_process, argv);
    }
    else
    {
        if (abs(duration - 0) < 1e-6)
        {
            gettimeofday(&time_start, NULL);
            wait(NULL); //等待子進程結束
            printTime();
        }
        else
        {
            gettimeofday(&time_start, NULL);
            // printf("sleep: %lf\n", duration);
            waitpid(pid, NULL, WNOHANG);
            usleep(duration * 1000000); // sec to usec
            int kill_ret_val = kill(pid, SIGKILL);
            if (kill_ret_val == -1) // return -1, fail
            {
                printf("kill failed.\n");
                perror("kill");
            }
            else if (kill_ret_val == 0) // return 0, success
            {
                printf("process %d has been killed\n", pid);
            }
            printTime();
        }
    }
}

測試源代碼

#include <iostream>
#include <ctime>
#include <unistd.h>
using namespace std;
int main(int argc, char const *argv[])
{
    for(int n = 0; n < argc; n++)
    {
        printf("arg[%d]:%s\n",n, argv[n]);
    }
    sleep(5);
    return 0;
}

測試

1. 自行編寫程序測試

2. 系統程序測試

3. 將timer加入環境變量

   這裏僅進行了臨時變量修改。

Windows

在Windows下進行父子進程的創建和管理在api調用上相較Linux有一定難度，但實際上在使用管理上比Linux容易的多。

CreateProcess

#include <Windows.h>
BOOL CreateProcessA(
  LPCSTR                lpApplicationName,
  LPSTR                 lpCommandLine,
  LPSECURITY_ATTRIBUTES lpProcessAttributes,
  LPSECURITY_ATTRIBUTES lpThreadAttributes,
  BOOL                  bInheritHandles,
  DWORD                 dwCreationFlags,
  LPVOID                lpEnvironment,
  LPCSTR                lpCurrentDirectory,
  LPSTARTUPINFOA        lpStartupInfo,
  LPPROCESS_INFORMATION lpProcessInformation
);

源代碼實現

timer程序

// 進程管理.cpp : 此文件包含 "main" 函數。程序執行將在此處開始並結束。
//

#include <iostream>
#include <wchar.h>
#include <Windows.h>
#include <tchar.h>
using namespace std;


void printTime(SYSTEMTIME* start, SYSTEMTIME* end);
void newProcess(TCHAR* cWinDir, double duration);

int _tmain(int argc, TCHAR *argv[])
{
    TCHAR* cWinDir = new TCHAR[MAX_PATH];
    memset(cWinDir, sizeof(TCHAR) * MAX_PATH, 0);

    printf("argc:   %d\n", argc);

    int step = 1;
    double duration = 0;
    if (argc > 1)
    {
        if (argv[1][0] == TCHAR('-') && argv[1][1] == TCHAR('t') && argv[1][2] == TCHAR('\0'))
        {
            step = 3;
            duration = atof((char*)argv[2]);
        }
    }
    //printf("printf content start: %ls\n", argv[1]);
    int j = 0;
    for (int i = 0, h = 0; i < argc - step; i++)
    {
        wcscpy_s(cWinDir + j, MAX_PATH - j, argv[i + step]);
        for (h = 0; argv[i + step][h] != TCHAR('\0'); h++);
        j += h;
        cWinDir[j++] = ' ';
        //printf("%d : %d\n", i, j);
        //printf("printf content start: %ls\n", cWinDir);
    }
    cWinDir[j - 2] = TCHAR('\0');
    //printf("printf content start: %ls\n", cWinDir);

    newProcess(cWinDir,duration);

    return 0;
}


void printTime(SYSTEMTIME* start, SYSTEMTIME* end)
{
    int hours = end->wHour - start->wHour;
    int minutes = end->wMinute - start->wMinute;
    int seconds = end->wSecond - start->wSecond;
    int ms = end->wMilliseconds - start->wMilliseconds;
    if (ms < 0)
    {
        ms += 1000;
        seconds -= 1;
    }
    if (seconds < 0)
    {
        seconds += 60;
        minutes -= 1;
    }
    if (minutes < 0)
    {
        minutes += 60;
        hours -= 1;
    }
    //由於僅考慮在一天之內，不考慮小時會變成負數的情況
    printf("runtime: %02dhours %02dminutes %02dseconds %02dmilliseconds\n", hours, minutes, seconds, ms);
}

void newProcess(TCHAR* cWinDir, double duration)
{
    PROCESS_INFORMATION pi;
    STARTUPINFO si;
    ZeroMemory(&si, sizeof(si));
    si.cb = sizeof(si);
    ZeroMemory(&pi, sizeof(pi));
    

    SYSTEMTIME start_time, end_time;
    memset(&start_time, sizeof(SYSTEMTIME), 0);
    memset(&end_time, sizeof(SYSTEMTIME), 0);
    GetSystemTime(&start_time);

        //建議大家不要單獨傳入lpApplicationName,而是將程序名放入cWinDir中
        //這樣會自動搜索PATH
    if (CreateProcess(
        NULL,       //lpApplicationName.若為空，則lpCommandLine必須指定可執行程序
                    //若路徑中存在空格，必須使用引號框定
        cWinDir,    //lpCommandLine
                    //若lpApplicationName為空，lpCommandLine長度不超過MAX_PATH
        NULL,       //指向一個SECURITY_ATTRIBUTES結構體，這個結構體決定是否返回的句柄可以被子進程繼承，進程安全性
        NULL,       //  如果lpProcessAttributes參數為空（NULL），那麼句柄不能被繼承。<同上>，線程安全性
        false,      //  指示新進程是否從調用進程處繼承了句柄。句柄可繼承性
        0,          //  指定附加的、用來控制優先類和進程的創建的標識符（優先級）
                    //  CREATE_NEW_CONSOLE  新控制台打開子進程
                    //  CREATE_SUSPENDED    子進程創建后掛起，直到調用ResumeThread函數
        NULL,       //  指向一個新進程的環境塊。如果此參數為空，新進程使用調用進程的環境。指向環境字符串
        NULL,       //  指定子進程的工作路徑
        &si,        //  決定新進程的主窗體如何显示的STARTUPINFO結構體
        &pi         //  接收新進程的識別信息的PROCESS_INFORMATION結構體。進程線程以及句柄
    ))
    {
    }
    else
    {
        printf("CreateProcess failed (%d).\n", GetLastError());
        return;
    }


    //wait untill the child process exits
    if (abs(duration - 0) < 1e-6)
        WaitForSingleObject(pi.hProcess, INFINITE);//這裏指定運行時間，單位毫秒
    else
        WaitForSingleObject(pi.hProcess, duration * 1000);

    GetSystemTime(&end_time);

    printTime(&start_time, &end_time);

    CloseHandle(pi.hProcess);
    CloseHandle(pi.hThread);
}

測試程序

#include <iostream>
#include <Windows.h>
using namespace std;
int main(int argc, char* argv[])
{
    for (int n = 0; n < argc; n++)
    {
        printf("arg[%d]:%s\n", n, argv[n]);
    }
    Sleep(5*1000);
    return 0;
}

測試

1. 自行編寫程序測試

2. 系統程序測試

3. 添加至環境變量

參考資料

Windows

Linux

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理【其他文章推薦】

※網頁設計公司推薦更多不同的設計風格，搶佔消費者視覺第一線

※廣告預算用在刀口上，網站設計公司幫您達到更多曝光效益

※自行創業 缺乏曝光? 下一步"網站設計"幫您第一時間規劃公司的門面形象

ASP.NET Core應用中使用得最多的還是具體的物理文件，比如配置文件、View文件以及作為Web資源的靜態文件。物理文件系統由定義在NuGet包“Microsoft.Extensions.FileProviders.Physical”中的PhysicalFileProvider來構建。我們知道System.IO命名空間下定義了一整套針操作物理目錄和文件的API，實際上PhysicalFileProvider最終也是通過調用這些API來完成相關的IO操作。

public class PhysicalFileProvider : IFileProvider, IDisposable
{   
    public PhysicalFileProvider(string root);   
     
    public IFileInfo GetFileInfo(string subpath);  
    public IDirectoryContents GetDirectoryContents(string subpath); 
    public IChangeToken Watch(string filter);

    public void Dispose();   
}

一、PhysicalFileInfo

一個PhysicalFileProvider對象總是映射到某個具體的物理目錄上，被映射的目錄所在的路徑通過構造函數的參數root來提供，該目錄將作為PhysicalFileProvider的根目錄。GetFileInfo方法返回的IFileInfo對象代表指定路徑對應的文件，這是一個類型為PhysicalFileInfo的對象。一個物理文件可以通過一個System.IO.FileInfo對象來表示，一個PhysicalFileInfo對象實際上就是對該對象的封裝，定義在PhysicalFileInfo的所有屬性都來源於這個FileInfo對象。對於創建讀取文件輸出流的CreateReadStream方法來說，它返回的是一個根據物理文件絕對路徑創建的FileStream對象。

public class PhysicalFileInfo : IFileInfo
{
    ...
    public PhysicalFileInfo(FileInfo info);    
}

對於PhysicalFileProvider的GetFileInfo方法來說，即使我們指定的路徑指向一個具體的物理文件，它並不總是會返回一個PhysicalFileInfo對象。PhysicalFileProvider會將一些場景視為“目標文件不存在”，並讓GetFileInfo方法返回一個NotFoundFileInfo對象。具體來說，PhysicalFileProvider的GetFileInfo方法在如下的場景中會返回一個NotFoundFileInfo對象：

• 確實沒有一個物理文件與指定的路徑相匹配。
• 如果指定的是一個絕對路徑（比如“c:\foobar”），即Path.IsPathRooted方法返回True。
• 如果指定的路徑指向一個隱藏文件。

顧名思義，具有如下定義的NotFoundFileInfo類型表示一個“不存在”的文件。NotFoundFileInfo對象的Exists屬性總是返回False，而其他的屬性則變得沒有任何意義。當我們調用它的CreateReadStream試圖讀取一個根本不存在的文件內容時，會拋出一個FileNotFoundException類型的異常。

public class NotFoundFileInfo : IFileInfo
{
    public bool Exists => false;   
    public long Length => throw new NotImplementedException();   
    public string PhysicalPath => null;  
    public string Name { get; }   
    public DateTimeOffset LastModified => DateTimeOffset.MinValue;
    public bool IsDirectory => false; 

    public NotFoundFileInfo(string name) => this.Name = name;
    public Stream CreateReadStream() => throw new FileNotFoundException($"The file {Name} does not exist.");
}

二、PhysicalDirectoryInfo

PhysicalFileProvider利用一個PhysicalFileInfo對象來描述某個具體的物理文件，而一個物理目錄則通過一個PhysicalDirectoryInfo的對象來描述。既然PhysicalFileInfo是對一個FileInfo對象的封裝，那麼我們應該想得到PhysicalDirectoryInfo對象封裝的就是表示目錄的DirectoryInfo對象。如下面的代碼片段所示，我們需要在創建一個PhysicalDirectoryInfo對象時提供這個DirectoryInfo對象，PhysicalDirectoryInfo實現的所有屬性的返回值都來源於這個DirectoryInfo對象。由於CreateReadStream方法的目的總是讀取文件的內容，所以PhysicalDirectoryInfo類型的這個方法會拋出一個InvalidOperationException類型的異常。

public class PhysicalDirectoryInfo : IFileInfo
{   
    ...
    public PhysicalDirectoryInfo(DirectoryInfo info);
}

三、PhysicalDirectoryContents

當我們調用PhysicalFileProvider的GetDirectoryContents方法時，如果指定的路徑指向一個具體的目錄，那麼該方法會返回一個類型為PhysicalDirectoryContents的對象。PhysicalDirectoryContents是一個IFileInfo對象的集合，該集合中包括所有描述子目錄的PhysicalDirectoryInfo對象和描述文件的PhysicalFileInfo對象。PhysicalDirectoryContents的Exists屬性取決於指定的目錄是否存在。

public class PhysicalDirectoryContents : IDirectoryContents
{
    public bool Exists { get; }
    public PhysicalDirectoryContents(string directory);
    public IEnumerator<IFileInfo> GetEnumerator();
    IEnumerator IEnumerable.GetEnumerator();
}

四、NotFoundDirectoryContents

如果指定的路徑並不指向一個存在的目錄，或者指定的是一個絕對路徑，GetDirectoryContents方法都會返回一個Exsits為False的NotFoundDirectoryContents對象。如下所示的代碼片段展示了NotFoundDirectoryContents類型的定義，如果我們需要使用到這麼一個類型，可以直接利用靜態屬性Singleton得到對應的單例對象。

public class NotFoundDirectoryContents : IDirectoryContents
{    
    public static NotFoundDirectoryContents Singleton { get; }  = new NotFoundDirectoryContents();
    public bool Exists => false;
    public IEnumerator<IFileInfo> GetEnumerator()  => Enumerable.Empty<IFileInfo>().GetEnumerator();
    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

五、PhysicalFilesWatcher

我們接着來談談PhysicalFileProvider的Watch方法。當我們調用該方法的時候，PhysicalFileProvider會通過解析我們提供的Globbing Pattern表達式來確定我們期望監控的文件或者目錄，並最終利用FileSystemWatcher對象來對這些文件實施監控。這些文件或者目錄的變化（創建、修改、重命名和刪除等）都會實時地反映到Watch方法返回的IChangeToken上。

PhysicalFileProvider的Watch方法中指定的Globbing Pattern表達式必須是針對當前根目錄的相對路徑，我們可以使用“/”或者“./”前綴，也可以不採用任何前綴。一旦我們使用了絕對路徑（比如“c:\test\*.txt”）或者“../”前綴（比如“../test/*.txt”），不論解析出來的文件是否存在於PhysicalFileProvider的根目錄下，這些文件都不會被監控。除此之外，如果我們沒有指定Globbing Pattern表達式，PhysicalFileProvider也不會有任何的文件會被監控。

PhysicalFileProvider針對物理文件系統變化的監控是通過如下這個PhysicalFilesWatcher對象實現的，其Watch方法內部會直接調用PhysicalFileProvider的CreateFileChangeToken方法，並返回得到的IChangeToken對象。這是一個公共類型，如果我們具有監控物理文件系統變化的需要，可以直接使用這個類型。

public class PhysicalFilesWatcher: IDisposable
{
    public PhysicalFilesWatcher(string root, FileSystemWatcher fileSystemWatcher, bool pollForChanges);
    public IChangeToken CreateFileChangeToken(string filter);
    public void Dispose();
}

從PhysicalFilesWatcher構造函數的定義我們不難看出，它最終是利用一個FileSystemWatcher對象（對應於fileSystemWatcher參數）來完成針對指定根目錄下（對應於root參數）所有子目錄和文件的監控。FileSystemWatcher的CreateFileChangeToken方法返回的IChangeToken對象會幫助我們感知到子目錄或者文件的添加、刪除、修改和重命名，但是它會忽略隱藏的目錄和文件。最後需要提醒的是，當我們不再需要對指定目錄實施監控的時候，記得調用PhysicalFileProvider的Dispose方法，該方法會負責將FileSystemWatcher對象關閉。

六、小結

我們藉助下圖所示的UML來對由PhysicalFileProvider構建物理文件系統的整體設計做一個簡單的總結。首先，該文件系統使用PhysicalDirectoryInfo和PhysicalFileInfo對類型來描述目錄和文件，它們分別是對DirectoryInfo和FileInfo（System.IO.FileInfo）對象的封裝。

PhysicalFileProvider的GetDirectoryContents方法返回一個PhysicalDirectoryContents 對象（如果指定的目錄存在），組成該對象的分別是根據其所有子目錄和文件創建的PhysicalDirectoryInfo和PhysicalFileInfo對象。當我們調用PhysicalFileProvider的GetFileInfo方法時，如果指定的文件存在，返回的是描述該文件的PhysicalFileInfo對象。至於PhysicalFileProvider的Watch方法，它最終利用了FileSystemWatcher來監控指定文件或者目錄的變化。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理【其他文章推薦】

※網頁設計公司推薦更多不同的設計風格，搶佔消費者視覺第一線

※廣告預算用在刀口上，網站設計公司幫您達到更多曝光效益

※自行創業 缺乏曝光? 下一步"網站設計"幫您第一時間規劃公司的門面形象

一、簡介

flexbox：全稱Flexible Box, 彈性盒子布局。可以簡單實現各種伸縮性的設計，它是由伸縮容器和伸縮項目組成。任何一個元素都可以指定為flexbox布局。這種新的布局方案在2009年是由W3C組織提出來的，在此之前，Web開發一般使用基於盒子模型的傳統頁面布局，依賴定位屬性、流動屬性和显示屬性來解決，參看鏈接：。彈性盒子布局的出現，極大的方便了開發者，在如今的ReactNative開發中，也已經被引入使用。

伸縮流布局結構圖如下：

彈性盒子布局具備的特徵：

1、伸縮容器的子元素稱為伸縮項目，伸縮項目使用伸縮布局來排版。伸縮布局和傳統布局不一樣，它按照伸縮流方向布局。

2、伸縮容器由兩條軸構成，分別為主軸(main axis)和交叉軸(cross axis)。主軸既可以用水平軸，也可以是豎直軸，根據開發者需要來決定。

3、主軸的起點叫main start，終點叫main end，主軸的空間用main size表示。

4、交叉軸的起點叫cross start，終點叫cross end，交叉軸的空間用cross size表示。

5、默認情況下，伸縮項目總是沿着主軸方向排版，從開始位置到終點位置。至於換行显示，則通過設置伸縮屬性來實現。

6、伸縮容器的屬性有：display、flex-direction、flex-wrap、flex-flow、justify-content、align-items、align-content

7、伸縮項目的屬性有: order、flex-grow、flex-shrink、flex-basis、flex、align-self

二、伸縮容器的屬性，全局設置排版

HTML：[注意：下面的演示截圖項目個數會根據需要選擇性註釋“flex-item”，有時用不到5個]

<!DOCTYPE html>
<html>
<head>
    <title>Flexbox</title>
    <!--  採用外聯方式導入css文件 -->
    <link rel="stylesheet" type="text/css" href="./css_test.css">
</head>
<body>
    <span class="flex-container"> 
        <span class="flex-item" id="item1" style="color:white;font-size:20px">1</span>
        <span class="flex-item" id="item2" style="color:white;font-size:20px">2</span>
        <span class="flex-item" id="item3" style="color:white;font-size:20px">3</span>
        <span class="flex-item" id="item4" style="color:white;font-size:20px">4</span>
        <span class="flex-item" id="item5" style="color:white;font-size:20px">5</span>
    </span>
</body>
</html> 

1、display：決定元素是否為伸縮容器

• flex：產生塊級伸縮容器

  .flex-container {
       display: flex;
   }

• inline-flex：產生行內塊級伸縮容器

•  .flex-container {
       display: inline-flex;
   }

2、flex-direction：指定伸縮容器主軸的方向

• row：水平方向，從左到右

   .flex-container {
       display: flex;
       flex-direction: row;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px; 
       height: 50px;
       background-color: green;
       margin: 1px;
   }

• row-reverse：水平方向，從右到左

   .flex-container {
       display: flex;
       flex-direction: row-reverse;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px; 
       height: 50px;
       background-color: green;
       margin: 1px;
   }

• column：豎直方向，從上到下

   .flex-container {
       display: flex;
       flex-direction: column;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px;
       height: 50px; 
       background-color: green;
       margin: 1px;
   }

• column-reverse：豎直方向，從下到上

   .flex-container {
       display: flex;
       flex-direction: column-reverse;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px;
       height: 50px; 
       background-color: green;
       margin: 1px;
   }

3、flex-wrap：指定伸縮容器主軸方向空間不足時，決定是否換行以及換行方式

• nowarp：不換行

  .flex-container {
       display: flex;
       flex-direction: row;
       flex-wrap: nowrap;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px; //下圖單行狀態寬度被重新計算
       height: 50px;
       background-color: green;
       margin: 1px;
   }

• warp：換行，若主軸為水平方向，換行方向是從上到下

   .flex-container {
       display: flex;
       flex-direction: row;
       flex-wrap: wrap;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px;
       height: 50px;
       background-color: green;
       margin: 1px;
   }

• wrap-reverse：換行，若主軸為水平方向，換行方向是從下到上

   .flex-container {
       display: flex;
       flex-direction: row;
       flex-wrap: wrap-reverse;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px;
       height: 50px;
       background-color: green;
       margin: 1px;
   }

4、flex-flow：flex-direction和flex-wrap的縮寫，同時指定伸縮容器主軸方向和換行設置

• row nowrap：默認主軸是水平方向，從左到右，且不換行

   .flex-container {
       display: flex;
       flex-flow: row nowrap;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px; //下圖單行狀態寬度被重新計算
       height: 50px;
       background-color: green;
       margin: 1px;
   }

5、justify-content：決定伸縮項目沿着主軸線的對齊方式

• flex-start：與主軸線起始位置靠齊

   .flex-container {
       display: flex;
       flex-flow: row wrap;
       justify-content: flex-start;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px;
       height: 50px;
       background-color: green;
       margin: 1px;
   }

• flex-end：與主軸線結束位置靠齊

   .flex-container {
       display: flex;
       flex-flow: row wrap;
       justify-content: flex-end;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px;
       height: 50px;
       background-color: green;
       margin: 1px;
   }

• center：與主軸線中間位置靠齊

   .flex-container {
       display: flex;
       flex-flow: row wrap;
       justify-content: center;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px;
       height: 50px;
       background-color: green;
       margin: 1px;
   }

• space-between：平均分配到主軸線里，第一個項目靠齊起始位置，最後一個項目靠齊終點位置

   .flex-container {
       display: flex;
       flex-flow: row wrap;
       justify-content: space-between;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px;
       height: 50px;
       background-color: green;
       margin: 1px;
   }

• sapce-around：平均分配到主軸線里，兩端保留一半的空間

  .flex-container {
       display: flex;
       flex-flow: row wrap;
       justify-content: space-around;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px;
       height: 50px;
       background-color: green;
       margin: 1px;
   }

6、align-items：決定伸縮項目不能換行時沿着交叉軸線的對齊方式

• flex-start：與交叉軸線起始位置靠齊

   .flex-container {
       display: flex;
       flex-flow: row nowrap;
       align-items: flex-start;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px; //下圖單行狀態寬度被重新計算
       height: 50px;
       background-color: green;
       margin: 1px;
   }

• flex-end：與交叉軸線結束位置靠齊

   .flex-container {
       display: flex;
       flex-flow: row nowrap;
       align-items: flex-end;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px; //下圖單行狀態寬度被重新計算
       height: 50px;
       background-color: green;
       margin: 1px;
   }

• center：與交叉軸線中間位置靠齊

   .flex-container {
       display: flex;
       flex-flow: row nowrap;
       align-items: center;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px;
       height: 50px;
       background-color: green;
       margin: 1px;
   }

• baseline：根據基線對齊

   .flex-container {
       display: flex;
       flex-flow: row nowrap;
       align-items: baseline;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px;
       height: 50px;
       background-color: green;
       margin: 1px;
   }
  
   #item1 {
       padding-top: 25px;
   }
  
   #item2 {
       padding-top: 20px;
   }
    
   #item3 {
       padding-top: 15px;
   }
  
   #item4 {
       padding-top: 10px;
   }
    
   #item5 {
       padding-top: 5px;
   }

• stretch：沿着交叉軸線拉伸填充整個伸縮容器

   .flex-container {
       display: flex;
       flex-flow: row nowrap;
       align-items: stretch;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px;//此時可以設置寬度，但不能設置高度，否則無法拉伸
       background-color: green;
       margin: 1px;
   }

7、align-content：決定伸縮項目可以換行時沿着交叉軸線的對齊方式，flex-warp:warp一定要開啟

• flex-start：與交叉軸線起始位置靠齊

   .flex-container {
       display: flex;
       flex-flow: row wrap;
       align-content:flex-start;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px;
       height: 50px;
       background-color: green;
       margin: 1px;
   }

• flex-end：與交叉軸線結束位置靠齊

   .flex-container {
       display: flex;
       flex-flow: row wrap;
       align-content:flex-end;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px;
       height: 50px;
       background-color: green;
       margin: 1px;
   }

• center：與主軸線中間位置靠齊

   .flex-container {
       display: flex;
       flex-flow: row wrap;
       align-content:center;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px;
       height: 50px;
       background-color: green;
       margin: 1px;
   }

• space-between：平均分配到主軸線里，第一行項目靠齊起始位置，最後一行項目靠齊終點位置

   .flex-container {
       display: flex;
       flex-flow: row wrap;
       align-content:space-between;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px;
       height: 50px;
       background-color: green;
       margin: 1px;
   }

• sapce-around：所有行平均分配到主軸線里，兩端保留一半的空間

   .flex-container {
       display: flex;
       flex-flow: row wrap;
       align-content:space-around;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px;
       height: 50px;
       background-color: green;
       margin: 1px;
   }

• stretch：沿着交叉軸

   .flex-container {
       display: flex;
       flex-flow: row wrap;
       align-content:stretch;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px; //不要設置高度，不然無法拉伸
       background-color: green;
       margin: 1px;
   }

三、伸縮項目的屬性，單個設置排版

1、order：定義伸縮項目的排列順序。數值越小，排列越靠前，默認值為0。

• 表達式 order: integer;

   .flex-container {
       display: flex;
       flex-flow: row wrap;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px;
       height: 50px;
       background-color: green;
       margin: 1px;
   }
  
   #item4 {
       order: -1;
   }
  
   #item5 {
       order: -2;
   }

2、flex-grow：定義伸縮項目的放大比例，默認值為0，表示即使存在剩餘空間，也不放大。

• 表達式 flex-grow: number;

   .flex-container {
       display: flex;
       flex-flow: row wrap;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px;
       height: 50px;
       background-color: green;
       margin: 1px;
   }
  
   #item2 {
       flex-grow: 1; //空間不足，item2不會放大
   }
  
   #item4 {
       flex-grow: 1; //item4放大填滿剩餘空間
   }

3、flex-shrink：定義伸縮項目的收縮比例，默認值為1。

• 表達式 flex-shrink: numer;

  .flex-container {
       display: flex;
       flex-flow: row nowrap;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px;
       height: 50px;
       background-color: green;
       margin: 1px;
   }
  
   #item4 {
       flex-shrink:3; //單行，空間有限，item4縮小為原來的1/3
   }
  
   #item5 {
       flex-shrink:4;  //單行，空間有限，item5縮小為原來的1/5
  }

4、flex-basis：定義伸縮項目的基準值，剩餘空間按照比例進行伸縮，默認auto。

•  auto

   .flex-container {
       display: flex;
       flex-flow: row wrap;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px;
       height: 50px;
       background-color: green;
       margin: 1px;
   }
  
   #item5 {
       flex-basis:auto;
   }

• flex-basis: length 

   .flex-container {
       display: flex;
       flex-flow: row wrap;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px;
       height: 50px;
       background-color: green;
       margin: 1px;
   }
  
   #item5 {
       flex-basis:200px;
   }

5、flex：是flex-grow、flex-shrink、flex-basis的縮寫，默認值 0 1 auto。

• none: 不設置

   .flex-container {
       display: flex;
       flex-flow: row wrap;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px;
       height: 50px;
       background-color: green;
       margin: 1px;
   }
  
   #item2 {
       flex: none; /* 等同於 flex: 0 0 auto */
   }

• flex-grow flex-shrink flex-basis: 設置放大或縮小或基準線

   .flex-container {
       display: flex;
       flex-flow: row wrap;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px;
       height: 50px;
       background-color: green;
       margin: 1px;
   }
  
   #item2 {
       flex: 1; /* 等同於 flex: 1 1 auto 或者 等同於 flex: auto*/
   }

6、align-self：用來設置伸縮項目在交叉軸的對齊方式。

• auto：自動對齊

   .flex-container {
       display: flex;
       flex-flow: row wrap;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px;
       height: 50px;
       background-color: green;
       margin: 1px;
   }
  
   #item3 {
       align-self: auto;
   }

• flex-start: 向交叉軸的開始位置對齊

   .flex-container {
       display: flex;
       flex-flow: row wrap;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px;
       height: 50px;
       background-color: green;
       margin: 1px;
   }
  
   #item3 {
       align-self: flex-start;
   }

• flex-end: 向交叉軸的結束位置對齊

   .flex-container {
       display: flex;
       flex-flow: row wrap;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px;
       height: 50px;
       background-color: green;
       margin: 1px;
   }
  
   #item3 {
       align-self: flex-end;
   }

• center: 向交叉軸的中間位置對齊

   .flex-container {
       display: flex;
       flex-flow: row wrap;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px;
       height: 50px;
       background-color: green;
       margin: 1px;
   }
  
   #item3 {
       align-self: center;
   }

• baseline:向交叉軸的基準線對齊

   .flex-container {
       display: flex;
       flex-flow: row wrap;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px;
       height: 50px;
       background-color: green;
       margin: 1px;
   }
  
   #item1 {
       align-self: baseline;
       margin-top: 50px;
   }
  
   #item2 {
       align-self: baseline;
   }

• stretch: 在交叉軸拉伸填滿伸縮容器

   .flex-container {
       display: flex;
       flex-flow: row wrap;
       width: 160px;
       height: 160px;
       background-color: red;
   }
  
   .flex-item {
       width: 50px;
       background-color: green;
       margin: 1px;
   }
  
   #item1 {
       align-self: stretch;
   }
  
   #item2 {
       align-self: stretch;
   }
  
   #item3 {
       align-self: stretch;
   }

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理【其他文章推薦】

※網頁設計公司推薦更多不同的設計風格，搶佔消費者視覺第一線

※廣告預算用在刀口上，網站設計公司幫您達到更多曝光效益

※自行創業 缺乏曝光? 下一步"網站設計"幫您第一時間規劃公司的門面形象

儘管蘋果公司一直三緘其口，但是對於傳聞中的蘋果電動汽車項目，已經快成為了公開的秘密。現在，蘋果的首個關於汽車技術的專利也被人曝光，不過看起來與我們期望的距離似乎有點遙遠。  
  近日，美國專利商標局通過了一批蘋果公司的新專利，其中一項專利顯示了一種採用履帶以及軌槽設計的交通工具草圖。這項專利其實是兩個貨箱之間的接駁原理，駕駛員可以在極端寒冷空氣條件下，直接，通過加熱裝置，控制第一個車廂的轉向構件及包括一個連接機制的第二個車廂。   據悉，這項專利由瑞典軍用坦克製造商BAE公司授權給蘋果，因此至少目前來看肯定不會被使用在普通的消費和商業領域。   文章來源：騰訊數碼

本站聲明:網站內容來源於EnergyTrend https://www.energytrend.com.tw/ev/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※網頁設計公司推薦更多不同的設計風格，搶佔消費者視覺第一線

※廣告預算用在刀口上，網站設計公司幫您達到更多曝光效益

※自行創業 缺乏曝光? 下一步"網站設計"幫您第一時間規劃公司的門面形象

一、摘要

在集合系列的第一章，咱們了解到，Map的實現類有HashMap、LinkedHashMap、TreeMap、IdentityHashMap、WeakHashMap、Hashtable、Properties等等。

本文主要從數據結構和算法層面，探討TreeMap的實現。

二、簡介

Java TreeMap實現了SortedMap接口，也就是說會按照key的大小順序對Map中的元素進行排序，key大小的評判可以通過其本身的自然順序（natural ordering），也可以通過構造時傳入的比較器（Comparator）。

TreeMap底層通過紅黑樹（Red-Black tree）實現，所以要了解TreeMap就必須對紅黑樹有一定的了解，在《集合系列》文章中，如果你已經讀過紅黑樹的講解，其實本文要講解的TreeMap，跟其大同小異。

紅黑樹又稱紅-黑二叉樹，它首先是一顆二叉樹，它具有二叉樹所有的特性。同時紅黑樹更是一顆自平衡的排序二叉樹。

對於一棵有效的紅黑樹二叉樹，主要有以下規則：

• 1、每個節點要麼是紅色，要麼是黑色，但根節點永遠是黑色的；
• 2、每個紅色節點的兩個子節點一定都是黑色；
• 3、紅色節點不能連續（也即是，紅色節點的孩子和父親都不能是紅色）；
• 4、從任一節點到其子樹中每個恭弘=叶 恭弘子節點的路徑都包含相同數量的黑色節點；
• 5、所有的恭弘=叶 恭弘節點都是是黑色的（注意這裏說恭弘=叶 恭弘子節點其實是上圖中的 NIL 節點）；

這些約束強制了紅黑樹的關鍵性質：從根到恭弘=叶 恭弘子的最長的可能路徑不多於最短的可能路徑的兩倍長。結果是這棵樹大致上是平衡的。因為操作比如插入、刪除和查找某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同於普通的二叉查找樹。所以紅黑樹它是複雜而高效的，其檢索效率O(log n)。下圖為一顆典型的紅黑二叉樹。

在樹的結構發生改變時（插入或者刪除操作），往往會破壞上述條件3或條件4，需要通過調整使得查找樹重新滿足紅黑樹的條件。

調整方式主要有：左旋、右旋和顏色轉換！

2.1、左旋

左旋的過程是將x的右子樹繞x逆時針旋轉，使得x的右子樹成為x的父親，同時修改相關節點的引用。旋轉之後，二叉查找樹的屬性仍然滿足。

2.2、右旋

右旋的過程是將x的左子樹繞x順時針旋轉，使得x的左子樹成為x的父親，同時修改相關節點的引用。旋轉之後，二叉查找樹的屬性仍然滿足。

2.3、顏色轉換

顏色轉換的過程是將紅色節點轉換為黑色節點，或者將黑色節點轉換為紅色節點，以滿足紅黑樹二叉樹的規則！

三、常用方法介紹

3.1、get方法

get方法根據指定的key值返回對應的value，該方法調用了getEntry(Object key)得到相應的entry，然後返回entry.value。

算法思想是根據key的自然順序（或者比較器順序）對二叉查找樹進行查找，直到找到滿足k.compareTo(p.key) == 0的entry。

源碼如下：

final Entry<K,V> getEntry(Object key) {
        //如果傳入比較器，通過getEntryUsingComparator方法獲取元素
        if (comparator != null)
            return getEntryUsingComparator(key);
        //不允許key值為null
        if (key == null)
            throw new NullPointerException();
        //使用元素的自然順序
            Comparable<? super K> k = (Comparable<? super K>) key;
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = k.compareTo(p.key);
            if (cmp < 0)
                //向左找
                p = p.left;
            else if (cmp > 0)
                //向右找
                p = p.right;
            else
                return p;
        }
        return null;
}

如果傳入比較器，通過getEntryUsingComparator方法獲取元素

final Entry<K,V> getEntryUsingComparator(Object key) {
            K k = (K) key;
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            Entry<K,V> p = root;
            while (p != null) {
                //通過比較器順序，獲取元素
                int cmp = cpr.compare(k, p.key);
                if (cmp < 0)
                    p = p.left;
                else if (cmp > 0)
                    p = p.right;
                else
                    return p;
            }
        }
        return null;
}

測試用例：

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("默認 排序結果:" + initMap.toString());

        //自定義排序，在TreeMap初始化階段傳入Comparator 內部對象
        Map comparatorMap = new TreeMap<String, String>(new Comparator<String>() {

            @Override
            public int compare(String o1, String o2){
                //根據key比較大小，採用倒敘，以大到小排序
                return o2.compareTo(o1);
            }
        });
        comparatorMap.put("4", "d");
        comparatorMap.put("3", "c");
        comparatorMap.put("1", "a");
        comparatorMap.put("2", "b");

        System.out.println("自定義 排序結果:" + comparatorMap.toString());
}

輸出結果：

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

3.2、put方法

put方法是將指定的key, value對添加到map里。該方法首先會對map做一次查找，看是否包含該元組，如果已經包含則直接返回，查找過程類似於getEntry()方法；如果沒有找到則會在紅黑樹中插入新的entry，如果插入之後破壞了紅黑樹的約束，還需要進行調整（旋轉，改變某些節點的顏色）。

源碼如下：

public V put(K key, V value) {
        Entry<K,V> t = root;
        //如果紅黑樹根部為空，直接插入
        if (t == null) {
            compare(key, key); // type (and possibly null) check

            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        //如果比較器，通過比較器順序，找到插入位置
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            //通過自然順序，找到插入位置
            if (key == null)
                throw new NullPointerException();
                Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        //創建並插入新的entry
        Entry<K,V> e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        //紅黑樹調整函數
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
}

紅黑樹調整函數fixAfterInsertion(Entry<K,V> x)

private void fixAfterInsertion(Entry<K,V> x) {
    x.color = RED;
    while (x != null && x != root && x.parent.color == RED) {
        //判斷x是否在樹的左邊，還是右邊
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            //如果x的父親的父親的右子樹是紅色，違反了紅色節點不能連續
            if (colorOf(y) == RED) {
                //進行顏色調整，以滿足紅色節點不能連續規則
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK); 
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                //如果x的父親的右子樹等於自己，那麼需要進行左旋轉
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateLeft(x);
                }
                setColor(parentOf(x), BLACK);  
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            //跟上面的流程正好相反
            //獲取x的父親的父親的左子樹節點
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            //如果y是紅色節點，違反了紅色節點不能連續
            if (colorOf(y) == RED) {
                //進行顏色轉換
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                //如果x的父親的左子樹等於自己，那麼需要進行右旋轉
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateRight(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    //根節點一定為黑色
    root.color = BLACK;
}

上述代碼的插入流程：

• 1、首先在紅黑樹上找到合適的位置；
• 2、然後創建新的entry並插入；
• 3、通過函數fixAfterInsertion()，對某些節點進行旋轉、改變某些節點的顏色，進行調整；

調整圖解：

3.3、remove方法

remove的作用是刪除key值對應的entry，該方法首先通過上文中提到的getEntry(Object key)方法找到 key 值對應的 entry，然後調用deleteEntry(Entry<K,V> entry)刪除對應的 entry。由於刪除操作會改變紅黑樹的結構，有可能破壞紅黑樹的約束，因此有可能要進行調整。

源碼如下：

public V remove(Object key) {
        Entry<K,V> p = getEntry(key);
        if (p == null)
            return null;

        V oldValue = p.value;
        deleteEntry(p);
        return oldValue;
}

刪除函數 deleteEntry()

private void deleteEntry(Entry<K,V> p) {
    modCount++;
    size--;
    if (p.left != null && p.right != null) {// 刪除點p的左右子樹都非空。
        Entry<K,V> s = successor(p);// 後繼
        p.key = s.key;
        p.value = s.value;
        p = s;
    }
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);
    if (replacement != null) {// 刪除點p只有一棵子樹非空。
        replacement.parent = p.parent;
        if (p.parent == null)
            root = replacement;
        else if (p == p.parent.left)
            p.parent.left  = replacement;
        else
            p.parent.right = replacement;
        p.left = p.right = p.parent = null;
        if (p.color == BLACK)
            fixAfterDeletion(replacement);// 調整
    } else if (p.parent == null) {
        root = null;
    } else { //刪除點p的左右子樹都為空
        if (p.color == BLACK)
            fixAfterDeletion(p);// 調整
        if (p.parent != null) {
            if (p == p.parent.left)
                p.parent.left = null;
            else if (p == p.parent.right)
                p.parent.right = null;
            p.parent = null;
        }
    }
}

刪除后調整函數fixAfterDeletion()的具體代碼如下：

private void fixAfterDeletion(Entry<K,V> x) {
    while (x != root && colorOf(x) == BLACK) {
        //判斷當前刪除的元素，是在x父親的左邊還是右邊
        if (x == leftOf(parentOf(x))) {
            Entry<K,V> sib = rightOf(parentOf(x));
            //判斷x的父親的右子樹，是紅色還是黑色節點
            if (colorOf(sib) == RED) {
                //進行顏色轉換
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateLeft(parentOf(x));
                sib = rightOf(parentOf(x));
            }
            //x的父親的右子樹的左邊是黑色節點，右邊也是黑色節點
            if (colorOf(leftOf(sib))  == BLACK &&
                colorOf(rightOf(sib)) == BLACK) {
                //設置x的父親的右子樹為紅色節點，將x的父親賦值給x
                setColor(sib, RED);
                x = parentOf(x);
            } else {
                //x的父親的右子樹的左邊是紅色節點，右邊也是黑色節點
                if (colorOf(rightOf(sib)) == BLACK) {
                    //x的父親的右子樹的左邊進行顏色調整，右旋調整
                    setColor(leftOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateRight(sib);
                    sib = rightOf(parentOf(x));
                }
                //對x進行左旋，顏色調整
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(rightOf(sib), BLACK);
                rotateLeft(parentOf(x));
                x = root;
            }
        } else { // 跟前四種情況對稱
            Entry<K,V> sib = leftOf(parentOf(x));
            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateRight(parentOf(x));
                sib = leftOf(parentOf(x));
            }
            if (colorOf(rightOf(sib)) == BLACK &&
                colorOf(leftOf(sib)) == BLACK) {
                setColor(sib, RED);
                x = parentOf(x);
            } else {
                if (colorOf(leftOf(sib)) == BLACK) {
                    setColor(rightOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateLeft(sib);
                    sib = leftOf(parentOf(x));
                }
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(leftOf(sib), BLACK);
                rotateRight(parentOf(x));
                x = root;
            }
        }
    }
    setColor(x, BLACK);
}

上述代碼的刪除流程：

• 1、首先在紅黑樹上找到合適的位置；
• 2、然後刪除entry；
• 3、通過函數fixAfterDeletion()，對某些節點進行旋轉、改變某些節點的顏色，進行調整；

四、總結

TreeMap 默認是按鍵值的升序排序，如果需要自定義排序，可以通過new Comparator構造參數，重寫compare方法，進行自定義比較。

以上，主要是對 java 集合中的 TreeMap 做了寫講解，如果有理解不當之處，歡迎指正。

五、參考

1、JDK1.7&JDK1.8 源碼
2、
2、

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理【其他文章推薦】

※網頁設計公司推薦更多不同的設計風格，搶佔消費者視覺第一線

※廣告預算用在刀口上，網站設計公司幫您達到更多曝光效益

※自行創業 缺乏曝光? 下一步"網站設計"幫您第一時間規劃公司的門面形象