map函數源碼

① golang map源碼淺析

golang 中 map的實現結構為： 哈希表 + 鏈表。 其中鏈表，作用是當發生hash沖突時，拉鏈法生成的結點。

可以看到， []bmap 是一個hash table， 每一個 bmap是我們常說的「桶」。 經過hash 函數計算出來相同的hash值， 放到相同的桶中。 一個 bmap中可以存放 8個 元素， 如果多出8個，則生成新的結點，尾接到隊尾。

以上是只是靜態文件 src/runtime/map.go 中的定義。 實際上編譯期間會給它加料 ，動態地創建一個新的結構：

上圖就是 bmap的內存模型， HOB Hash 指的就是 top hash。 注意到 key 和 value 是各自放在一起的，並不是 key/value/key/value/... 這樣的形式。源碼里說明這樣的好處是在某些情況下可以省略掉 padding 欄位，節省內存空間。

每個 bmap設計成 最多隻能放 8 個 key-value 對 ，如果有第 9 個 key-value 落入當前的 bmap，那就需要再構建一個 bmap，通過 overflow 指針連接起來。

map創建方法:

我們實際上是通過調用的 makemap ，來創建map的。實際工作只是初始化了hmap中的各種欄位，如：設置B的大小， 設置hash 種子 hash 0.

注意 :

makemap 返回是*hmap 指針， 即 map 是引用對象， 對map的操作會影響到結構體內部 。

使用方式

對應的是下面兩種方法

map的key的類型，實現了自己的hash 方式。每種類型實現hash函數方式不一樣。

key 經過哈希計算後得到hash值，共 64 個 bit 位。 其中後B 個bit位置， 用來定位當前元素落在哪一個桶里， 高8個bit 為當前 hash 值的top hash。 實際上定位key的過程是一個雙重循環的過程， 外層循環遍歷 所有的overflow， 內層循環遍歷 當前bmap 中的 8個元素 。

舉例說明： 如果當前 B 的值為 5， 那麼buckets 的長度 為 2^5 = 32。假設有個key 經過hash函數計算後，得到的hash結果為：

外層遍歷bucket 中的鏈表

內層循環遍歷 bmap中的8個 cell

建議先不看此部分內容，看完後續 修改 map中元素 -> 擴容 操作後 再回頭看此部分內容。

擴容前的數據：

等量擴容後的數據：

等量擴容後，查找方式和原本相同， 不多做贅述。

兩倍擴容後的數據

兩倍擴容後，oldbuckets 的元素，可能被分配成了兩部分。查找順序如下：

此處只分析 mapaccess1 ,。 mapaccess2 相比 mapaccess1 多添加了是否找到的bool值， 有興趣可自行看一下。

使用方式：

步驟如下：

擴容條件 ：

擴容的標識 ： h.oldbuckets ！= nil

假設當前定位到了新的buckets的3號桶中，首先會判斷oldbuckets中的對應的桶有沒有被搬遷過。 如果搬遷過了，不需要看原來的桶了，直接遍歷新的buckets的3號桶。

擴容前：

等量擴容結果

雙倍擴容會將old buckets上的元素分配到x， y兩個部key & 1 << B == 0 分配到x部分，key & 1 << B == 1 分配到y部分

注意： 當前只對雙倍擴容描述， 等量擴容只是重新填充了一下元素， 相對位置沒有改變。

假設當前map 的B == 5，原本元素經過hash函數計算的 hash 值為：

因為雙倍擴容之後 B = B + 1，此時B == 6。key & 1 << B == 1, 即 當前元素rehash到高位，新buckets中 y 部分. 否則 key & 1 << B == 0 則rehash到低位，即x 部分。

使用方式：

可以看到，每一遍歷生成迭代器的時候，會隨機選取一個bucket 以及 一個cell開始。 從前往後遍歷，再次遍歷到起始位置時，遍歷完成。

https://www.qcrao.com/2019/05/22/dive-into-go-map/

https://draveness.me/golang/docs/part2-foundation/ch03-datastructure/golang-hashmap/

https://www.bilibili.com/video/BV1Q4411W7MR?spm_id_from=333.337.search-card.all.click

② matlab中「colormap(map) map」為什麼沒被定義

1、colormap函數：獲取當前色圖

2、用法說明：colormap(map)函數設置或獲取當前圖像的色圖。

參量map為一個m×3的、元素在[0,1]之間的實數矩陣，每一行是定義一種顏色的一個RGB向量。

顏色圖的第k行定義第k種顏色，其中map(k,:)=[r(k) g(k) b(k)]定義紅綠藍的亮度。

3、實例

(1)源碼

③ c++中的map函數問題，求高手解答我的疑惑

你應該說的是：

map<string,int>q;

map的[]取值，有一個特性，對於上面的q來說，

q[i]++;

找不到對應的關鍵值i時，它首先會執行

q[i]=初始值;

其中，初始值對int、double一類的系統預定義類型，是取0，對於類，是直接調用無參構造函數。比如上面的實際執行效果為：

q[i]=0;

然後，才會執行

q[i]++;

這一句。

以後再執行同樣i值的上面這一句時，就不會再次賦初值了。

整個輸入數據中，Andy一共在4行中出現，排除重復的一行，一共出現3次，故Andy最後的朋友數為3。

④ C++map類中find函數的實現

map::find和map::end的返回值的是迭代器類iterator
class iterator類中數據成員是指針，指向map底層實現的紅黑樹的節點
iterator定義的operator==/!=函數是比較這個指針是否相等
因此與自定義的類是否定義/重載了operator==/!=函數無關
另外想要知道細節，按F11進入源代碼調試

⑤ Map類型：ClickHouse中對動態欄位的支持

在互動式分析場景下，很多時候除了固定欄位之外，還會有一些動態欄位的需求。比如，在游戲場景下，需要動態存儲用戶每個游戲的play時長。

這種場景下，我們希望在一張表中同時存儲固定欄位和動態欄位的信息，並且可以高效地使用動態欄位做過濾查詢。

CREATE TABLEuser_game_play

(

     mid UInt64,

   buvidString,

     game_play_rationMap(String, UInt32),

   log_dateString

)

ENGINE=MergeTree()

PARTITION BY log_date

ORDER BYmid;  

insert into user_game_play values (1, '123',  map(' 王者榮耀 ',3600, 'FGO', 1800), '2021-11-14');

SELECT game_play_ration[' 王者榮耀 '] AS ration  FROM test.user_game_play

┌─ration─┐

│    3600 │

└──────────┘

ClickHouse從 v21.1.2.15-stable 版本開始支持Map類型（詳見PR #1586 ），其讀取key對應value的實現邏輯大致如下：

1. 內部用兩個數組(ColumnArray)分別存儲key和value值，我們分別稱之為 key_array和value_array。

2. 對於Map的取值操作（即map[『key』]操作），先在從key_array中找到要找的key的下標，然後根據這個下標到value_array里獲取對應的值。

具體實現細節詳見源碼 FunctionArrayElement::executeMap .

從上述分析可知，Map類型的工作方式本質上和用兩個數組分別存儲key和value的方式是一樣的。只是在功能上做了封裝，提高了用戶使用的便捷性，但在性能上並沒有變化。

為了提升map操作的性能，我們在社區版本的Map類型基礎上，給其加上了多種類型的skipping

index，包括 bloom_filter ，tokenbf_v1，ngrambf_v1

上面這三種skipping index本質上都是用bloom filter存儲每個索引粒度的索引值。其中，tokenbf_v1和ngrambf_v1隻支持String類型，bloom_filter可支持各種類型。

1. ngrambf_v1是對字元串中固定長度的substring做bloom filter存儲和檢索。

2. tokenbf_v1是對由非字母數字元號分隔開的token做bloom filter存儲和檢索。

3. bloom_filter則是直接對欄位取值做bloom filter存儲和檢索。

在數據寫入到Map類型欄位時，所有的key會被抽取出來生成每個索引粒度對應的bloom filter。

對於針對Map類型欄位的過濾條件，如：

     where game_play_ration[『王者榮耀』] >= 1800 and game_play_ration[『王者榮耀』] <=3600

會做以下處理：

1. 從filtering condition中提取map的key。

2. 分析過濾操作符（如 = , >=, <=, >, <, like , in , not in），如果該過濾條件在map不包含對應key時不可能成立，則利用bloom filter過濾掉不可能包含對應key的數據塊（索引粒度）。

具體實現細節詳見源碼PR #28634 。

CREATE TABLEuser_game_play

(

     mid UInt64,

     buvidString,

     game_play_rationMap(String, UInt32),

     log_dateString,

     Index idx game_play_ration TYPE bloom_filter GRANULARITY 2,

)

ENGINE=MergeTree()

PARTITION BY log_date

ORDER BY mid;

在我們的性能測試中，給Map類型添加skipping index可以收獲的性能提升差異很大。

效果好的case可以十幾到幾十倍的性能提升，而效果不好的則沒有明顯提升。

跳數索引的過濾效果和兩個數據特性相關：

1. 索引值的cardinality：這個比較好理解，當索引值cardinality很小（比如性別，可取值只有男和女），那麼過濾效果通常有限。

2. 索引值的分布是否聚集：ClickHouse的跳數索引和主鍵索引一樣，也是稀疏索引。當索引值分布非常離散時，即使包含查詢值的記錄佔比很小，但可能每個數據塊（索引粒度）都包含查詢值，那麼所有數據都需要讀進內存做過濾判斷。

ClickHouse社區版本中已經實現了一些map類型相關的函數，包括：

1. map : 基於傳入的鍵值對生成Map類型對象。

2. mapKeys : 獲取map對象的所有keys。

3. mapValues : 獲取map對象的所有values

4. mapContains : 檢查map對象是否包含指定的key。

更多map相關函數細節詳見 這里 。

另外，我們添加了兩個map函數mapContainsKeyLike和mapExtractKeyLike（已合並進社區版本，詳見 這里 ） 。其中mapContainsKeyLike函數支持通過tokenbf_v1索引進行跳數過濾。

⑥ 想通過c++中的map容器實現函數分發，請教各位大神解答下疑惑

因為你使用的map的key是const char *類型，即存儲的是一個指針類型，所以在下面的代碼中使用find函數就找不到對應的key。這里主要要理解c風格字元串和c++字元串的差異。

可以將map的key類型改為string，修改後代碼：

#include<iostream>
#include<string>
#include<map>

//定義函數指針
typedefvoid(*fun)(constchar*);
//定義map容器
std::map<std::string,fun>mapTest;
voidmyPrintf(constchar*pszStr){std::cout<<pszStr<<std::endl;}

intmain(intargc,char*argv[])
{
std::cout<<"map初始化!"<<std::endl;
mapTest.insert(std::pair<std::string,fun>("myPrintf",myPrintf));
std::stringstrCmd="myPrintf";
mapTest["myPrintf"]("123");
boolisFind=(mapTest.find(strCmd)==mapTest.end())?true:false;
if(!isFind)
{
mapTest[strCmd]("aaaa");
}
else
{
std::cout<<"找不到對應的處理函數!"<<std::endl;
}
return0;
}

執行結果：

⑦ 徹底理解Golang Map

本文目錄如下，閱讀本文後，將一網打盡下面Golang Map相關面試題

Go中的map是一個指針，佔用8個位元組，指向hmap結構體; 源碼 src/runtime/map.go 中可以看到map的底層結構

每個map的底層結構是hmap，hmap包含若干個結構為bmap的bucket數組。每個bucket底層都採用鏈表結構。接下來，我們來詳細看下map的結構

bmap 就是我們常說的「桶」，一個桶裡面會最多裝 8 個 key，這些 key 之所以會落入同一個桶，是因為它們經過哈希計算後，哈希結果是「一類」的，關於key的定位我們在map的查詢和插入中詳細說明。在桶內，又會根據 key 計算出來的 hash 值的高 8 位來決定 key 到底落入桶內的哪個位置（一個桶內最多有8個位置)。

bucket內存數據結構可視化如下：

注意到 key 和 value 是各自放在一起的，並不是 key/value/key/value/... 這樣的形式。源碼里說明這樣的好處是在某些情況下可以省略掉 padding欄位，節省內存空間。

當 map 的 key 和 value 都不是指針，並且 size 都小於 128 位元組的情況下，會把 bmap 標記為不含指針，這樣可以避免 gc 時掃描整個 hmap。但是，我們看 bmap 其實有一個 overflow 的欄位，是指針類型的，破壞了 bmap 不含指針的設想，這時會把 overflow 移動到 extra 欄位來。

map是個指針，底層指向hmap，所以是個引用類型

golang 有三個常用的高級類型 slice 、map、channel, 它們都是 引用類型 ，當引用類型作為函數參數時，可能會修改原內容數據。

golang 中沒有引用傳遞，只有值和指針傳遞。所以 map 作為函數實參傳遞時本質上也是值傳遞，只不過因為 map 底層數據結構是通過指針指向實際的元素存儲空間，在被調函數中修改 map，對調用者同樣可見，所以 map 作為函數實參傳遞時表現出了引用傳遞的效果。

因此，傳遞 map 時，如果想修改map的內容而不是map本身，函數形參無需使用指針

map 底層數據結構是通過指針指向實際的元素 存儲空間 ，這種情況下，對其中一個map的更改，會影響到其他map

map 在沒有被修改的情況下，使用 range 多次遍歷 map 時輸出的 key 和 value 的順序可能不同。這是 Go 語言的設計者們有意為之，在每次 range 時的順序被隨機化，旨在提示開發者們，Go 底層實現並不保證 map 遍歷順序穩定，請大家不要依賴 range 遍歷結果順序。

map 本身是無序的，且遍歷時順序還會被隨機化，如果想順序遍歷 map，需要對 map key 先排序，再按照 key 的順序遍歷 map。

map默認是並發不安全的，原因如下：

Go 官方在經過了長時間的討論後，認為 Go map 更應適配典型使用場景（不需要從多個 goroutine 中進行安全訪問），而不是為了小部分情況（並發訪問），導致大部分程序付出加鎖代價（性能），決定了不支持。

場景: 2個協程同時讀和寫，以下程序會出現致命錯誤：fatal error: concurrent map writes

如果想實現map線程安全，有兩種方式：

方式一：使用讀寫鎖 map + sync.RWMutex

方式二：使用golang提供的 sync.Map

sync.map是用讀寫分離實現的，其思想是空間換時間。和map+RWLock的實現方式相比，它做了一些優化：可以無鎖訪問read map，而且會優先操作read map，倘若只操作read map就可以滿足要求(增刪改查遍歷)，那就不用去操作write map(它的讀寫都要加鎖)，所以在某些特定場景中它發生鎖競爭的頻率會遠遠小於map+RWLock的實現方式。

golang中map是一個kv對集合。底層使用hash table，用鏈表來解決沖突 ，出現沖突時，不是每一個key都申請一個結構通過鏈表串起來，而是以bmap為最小粒度掛載，一個bmap可以放8個kv。在哈希函數的選擇上，會在程序啟動時，檢測 cpu 是否支持 aes，如果支持，則使用 aes hash，否則使用 memhash。

map有3鍾初始化方式，一般通過make方式創建

map的創建通過生成匯編碼可以知道，make創建map時調用的底層函數是 runtime.makemap 。如果你的map初始容量小於等於8會發現走的是 runtime.fastrand 是因為容量小於8時不需要生成多個桶，一個桶的容量就可以滿足

makemap函數會通過 fastrand 創建一個隨機的哈希種子，然後根據傳入的 hint 計算出需要的最小需要的桶的數量，最後再使用 makeBucketArray 創建用於保存桶的數組，這個方法其實就是根據傳入的 B 計算出的需要創建的桶數量在內存中分配一片連續的空間用於存儲數據，在創建桶的過程中還會額外創建一些用於保存溢出數據的桶，數量是 2^(B-4) 個。初始化完成返回hmap指針。

找到一個 B，使得 map 的裝載因子在正常范圍內

Go 語言中讀取 map 有兩種語法：帶 comma 和 不帶 comma。當要查詢的 key 不在 map 里，帶 comma 的用法會返回一個 bool 型變數提示 key 是否在 map 中；而不帶 comma 的語句則會返回一個 value 類型的零值。如果 value 是 int 型就會返回 0，如果 value 是 string 類型，就會返回空字元串。

map的查找通過生成匯編碼可以知道，根據 key 的不同類型，編譯器會將查找函數用更具體的函數替換，以優化效率：

函數首先會檢查 map 的標志位 flags。如果 flags 的寫標志位此時被置 1 了，說明有其他協程在執行「寫」操作，進而導致程序 panic。這也說明了 map 對協程是不安全的。

key經過哈希函數計算後，得到的哈希值如下（主流64位機下共 64 個 bit 位）：

m: 桶的個數

從buckets 通過 hash & m 得到對應的bucket，如果bucket正在擴容，並且沒有擴容完成，則從oldbuckets得到對應的bucket

計算hash所在桶編號：

用上一步哈希值最後的 5 個 bit 位，也就是 01010 ，值為 10，也就是 10 號桶（范圍是0~31號桶）

計算hash所在的槽位:

用上一步哈希值哈希值的高8個bit 位，也就是 10010111 ，轉化為十進制，也就是151，在 10 號 bucket 中尋找** tophash 值（HOB hash）為 151* 的 槽位**，即為key所在位置，找到了 2 號槽位，這樣整個查找過程就結束了。

如果在 bucket 中沒找到，並且 overflow 不為空，還要繼續去 overflow bucket 中尋找，直到找到或是所有的 key 槽位都找遍了，包括所有的 overflow bucket。

通過上面找到了對應的槽位，這里我們再詳細分析下key/value值是如何獲取的：

bucket 里 key 的起始地址就是 unsafe.Pointer(b)+dataOffset。第 i 個 key 的地址就要在此基礎上跨過 i 個 key 的大小；而我們又知道，value 的地址是在所有 key 之後，因此第 i 個 value 的地址還需要加上所有 key 的偏移。

通過匯編語言可以看到，向 map 中插入或者修改 key，最終調用的是 mapassign 函數。

實際上插入或修改 key 的語法是一樣的，只不過前者操作的 key 在 map 中不存在，而後者操作的 key 存在 map 中。

mapassign 有一個系列的函數，根據 key 類型的不同，編譯器會將其優化為相應的「快速函數」。

我們只用研究最一般的賦值函數 mapassign 。

map的賦值會附帶著map的擴容和遷移，map的擴容只是將底層數組擴大了一倍，並沒有進行數據的轉移，數據的轉移是在擴容後逐步進行的，在遷移的過程中每進行一次賦值（access或者delete）會至少做一次遷移工作。

1.判斷map是否為nil

每一次進行賦值/刪除操作時，只要oldbuckets != nil 則認為正在擴容，會做一次遷移工作，下面會詳細說下遷移過程

根據上面查找過程，查找key所在位置，如果找到則更新，沒找到則找空位插入即可

經過前面迭代尋找動作，若沒有找到可插入的位置，意味著需要擴容進行插入，下面會詳細說下擴容過程

通過匯編語言可以看到，向 map 中刪除 key，最終調用的是 mapdelete 函數

刪除的邏輯相對比較簡單，大多函數在賦值操作中已經用到過，核心還是找到 key 的具體位置。尋找過程都是類似的，在 bucket 中挨個 cell 尋找。找到對應位置後，對 key 或者 value 進行「清零」操作，將 count 值減 1，將對應位置的 tophash 值置成 Empty

再來說觸發 map 擴容的時機：在向 map 插入新 key 的時候，會進行條件檢測，符合下面這 2 個條件，就會觸發擴容：

1、裝載因子超過閾值

源碼里定義的閾值是 6.5 (loadFactorNum/loadFactorDen)，是經過測試後取出的一個比較合理的因子

我們知道，每個 bucket 有 8 個空位，在沒有溢出，且所有的桶都裝滿了的情況下，裝載因子算出來的結果是 8。因此當裝載因子超過 6.5 時，表明很多 bucket 都快要裝滿了，查找效率和插入效率都變低了。在這個時候進行擴容是有必要的。

對於條件 1，元素太多，而 bucket 數量太少，很簡單：將 B 加 1，bucket 最大數量( 2^B )直接變成原來 bucket 數量的 2 倍。於是，就有新老 bucket 了。注意，這時候元素都在老 bucket 里，還沒遷移到新的 bucket 來。新 bucket 只是最大數量變為原來最大數量的 2 倍( 2^B * 2 ) 。

2、overflow 的 bucket 數量過多

在裝載因子比較小的情況下，這時候 map 的查找和插入效率也很低，而第 1 點識別不出來這種情況。表面現象就是計算裝載因子的分子比較小，即 map 里元素總數少，但是 bucket 數量多（真實分配的 bucket 數量多，包括大量的 overflow bucket）

不難想像造成這種情況的原因：不停地插入、刪除元素。先插入很多元素，導致創建了很多 bucket，但是裝載因子達不到第 1 點的臨界值，未觸發擴容來緩解這種情況。之後，刪除元素降低元素總數量，再插入很多元素，導致創建很多的 overflow bucket，但就是不會觸發第 1 點的規定，你能拿我怎麼辦？overflow bucket 數量太多，導致 key 會很分散，查找插入效率低得嚇人，因此出台第 2 點規定。這就像是一座空城，房子很多，但是住戶很少，都分散了，找起人來很困難

對於條件 2，其實元素沒那麼多，但是 overflow bucket 數特別多，說明很多 bucket 都沒裝滿。解決辦法就是開辟一個新 bucket 空間，將老 bucket 中的元素移動到新 bucket，使得同一個 bucket 中的 key 排列地更緊密。這樣，原來，在 overflow bucket 中的 key 可以移動到 bucket 中來。結果是節省空間，提高 bucket 利用率，map 的查找和插入效率自然就會提升。

由於 map 擴容需要將原有的 key/value 重新搬遷到新的內存地址，如果有大量的 key/value 需要搬遷，會非常影響性能。因此 Go map 的擴容採取了一種稱為「漸進式」的方式，原有的 key 並不會一次性搬遷完畢，每次最多隻會搬遷 2 個 bucket。

上面說的 hashGrow() 函數實際上並沒有真正地「搬遷」，它只是分配好了新的 buckets，並將老的 buckets 掛到了 oldbuckets 欄位上。真正搬遷 buckets 的動作在 growWork() 函數中，而調用 growWork() 函數的動作是在 mapassign 和 mapdelete 函數中。也就是插入或修改、刪除 key 的時候，都會嘗試進行搬遷 buckets 的工作。先檢查 oldbuckets 是否搬遷完畢，具體來說就是檢查 oldbuckets 是否為 nil。

如果未遷移完畢，賦值/刪除的時候，擴容完畢後（預分配內存），不會馬上就進行遷移。而是採取 增量擴容 的方式，當有訪問到具體 bukcet 時，才會逐漸的進行遷移（將 oldbucket 遷移到 bucket）

nevacuate 標識的是當前的進度，如果都搬遷完，應該和2^B的長度是一樣的

在evacuate 方法實現是把這個位置對應的bucket，以及其沖突鏈上的數據都轉移到新的buckets上。

轉移的判斷直接通過tophash 就可以，判斷tophash中第一個hash值即可

遍歷的過程，就是按順序遍歷 bucket，同時按順序遍歷 bucket 中的 key。

map遍歷是無序的，如果想實現有序遍歷，可以先對key進行排序

為什麼遍歷 map 是無序的？

如果發生過遷移，key 的位置發生了重大的變化，有些 key 飛上高枝，有些 key 則原地不動。這樣，遍歷 map 的結果就不可能按原來的順序了。

如果就一個寫死的 map，不會向 map 進行插入刪除的操作，按理說每次遍歷這樣的 map 都會返回一個固定順序的 key/value 序列吧。但是 Go 杜絕了這種做法，因為這樣會給新手程序員帶來誤解，以為這是一定會發生的事情，在某些情況下，可能會釀成大錯。

Go 做得更絕，當我們在遍歷 map 時，並不是固定地從 0 號 bucket 開始遍歷，每次都是從一個**隨機值序號的 bucket 開始遍歷，並且是從這個 bucket 的一個 隨機序號的 cell **開始遍歷。這樣，即使你是一個寫死的 map，僅僅只是遍歷它，也不太可能會返回一個固定序列的 key/value 對了。

⑧ Mapbox源碼分析（2）url解析

通過源碼，我們來一步步分析Mapbox地圖引擎如何進行指定字元串變數解析成url地址載入的，這里是基於5.3.0的版本．

在官方demo中，我們不僅可以載入本地樣式文件，已定義樣式文件和網路在線文件，它們的格式分別是

1. "asset://test.json"

2 . "https://www.mapbox.com/android-docs/files/mapbox-raster-v8.json"

3 . "mapbox://styles/mapbox/streets-v10"

這些格式，那麼Mapbox如果解析這些字元串去獲取到需要的樣式數據呢？我們從 Mapbox源碼分析（1）樣式載入 這篇的loadURL()方法開始看起

我們在這里看到，樣式的數據是通過fileSource.request進行請求載入的，通過調試我們發現這個fileSource是FileSource的子類DefaultFileSource，那麼我們先看看這個DefaultFileSource是什麼時候傳進來的

我們在這里看到，是在構造方法時對fileSource變數進行初始化的，那麼我們只需要看到Style::Impl對象什麼時候構造的，便知道了fileSource的來源，繼續往回找

在這里我們發現Impl對象的fileSource是Style對象構造時傳進來的，那麼我們繼續往回找

這里我們看到Style對象是通過map.cpp里的getStyle對象獲取的，而style對象是在Map::Impl::Impl構造方法時初始化的，繼續往回找

這里我們其實也能大概猜出來Map::Impl對象是在Map構造方法時初始化的，那麼map對象又是什麼時候初始化的，是不是覺得很繞，馬上就快到了，我們找到native_map_view.cpp文件，發現在NativeMapView構造方法中構造了map對象

到這里我們已經基本清楚fileSource的來源了，是java層NativeMapView對象初始化的時候傳下來的，我們繼續看到開頭，既然我們已經知道fileSource對象是DefaultFileSource，那麼它調用的request方法，也就是調用的DefaultFileSource的request方法，這里我們看到default_file_source.cpp文件

這里我們看到它轉到了它的實現類的request方法

這里我們可以看到根據url的不同，和載入方法的不同，將請求分別轉給了assetFileSource，localFileSource，onlineFileSource等的request方法，這里我們看onlineFileSource的request方法

看到這里我們看到根據請求的類型不同，去處理不同的url,在這些參數里我們看下apiBaseURL這個變數，這是一個base url,指定了伺服器地址，我們在constants.hpp文件中找到了它

constexpr const char* API_BASE_URL = "https://api.mapbox.com";

繼續往下看，我們選normalizeStyleURL()方法往下看

這里我們看到它先驗證了一下url,然後將url字元串包裝成URL對象，然後進行一個拼接成tpl變數，最後再通過transformURL函數進行一個轉換，這里我們先看它如何包裝這個URL對象的

這里我們看到它將字元串分解成query,scheme,domain,path四個變數進行存儲，我們再看看transformURL()函數

這里我們看到根據url的不同變數值進行了再次字元串拼接，甚至根據路徑的不同，繼續拆分成Path對象，最後將拼接結果返回，到這里有關url解析拼接的過程就講完了．

⑨ HashMap源碼分析

HashMap（jdk 1.8）
  使用哈希表存儲鍵值對，底層是一個存儲Node的table數組。其基本的運行邏輯是，table數組的每一個元素是一個槽，用於存儲Node對象，向Hash表中插入鍵值對時，首先計算鍵的hash值，並對數組容量（即數組長度）取余，定位該鍵值對應放在哪個槽中，若槽中已經存在元素（即哈希沖突），將Node節點插入到沖突鏈表尾端，當該槽中結點超過一定數量（默認為8）並且哈希表容量超過一定值（默認為64）時，對該鏈表進行樹化。低於一定數量（默認為6）後進行resize時，樹形結構又會鏈表化。當哈希表的總節點數超過閾值時，對哈希表進行擴容，容量翻倍。

由於哈希表需要用到key的哈希函數，因此對於自定義類作為key使用哈希表時，需要重寫哈希函數，保證相等的key哈希值相同。

由於擴容或樹化過程Node節點的位置會發生改變，因此哈希表是無序的，不同時期遍歷同一張哈希表，得到的節點順序會不同。

成員變數

    Hash表的成員變數主要有存儲鍵值對的table數組，size，裝載因子loadFactory，閾值theshold，容量capacity。

table數組：

哈希表的實質就是table數組，它用來存儲鍵值對。哈希表中內部定義了Node類來封裝鍵值對。

 Node類實現了Map的Entry介面。包括key，value，下一個Node指針和key的hash值。

 容量Capacity：

HashMap中沒有專門的屬性存儲容量，容量等於table.lenth，即數組的長度，默認初始化容量為16。初始化時，可以指定哈希表容量，但容量必須是2的整數次冪，在初始化過程中，會調用tableSizeFor函數，得到一個不小於指定容量的2的整數次冪，暫時存入到threshold中。

注意，若容量設置過大，那麼遍歷整個哈希表需要耗費更多的時間。

    閾值threshold：

指定當前hash表最多存儲多少個鍵值對，當size超過閾值時，hash表進行擴容，擴容後容量翻倍。

   loadFactory：

threshold=capacity*loadFactory。

裝填因子的大小決定了哈希表存儲鍵值對數量的能力，它直接影響哈希表的查找性能。初始化時可以指定loadFactory的值，默認為0.75。

 初始化過程

哈希表有3個構造函數，用戶可以指定哈希表的初始容量和裝填因子，但初始化過程只是簡單填入這兩個參數，table數組並沒有初始化。注意，這里的initialCapacity會向上取2的整數次冪並暫時保存到threshold中。

table數組的初始化是在第一次插入鍵值對時觸發，實際在resize函數中進行初始化。

hash過程與下標計算

哈希表是通過key的哈希值決定Node放入哪個槽中， 在java8中 ，hash表沒有直接用key的哈希值，而是自定義了hash函數。

哈希表中的key可以為null，若為null，哈希值為0，否則哈希值（一共32位）的高16位不變，低16位與高16位進行異或操作，得到新的哈希值。（h >>> 16，表示無符號右移16位，高位補0，任何數跟0異或都是其本身，因此key的hash值高16位不變。）

之所以這樣處理，是與table的下標計算有關

因為，table的長度都是2的冪，因此index僅與hash值的低n位有關（n-1為0000011111的形式），hash值的高位都被與操作置為0了，相當於hash值對n取余。

由於index僅與hash值的低n位有關，把哈希值的低16位與高16位進行異或處理，可以讓Node節點能更隨機均勻得放入哈希表中。

get函數：

V  get(Object key) 通過給定的key查找value

先計算key的哈希值，找到對應的槽，遍歷該槽中所有結點，如果結點中的key與查找的key相同或相等，則返回value值，否則返回null。

注意，如果返回值是null，並不一定是沒有這種KV映射，也有可能是該key映射的值value是null，即key-null的映射。也就是說，使用get方法並不能判斷這個key是否存在，只能通過containsKey方法來實現。

put函數

V put(K key, V value) 存放鍵值對

計算key的哈希值，找到哈希表中對應的槽，遍歷該鏈表，如果發現已經存在包含該key的Node，則把新的value放入該結點中，返回該結點的舊value值（舊value可能是null），如果沒有找到，則創建新結點插入到 鏈表尾端 （java7使用的是頭插法），返回null。插入結點後需要判斷該鏈表是否需要樹化，並且判斷整個哈希表是否需要擴容。

由該演算法可以看出，哈希表中不會有兩個key相同的鍵值對。

resize函數

    resize函數用來初始化或擴容table數組。主要做了兩件事。

1.根據table數組是否為空判斷初始化還是擴容，計算出相應的newCap和newThr，新建table數組並設置新的threshold。

2.若是進行擴容，則需要將原數組中的Node移植到新的數組中。

由於數組擴容，原來鍵值對可能存儲在新數組不同的槽中。但由於鍵值對位置是對數組容量取余（index=hash(key)&(Capacity-1)）,由於Capacity固定為2的整數次冪，並新的Capacity（newCap）是舊的兩倍（oldCap）。因此，只需要判斷每個Node中的hash值在oldCap二進制那一位上是否為0(hash&oldCap==0)，若為0，對newCap取余值與oldCap相同，Node在新數組中槽的位置不變，若為1，新的位置是就得位置加一個oldCap值。

因此hashMap的移植演算法是，遍歷舊的槽：

若槽為空，跳過。

若槽只有一個Node，計算該Node在新數組中的位置，放入新槽中。

若槽是一個鏈表，則遍歷這個鏈表，分別用loHead，loTail,hiHead,hiTail兩組指針建立兩個鏈表，把hash值oldCap位為0的Node節點放入lo鏈表中，hash值oldCap位為1的節點放入hi鏈表中，之後將兩個鏈表分別插入到新數組中，實現原鍵值對的移植。

lo鏈表放入新數組原來位置，hi鏈表放入新數組原來位置+oldCap中

樹化過程 ：

當一個槽中結點過多時，哈希表會將鏈表轉換為紅黑樹，此處挖個坑。

[總結] java8中hashMap的實現原理與7之間的區別：

1.hash值的計算方法不同 2.鏈表採用尾插法，之前是頭插法 3.加入了紅黑樹結構

⑩ 關於C++ STL裡面的map 今天見的代碼（見問題補充）為什麼開始就能判斷b[str1]==0;是int的初始都是0嗎

你可以看看map的源碼，其中[]的實現是這樣的：

mapped_type&operator[](key_type&&_Keyval)
{
iterator_Where=this->lower_bound(_Keyval);

if(_Where==this->end()
||this->comp(_Keyval,this->_Key(_Where._Mynode())))
_Where=this->insert(_Where,
_STDpair<key_type,mapped_type>(
_STDmove(_Keyval),
mapped_type()));
return((*_Where).second);
}

首先，會在map查找這個鍵值的項，map如果不包含某個鍵值，會返回map的end，然後它發現此鍵值沒有找到(_Where == this->end())的話，會自動在末尾插入（this->insert(_Where）一個以你輸入的鍵值和value的默認值（mapped_type()）構成的對兒（pair），然後返回這個插入項的值（second，鍵是first）。而int的默認構造函數int()，就是0。

也就是時候，哪怕你沒有對map進行插入操作，哪怕只是用[]判斷了下返回值是否是0，map對象也會自動添加一項。

不過一般判斷map是否包含一個鍵，是用map的find方法，判斷find的返回結果是否是map的end。