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。