目錄

1、基礎概念

1.1、JNI

JNI（Java Native Interface）Java本地接口，使得Java與C/C++具有交互能力

1.2、NDK

NDK（Native Development Kit） 本地開發工具包，允許使用原生語言（C和C++）來實現應用程序的部分功能

Android NDK開發的主要作用：

1、特定場景下，提升應用性能；
2、代碼保護，增加反編譯難度；
3、生成庫文件，庫可重複使用，也便於平台、項目間移植；

1.3、CMake與ndk-build

當我們基於NDK開發出native功能后，通常需要編譯成庫文件，給Android項目使用。
目前，有兩種主流的編譯方式：__CMake__與ndk-build

__CMake__與__ndk-build__是兩種不同的編譯工具（與Android代碼和C/C++代碼無關）

CMake

CMake是Androidstudio2.2之後引入的跨平台編譯工具（特點：簡單易用，2.2之後是默認的NDK編譯工具）

如何配置：
   1、創建CMakeLists.txt文件，配置CMake必要參數；
   2、使用gradle配置CMakeLists.txt以及native相關參數；

如何編譯庫文件：
   1、Android Studio執行Build即可；

ndk-build

ndk-build是NDK中包含的腳本工具（可在NDK目錄下找到該工具，為了方便使用，通常配置NDK的環境變量）

如何配置：
   1、創建Android.mk文件，配置ndk-build必要參數；
   2、可選創建application.mk文件，配置ndk-build參數 (該文件的配置項可使用gradle的配置替代)；
   3、使用gradle配置Android.mk以及native相關參數；

2、如何編譯庫文件（兩種方式）：
   1、Android Studio執行Build即可（執行了：Android.mk + gradle配置）；
   2、也可在Terminal、Mac終端、cmd終端中通過ndk-build命令直接構建庫文件（執行了：Android.mk）

2、環境搭建

JNI安裝
JNI 是JDK里的內容，電腦上正確安裝並配置JDK即可 (JDK1.1之後就正式支持了);

NDK安裝
可從官網自行下載、解壓到本地，也可基於AndroidStudio下載解壓到默認目錄;

編譯工具安裝
cmake 可基於AndroidStudio下載安裝;
ndk-build 是NDK里的腳本工具，NDK安裝好即可使用ndk-build;

當前演示，使用的Android Studio版本如下（當前最新版）：

啟動Android Studio –> 打開SDK Manager –> SDK Tools，如下圖所示：

我們選擇NDK、CMake、LLDB（調試Native時才會使用），選擇Apply進行安裝，等安裝成功后，NDK開發所依賴的環境也就都齊全了。

3、Native C++ 項目（HelloWord案例）

3.1、項目創建（java / kotlin）

新建項目，選擇 Native C++，如下圖：

新創建的項目，默認已包含完整的native 示例代碼、cmake配置 ，如下圖：

這樣，我們就可以自己定義Java native方法，並在cpp目錄中寫native實現了，很方便。

但是，當我們寫完native的實現代碼，希望運行APP，查看JNI的交互效果，此時，就需要使用編譯工具了，咱們還是先看一下Android Studio默認的Native編譯方式吧：CMake

3.2、CMake的應用

在CMake編譯之前，咱們應該先做哪些準備工作？

1、NDK環境是否配置正確？
-- 如果未配置正確是無法進行C/C++開發的，更不用說CMake編譯了

2、C/C++功能是否實現？ 
-- 此次演示主要使用系統默認創建的native-lib.cpp文件，關於具體如何實現：後續文章再詳細講解

3、CMakeLists.txt是否創建並正確配置？ 
-- 該文件是CMake工具編譯的基礎，未配置或配置項錯誤，均會影響編譯結果

4、gradle是否正確配置？
-- gradle配置也是CMake工具編譯的基礎，未配置或配置項錯誤，均會影響編譯結果

除此之外，咱們還應該學習CMake的哪些重要知識？

1、CMake工具編譯生成的庫文件默認在什麼位置？apk中庫文件又是在什麼位置？
2、CMake工具如何指定編譯生成的庫文件位置？
3、CMake工具如何指定生成不同CPU平台對應的庫文件？

帶着這些問題，咱們開始CMake之旅吧：

3.2.1、NDK環境檢查

編譯前，建議先檢查下工程的NDK配置情況（不然容易報一些亂七八糟的錯誤）：
File –> Project Structure –> SDK Location，如下圖（我本地的Android Studio默認沒有給配置NDK路徑，那麼，需要自己手動指定一下）：

3.2.2、C/C++功能實現

因為本節主講CMake編譯工具，代碼就不單獨寫了，咱們直接使用工程默認生成的native-liv.cpp，簡單調整一下native實現方法的代碼吧（修改返迴文本信息）：

因Native C++工程默認已配置好了CMakeLists.txt和gradle，所以咱們可直接運行工程看效果，如下圖：

JNI交互效果我們已經看到了，說明CMake編譯成功了。那麼，這究竟是怎麼做到的呢？咱們接着分析一下吧：

3.2.3、CMake生成的庫文件與apk中的庫文件

安卓工程編譯時，會執行CMake編譯，在 工程/app/build/…/cmake/ 中會產生對應的so文件，如下圖：

繼續編譯安卓工程，會根據build中的內容，生成我們的*.apk安裝包文件。我們找到、反編譯apk安裝包文件，查找so庫文件。原來在apk安裝包中，so庫都被存放在lib目錄中，如下圖：

3.2.4、CMake是如何編譯生成so庫的呢？

在前面介紹CMake定義時，提到了CMake是基於CMakeLists.txt文件和gradle配置實現編譯Native類的。那麼，咱們先來看一下CMakeLists.txt文件吧：

#cmake最低版本要求
cmake_minimum_required(VERSION 3.4.1)

#添加庫
add_library(
        # 庫名
        native-lib

        # 類型：
        # SHARED 是指動態庫，對應的是.so文件
        # STATIC 是指靜態庫，對應的是.a文件
        # 其他類型:略
        SHARED

        # native類路徑
        native-lib.cpp)

# 查找依賴庫
find_library( 
        # 依賴庫別名
        log-lib

        # 希望加到本地的NDK庫名稱，log指NDK的日誌庫
        log)


# 鏈接庫，建立關係（ 此處就是指把log-lib 鏈接給 native-lib使用 ）
target_link_libraries( 
        # 目標庫名稱（native-lib 是咱們要生成的so庫）
        native-lib

        # 要鏈接的庫（log-lib 是上面查找的log庫）
        ${log-lib})

實際上，CMakeList.txt可配置的內容遠不止這些，如：so輸出目錄，生成規則等等，有需要的同學可查下官網。

接着，咱們再看一下app的gradle又是如何配置CMake的呢？

apply plugin: 'com.android.application'

android {
    compileSdkVersion 29
    buildToolsVersion "29.0.1"
    defaultConfig {
        applicationId "com.qxc.testnativec"
        minSdkVersion 21
        targetSdkVersion 29
        versionCode 1
        versionName "1.0"
        testInstrumentationRunner "androidx.test.runner.AndroidJUnitRunner"
        //定義cmake默認配置屬性
        externalNativeBuild {
            cmake {
                cppFlags ""
            }
        }
    }
    
    //定義cmake對應的CMakeList.txt路徑（重要）
    externalNativeBuild {
        cmake {
            path "src/main/cpp/CMakeLists.txt"
        }
    }
}

dependencies {
    implementation fileTree(dir: 'libs', include: ['*.jar'])
    implementation 'androidx.appcompat:appcompat:1.1.0'
    implementation 'androidx.constraintlayout:constraintlayout:1.1.3'
    testImplementation 'junit:junit:4.12'
    androidTestImplementation 'androidx.test.ext:junit:1.1.1'
    androidTestImplementation 'androidx.test.espresso:espresso-core:3.2.0'
}

實際上，gradle可配置的cmake內容也遠不止這些，如：abi、cppFlags、arguments等，有需要的同學可查下官網。

3.2.5、如何指定庫文件的輸出目錄？

如果希望將so庫生成到特定目錄，並讓項目直接使用該目錄下的so，應該如何配置呢？
比較簡單：需要在CMakeList.txt中配置庫的輸出路徑信息，即：

CMAKE_LIBRARY_OUTPUT_DIRECTORY

# cmake最低版本要求
cmake_minimum_required(VERSION 3.4.1)

# 配置庫生成路徑
# CMAKE_CURRENT_SOURCE_DIR是指 cmake庫的源路徑，通常是build/.../cmake/
# /../jniLibs/是指與CMakeList.txt所在目錄的同級目錄：jniLibs (如果沒有會新建)
# ANDROID_ABI 生成庫文件時，採用gradle配置的ABI策略（即：生成哪些平台對應的庫文件）
set(CMAKE_LIBRARY_OUTPUT_DIRECTORY ${CMAKE_CURRENT_SOURCE_DIR}/../jniLibs/${ANDROID_ABI})

# 添加庫
add_library( # 庫名
        native-lib

        # 類型：
        # SHARED 是指動態庫，對應的是.so文件
        # STATIC 是指靜態庫，對應的是.a文件
        # 其他類型:略
        SHARED

        # native類路徑
        native-lib.cpp)

# 查找依賴庫
find_library(
        # 依賴庫別名
        log-lib

        # 希望加到本地的NDK庫名稱，log指NDK的日誌庫
        log)


# 鏈接庫，建立關係（ 此處就是指把log-lib 鏈接給native-lib使用 ）
target_link_libraries(
        # 目標庫名稱（native-lib就是咱們要生成的so庫）
        native-lib

        # 要鏈接的庫（上面查找的log庫）
        ${log-lib})

還需要在gradle中配置 jniLibs.srcDirs 屬性（即：指定了lib庫目錄）：

sourceSets {
        main {
            jniLibs.srcDirs = ['jniLibs']//指定lib庫目錄
        }
    }

接着，重新build就會在cpp相同目錄級別位置生成jniLibs目錄，so庫也在其中了：

注意事項：
1、配置了CMAKE_CURRENT_SOURCE_DIR，並非表示編譯時直接將so生成在該目錄中，實際編譯時，so文件仍然是
先生成在build/.../cmake/中，然後再拷貝到目標目錄中的

2、如果只配置了CMAKE_CURRENT_SOURCE_DIR，並未在gradle中配置 jniLibs.srcDirs，也會有問題，如下：
More than one file was found with OS independent path 'lib/arm64-v8a/libnative-lib.so'

此問題是指：在編譯生成apk時，發現了多個so目錄，android studio不知道使用哪一個了，所以需要咱們
告訴android studio當前工程使用的是jniLibs目錄，而非build/.../cmake/目錄

3.2.5、如何生成指定CPU平台對應的庫文件呢？

我們可以在cmake中設置abiFilters，也可在ndk中設置abiFilters，效果是一樣的：

defaultConfig {
        applicationId "com.qxc.testnativec"
        minSdkVersion 21
        targetSdkVersion 29
        versionCode 1
        versionName "1.0"
        testInstrumentationRunner "androidx.test.runner.AndroidJUnitRunner"
        externalNativeBuild {
            cmake {
                cppFlags ""
                abiFilters "arm64-v8a"
            }
        }
    }

defaultConfig {
        applicationId "com.qxc.testnativec"
        minSdkVersion 21
        targetSdkVersion 29
        versionCode 1
        versionName "1.0"
        testInstrumentationRunner "androidx.test.runner.AndroidJUnitRunner"
        externalNativeBuild {
            cmake {
                cppFlags ""
            }
        }
        ndk {
            abiFilters "arm64-v8a"
        }
    }

按照新的配置，我們重新運行工程，如下圖：

再反編譯看下工程，果然只有arm64-v8a的so庫了，不過庫文件在apk中仍然是放在lib目錄，而非jniLibs（其實也很好理解，jniLibs只是我們本地的目錄，便於我們管理庫文件，真正生成apk時，仍然會按照lib目錄放置庫文件），如下圖：

至此，CMake的主要技術點都講完了，接下來咱們看下NDK-Build吧~

3.3、ndk-build的應用

在ndk-build編譯之前，咱們又應該先做哪些準備工作？

1、ndk-build環境變量是否正確配置？
-- 如果未配置，是無法在cmd、Mac終端、Terminal中使用ndk-build命令的（會報錯：找不到命令）

2、NDK環境是否配置正確？
-- 如果未配置正確是無法進行C/C++開發的，更不用說ndk-build編譯了

3、C/C++功能是否實現？
-- 此次演示主要使用系統默認創建的native-lib.cpp文件，關於具體如何實現：後續文章再詳細講解
-- 注意：為了與CMake區分，咱們新建一個“jni”目錄存放C/C++文件、配置文件吧

4、Android.mk是否創建並正確配置？ 
-- 該文件是ndk-build工具編譯的基礎，未配置或配置項錯誤，均會影響編譯結果

5、gradle是否正確配置？(可選項，如果通過cmd、Mac終端、Terminal執行ndk-build，可忽略)
-- gradle配置也是ndk-build工具編譯的基礎，未配置或配置項錯誤，均會影響編譯結果

6、Application.mk是否創建並正確配置？（可選項，一般配ABI、版本，這些項均可在gradle中配置）
-- 該文件也是ndk-build工具編譯的基礎，未配置或配置項錯誤，均會影響編譯結果

除此之外，咱們還應該學習ndk-build的哪些重要知識？

1、ndk-build工具如何指定編譯生成的庫文件位置？
2、ndk-build工具如何指定生成不同CPU平台對應的庫文件？

帶着這些問題，咱們繼續ndk-build之旅吧：

3.3.1、環境變量配置

介紹NDK-Build定義時，提到了其實它是NDK的腳本工具。那麼，咱們還是先進NDK目錄找一下吧，ndk-build工具的位置如下圖：

如果我們希望任意情況下都能便捷的使用這種腳本工具，通常做法是配置其環境變量，否則我們在cmd、Mac終端、Terminal中執行 ndk-build 命令時，會報錯：“未找到命令”

配置NDK的環境變量，也很簡單，以Mac電腦舉例（如果是Windows電腦，網上也有很多關於配置環境變量的文章，如果有需要可自行查下）：

1、打開命令終端，輸入命令： open -e .bash_profile，打開bash_profile配置文件

2、寫入如下內容（NDK_HOME指向 ndk-build 所在路徑）：
export NDK_HOME=/Users/xc/SDK/android-sdk-macosx/ndk/20.1.5948944
export PATH=$PATH:$NDK_HOME

3、生效.bash_profile配置
source .bash_profile

當我們在cmd、Mac終端、Terminal中執行 ndk-build 命令時，如果出現下圖所示內容，則代表配置成功了：

3.3.2、C/C++功能實現

咱們使用比較常用的一種ndk-build方式吧：ndk-build + Android.mk + gradle配置

項目中新建jni目錄，拷貝一份CMake的代碼實現吧：

1、新建jni目錄
2、拷貝cpp/native-lib.cpp 至 jni目錄下
3、重命名為haha.cpp （與CMake區分）
4、調整一下native實現方法的文本（與CMake運行效果區分）
5、新建Android.mk文件

接着，編寫Android.mk文件內容：

#表示Android.mk所在目錄
LOCAL_PATH := $(call my-dir)

#CLEAR_VARS變量指向特殊 GNU Makefile，用於清除部分LOCAL_變量
include $(CLEAR_VARS)

#模塊名稱
LOCAL_MODULE    := haha
#構建系統用於生成模塊的源文件列表
LOCAL_SRC_FILES := haha.cpp

#BUILD_SHARED_LIBRARY 表示.so動態庫
#BUILD_STATIC_LIBRARY 表示.a靜態庫
include $(BUILD_SHARED_LIBRARY)

配置gradle：

apply plugin: 'com.android.application'
android {
    compileSdkVersion 28
    defaultConfig {
        applicationId "com.aaa.testnative"
        minSdkVersion 16
        targetSdkVersion 28
        versionCode 1
        versionName "1.0"
        testInstrumentationRunner "android.support.test.runner.AndroidJUnitRunner"

        //定義ndkBuild默認配置屬性
        externalNativeBuild {
            ndkBuild {
                cppFlags ""
            }
        }
    }
   
    //定義ndkBuild對應的Android.mk路徑（重要）
    externalNativeBuild {
        ndkBuild{
            path "src/main/jni/Android.mk"
        }
    }
}

dependencies {
    implementation fileTree(dir: 'libs', include: ['*.jar'])
    implementation 'com.android.support:appcompat-v7:28.0.0'
    implementation 'com.android.support.constraint:constraint-layout:1.1.3'
    testImplementation 'junit:junit:4.12'
    androidTestImplementation 'com.android.support.test:runner:1.0.2'
    androidTestImplementation 'com.android.support.test.espresso:espresso-core:3.0.2'
}

現在，native代碼、ndk-build配置都完成了，咱們運行看一下效果吧，如下圖：

3.3.4、如何指定庫文件的輸出目錄？

通常，可在Android.mk文件中配置NDK_APP_DST_DIR
指定源目錄與輸出目錄（與CMake類似）

#表示Android.mk所在目錄
LOCAL_PATH := $(call my-dir)

#設置庫文件的輸入目錄
#輸出目錄 ../jniLibs/
#源目錄 $(TARGET_ARCH_ABI)
NDK_APP_DST_DIR=../jniLibs/$(TARGET_ARCH_ABI)

#CLEAR_VARS變量指向特殊 GNU Makefile，用於清除部分LOCAL_變量
include $(CLEAR_VARS)

#模塊名稱
LOCAL_MODULE    := haha
#構建系統用於生成模塊的源文件列表
LOCAL_SRC_FILES := haha.cpp

#BUILD_SHARED_LIBRARY 表示.so動態庫
#BUILD_STATIC_LIBRARY 表示.a靜態庫
include $(BUILD_SHARED_LIBRARY)

3.3.5、如何生成指定CPU平台對應的庫文件呢？

可在gradle中配置abiFilters（與Cmake類似）

externalNativeBuild {
            ndkBuild {
                cppFlags ""
                abiFilters "arm64-v8a"
            }
        }

externalNativeBuild {
            ndkBuild {
                cppFlags ""
            }
        }
  ndk {
            abiFilters "arm64-v8a"
        }

3.3.6、如何在Terminal中直接通過ndk-build命令構建庫文件呢？

除了執行AndroidStudio的build命令，基於gradle配置 + Android.mk編譯生成庫文件，我們還可以在cmd、Mac 終端、Terminal中直接通過ndk-build命令構建庫文件，此處以Terminal為例進行演示吧：

先進入包含Android.mk文件的jni目錄（Android Studio中可直接選中jni目錄並拖拽到Terminal中，會自動跳轉到該目錄），再執行ndk-build命令，如下圖：

同樣，編譯也成功了，如下圖：

因是直接在Terminal中執行了ndk-build命令，所以只會根據Android.mk進行編譯（不包含gradle配置內容，也就不會執行abiFilters過濾），生成了所有默認CPU平台的so庫文件。

ndk-build命令其實也可以配上一些參數使用，此處就不再詳解了。日常開發時，還是建議選擇CMake作為Native編譯工具，因為是安卓主推的，而且更簡單一些。

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

※想知道網站建置、網站改版該如何進行嗎?將由專業工程師為您規劃客製化網頁設計及後台網頁設計

※不管是台北網頁設計公司、台中網頁設計公司，全省皆有專員為您服務

※Google地圖已可更新顯示潭子電動車充電站設置地點!!

※帶您來看台北網站建置，台北網頁設計，各種案例分享

一、摘要

在集合系列的第一章，咱們了解到，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、

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

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

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

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

前言： 不知不覺已經工作了快 7 個月了，去年這個時候還躋身在考研的大軍中，不禁有些感慨… 結合這 7 個月發生的一些事情，簡單做一下總結吧…

為獲得更好的閱讀體驗，請訪問原文地址：

一、那時候剛入職

不同於其他同學忙於畢設的 4 月，提早安排趁寒假已經完成畢設的我，已經開始撲在了「找工作」這件事上，有了去年「秋招」打下的基礎，複習起來快了很多，沒過多久就開始投簡歷面試了，面試也總體比較順利，剛面沒幾家就迅速和一家自己看好的初創公司簽下了。

公司使用的技術棧區別於自己熟悉的 Java/ MySQL 這一套，而是主要使用的 Rails/ MongoDB，所以剛入職的一段時間，基本上都是在自己熟悉技術棧，也趁着閑暇的時間，把自己入門時候的一些學習心得寫成了文章發表：

• MongoDB【快速入門】：
• Java轉Ruby【快速入門】：

對於職場小白來說，所謂「職場」還是顯得有些陌生，剛來的時候，雖然跟周圍的同事都稀鬆平常地打了一圈兒招呼，坐下之後，隨着他們又埋頭噼里啪啦敲打鍵盤工作的深入，又頓覺周圍一片陌生，還挺奇妙的，在第一周完的周報裏面我寫道：

剛來公司有些迷茫，只是看着CheckList對照着熟悉一些技術，也不了解自己應該要熟悉到哪種程度，就希望自己能再主動些，不管是技術問題還是其他問題多請教，然後儘快跟其他成員熟悉起來。

剛開始上手的時候也有好多問題不懂，我都習慣性的選擇自己研究一陣兒，因為自己有寫博客的一些經歷，被問過好多一搜索 or 自己一嘗試就能解決的問題，所以比較克制，但是後來「入職 1v1」溝通的時候被說到有問題別自己死磕，半個小時沒解決盡量就找一下旁邊的同事。摁？我一下子就把我的「主動性」發揮了出來。

不過好記性也不如爛筆頭，找了一些工具記錄把這些「問題的答案」都記錄了下來，方便之後再查找，當時對於 Git 都不是很熟悉，也記錄了很多常用的命令在裏面，還有一些問題的反饋，甚至知道了月會要自我介紹，也打了一遍草稿記錄在了這裏：（那段時間真的問了好多問題，周報里也手動感謝了坐我旁邊的兩位大佬..）

入職兩周的時候，雖然已經開始上手做一些簡單的埋點工作，但自己對於 Ruby 還是不是特別了解和熟悉，趁着某一個雙休，抓着一本《Effetive-Ruby》啃了两天，也把自己的學習輸出了一下：

• 《Effective-Ruby》讀書筆記：

二、逐漸能夠上手

就這樣一邊熟悉，一邊開始接一些小需求，我記得我寫下的第一個 BUG，就報出了 6K 條記錄.. 慌慌張張在修復之後我不禁感嘆：「不要太相信用戶的任何數據」。（包括 equal 反寫也是之後在錯誤之中學習到的..）

剛上手沒有一段時間，就接到了一個新項目的需求，跟着一位大佬開發一個新功能，大佬負責搭建基礎代碼和設計，我負責完成其餘的功能代碼，沒敢一絲懈怠，下班回家之後也對照着別人寫的代碼敲敲敲，時間和完成度上倒是沒有一絲耽擱，只是現在回過頭一想，當時沒有什麼單元測試的概念和意識，就自己在本地 Post-Man 測試完就完，所幸比較簡單 + 自己測試得比較仔細，到現在也沒有出現過什麼問題。

工作對我這樣的小白另一個好處就是：「見識和增加技術的廣度」。公司所使用技術棧不論是廣度還是深度，都是自己在大學本科的學習中不可企及的程度，Jekins？Docker？K8S？跳板機？一下子冒出來好多新鮮陌生的名詞，懷着好奇心也嘗試了解了一些：

• 了解【Docker】從這裏開始：
• 「消息隊列」看過來！：
• Kafka【入門】就這一篇！：

也隨着公司的逐漸壯大，各模塊的耦合也越發嚴重，各條業務線之間的協作溝通成本越來越大，逐漸開始提出「微服務」這樣的概念，具體怎麼樣理解就不作討論了，總之就是期望通過梳理/ 重構/ 拆服務的方式來解決「協作」問題，所以期間也開始了解學習一些這方面的東西：

• 什麼是微服務？：
• 《重構：改善既有代碼的設計》讀書筆記：

甚至期間還做了一些「微服務」的調研，我們選用什麼樣的姿勢和技術棧更加合適，所以也輸出了一些關於「Spring Cloud」的東西，但是最終駁回的原因是待我們整個容器化之後 k8s 平台自帶了這麼一套東西，業務同學只需要關心業務代碼就行了，也就沒有繼續深入了：

• 你想了解的「Spring Cloud」都在這裏：

然後我們在拆解的過程中，也借鑒到一些「DDD」的思想，也嘗試進行了一波學習：

• 【吐血推薦】領域驅動設計學習輸出：

總之，這一段時間我一邊通過各種小需求，接觸和了解了公司的系統的大半，一邊學習和了解着各種不同的技術，增加了技術上的廣度。

三、開始負責一些項目

為了加速服務化的推進工作和驗證「DDD」的一些東西，部門老大把一個邊界足夠清晰，也足夠小的一個模塊單獨交給我，期望我快速上線，不過最終交付已經逾期快大半個月了.. 雖然從最終的結果來看，順利交付完成了拆解任務並從 MongoDB 數據庫轉變成了 MySQL.. 但期間也踩過好些坑，當然也學習到一些東西..

例如我真實地意識到「完美」這個詞的理想化。就拿設計 API 來說吧.. 自己就基於 RESTful 風格設計了好幾版.. 左想右想都覺得差一些，有一些接口覺得怎麼設計都不優雅.. 後來糾結一陣子也就放棄了.. 再例如寫代碼這件事情吧，好的代碼整潔的代碼是一次一次迭代和重構中出來的，如果一開始就想着寫出「完美」的代碼，那麼最終的結果可能就是寫不出來代碼。

另外一個小插曲是，在做數據遷移的時候，我差點把線上服務器搞掛了.. 我在測試環境驗證了一把之後，就直接在線上進行操作了，因為當時對於數據庫的操作管控還沒有那麼嚴格，加上自己對於線上環境的複雜程度認識不足，我就起了 50 個線程，去分批量地讀取 MongoDB 的數據遷移到 MySQL，造成了線上庫的性能報警，就趕緊停了.. 緊接着就被一群大佬抓進了一個會議室做事件的復盤..

說實話，我緊張壞了，第一次經歷這樣的算是「事故」的情況吧，差一點線上就被我搞掛啦，一時間不知所措… 讓人感到溫暖的是部門老大隨即丟來的消息：

那天還有一些相關的同事都陪我寫復盤郵件到了晚上 10：30，現在想來都十分感謝他們。後來回到家我還打電話給我媽，我說我在工作中犯錯了，我做了xxxx這些動作，你覺得我做的怎麼樣呢，老媽的回復也讓人安心，只是現在想來，一些後續的動作可以做得更好的…

因為「埋點」這件事涉及到系統的方方面面，我也藉此了解了很多不同的模塊，也是拜這一點所賜吧，後來我被派到各種各樣的支援任務中，同樣也因為對不同模塊都還不算陌生，都還算完成得不錯吧…

時間一晃，在公司就四個月過去了，也在這個過程中從各個大佬那兒都學到了一些東西，在 8 月底發的周報裏面我寫下了以下的總結：

之後也跟着大佬碰了一些公司的核心模塊，期間也沒有停止在工作中不斷地做學習輸出：

• Git 原理入門解析：
• Java計時新姿勢√：
• Java8流操作-基本使用&性能測試：
• 《代碼整潔之道》讀書筆記：
• React 入門學習：
• 談一談依賴倒置原則：

四、回顧做的不好的部分

• 對代碼還沒有保持足夠的敬畏之心。

特別是一開始上手的時候，有時候甚至是在線上環境搞測試，後來越來越注重 codereview 和單元測試好了很多。

• 溝通還不夠深入/ 到位

有一次是臨時接到一個需求，因為「通用語言」沒有達成一致，導致最終交付的結果不符合產品的期望，最終我們所有相關人員在一起開了一個會，統一了「通用語言」，造成了額外的工作和負擔，拿到需求就應該確認好相關事宜的，越底層越細節越好，這方面的能力我仍然欠缺，但我已經持續在注意當中。

另一次也是因為這一點，我需要幫助 A 系統擁有某一項功能，之前 A 系統已經介入了 B 系統完成了部分功能，我因為沒有進一步地確認 B 系統的現狀，就去接入了有完整功能的 C 系統，但其實 B 系統已經在上一周和開發 C 系統和 A 系統的同學對接好了，並完成了相關功能的接入，少了這一部分的溝通，就造成了不少額外的工作量.. 所以「溝通」還是非常重要的，也只能說持續進步吧…

• 缺少一些主動性

當我頭上掛着一些事情的時候，還是能夠保持着效率的，只是當我做完了，就時常缺乏一些主動地思考了，通常都是被動地去詢問同小組的同事有什麼事情是需要幫忙的.. 雖然也积極地參与到自己感興趣的那些技術評審之類的事情之中，但似乎效果都不佳.. 也沒有什麼實際好的輸出..

• 接了一些私活兒黑活兒（沒有充分考慮團隊之間的配合）

因為「埋點」會接觸各個平台的童鞋，並且時常變化和有一些新的需求，有時候直接繞過了一些環節，直接找上我了，我心想直接自己弄弄改改就可以了，也就沒多想… 但是現在想來，這樣跨團隊的事情，不能越過「頂頭上司」私自進行，一方面經常我的 BOSS 不知道我接了活兒，另一方面這樣的私自對接就會造成一些信息的流失，對於團隊之內還是團隊之間都會造成影響…

五、回顧做得好的部分

• 養成了閱讀的習慣

公司買書是免費的，也有自己的圖書館，同事也不乏喜歡閱讀學習的，所以跟着跟着就養成了閱讀的習慣，期間也學習到了一些方法論的東西，貼一下入職以來讀過的那些書吧：（技術類的就沒有囊括了）

其實每天閱讀的時間也不長，想我大學總共捧起的那麼些課外書，不禁有些唏噓…

• 早睡早起 + 晨間日記

早睡早起，從步入職場以來，就發現這樣的習慣會帶來一些額外的價值，例如一些閱讀我會放在早上，後來還加入了「晨間日記」，用來「回顧前一天的事情」和提前部署「今天的任務」，這不禁讓我多了一份清醒，也讓現在不怎麼鍛煉的我每一天精力更加好一些：（目前正在從印象筆記往 Notion 逐步遷移的過程中）

• 學習撰寫 Commit Message && 遵守一些 Git 規範

起初使用 Git 十分不規範，後來向大佬那兒學習到了如何標準地提交 Commit，包括 Commit Message 應該怎麼寫，我覺得這是一個很好的習慣，每一個 Commit 都有上下文，並且還帶上了 JIRA 號，任務也很好跟蹤，雖然公司並沒有大範圍地盛行起來，但我覺得這樣好習慣應該堅持下來：

• 任務進度及時反饋給相關人員

自己比較注意這一點，因為不這樣做會讓別人感受不怎麼好.. 光是自己心裏清楚是不行的.. 要保持信息的通暢才行，及時反饋是很重要的一步..

• 自己先 review 一遍代碼

犯過一些白痴錯誤之後，就有些擔心，逐步養成了自己先 review 一遍代碼的習慣..

六、小結 && 展望

總的來說，看着自己這樣一步一步成長過來，沒有很懈怠，自己就算比較滿意了，在工作中學習了很多東西，不管是技術上的硬技能，還是溝通中的軟技能，也認識到了很多厲害的大佬和有趣的小夥伴們..

感恩在路上相遇，有幸共同行走過一段已然算是幸運，突然翻看起自己的朋友圈有一句話說得好：「成長從來都不是告別過去，成長是更加堅定的看向未來！」

期待一路同行的大家，都能夠 Be Better！

按照慣例黏一個尾巴：

歡迎轉載，轉載請註明出處！
獨立域名博客：wmyskxz.com
簡書ID：
github：
歡迎關注公眾微信號：wmyskxz
分享自己的學習 & 學習資料 & 生活
想要交流的朋友也可以加qq群：3382693
錢

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

※想知道網站建置、網站改版該如何進行嗎?將由專業工程師為您規劃客製化網頁設計及後台網頁設計

※不管是台北網頁設計公司、台中網頁設計公司，全省皆有專員為您服務

※Google地圖已可更新顯示潭子電動車充電站設置地點!!

※帶您來看台北網站建置，台北網頁設計，各種案例分享