---- Cache的容量很小，它保存的内容只是主存内容的一个子集，且Cache与主存的数据交换是以块（cache line）为单位的。为了把信息放到Cache中，必须应用某种函数把主存地址定位到Cache中，这称为地址映射。
---- 在信息按这种映射关系装入Cache后，CPU执行程序时，会将程序中的主存地址变换成Cache地址，这个变换过程叫做地址变换。
Cache的地址映射方式有直接映射、全相联映射和组相联映射。
假设某台计算机主存容量为1MB，被分为2048块，每个Block为512B；Cache容量为8KB，被分为16块，每块也是512B。
下面以此为例介绍三种基本的地址映射方法。
1. 直接映射
---- 一个内存地址能被映射到的Cache line是固定的。就如每个人的停车位是固定分配好的，可以直接找到。缺点是：因为人多车位少，很可能几个人争用同一个车位，导致Cache淘汰换出频繁，需要频繁的从主存读取数据到Cache，这个代价也较高。
直接映射的Cache组织如图（1）所示。主存中的一个块只能映射到Cache的某一特定块中去。例如，
主存的第0块、第16块、第32块、第48块、……、第2032块等128块，只能映射到Cache的第0块；
主存的第1块、第17块、第33块、第49块、……、第2033块等128块，只能映射到Cache的第1块；
以此类推，主存的第15块、第31块、第47块、……、第2047块等128块，只能映射到Cache的第15块中。
映射完毕，Cache总共有0～15即16块，主存中的每128（2048/16）块，只能映射到Cache中的某一个块中。
即映射规则为cache line index = （主存（Page）的line数）%（cache中 cache line的总数）
主存的line数是0～2047，cache中cache line的总数是16.
  
                                          图（1）
直接映射是最简单的地址映射方式，它的硬件简单，成本低，地址变换速度快，而且不涉及替换算法问题。但是这种方式不够灵活，Cache的存储空间得不到充分利用，每个主存块只有一个固定位置可存放，容易产生冲突，使Cache效率下降，因此只适合大容量Cache采用。例如，如果一个程序需要重复引用主存中第0块与第16块，最好将主存第0块与第16块同时复制到Cache中，但由于它们都只能复制到Cache的第0块中去，即使Cache中别的存储空间空着也不能占用，因此这两个块会不断地交替装入Cache中，导致命中率降低。
2. 全相联映射
---- 主存中的一个地址可被映射进任意cache line，问题是：当寻找一个地址是否已经被cache时，需要遍历每一个cache line来寻找，这个代价很高。就像停车位可以大家随便停一样，停的时候简单，找车的时候需要一个一个停车位的找了。
图（2）是全相联映射的Cache组织，主存中任何一块都可以映射到Cache中的任何一块位置上。
  
                                         图（2）
全相联映射方式比较灵活，主存的各块可以映射到Cache的任一块中，Cache的利用率高，块冲突概率低，只要淘汰Cache中的某一块，即可调入主存的任一块。但是，由于Cache比较电路的设计和实现比较困难，这种方式只适合于小容量Cache采用。
3. 组相联映射
---- 组相联映射实际上是直接映射和全相联映射的折中方案，其组织结构如图（3）所示。
主存和Cache都分组，主存中一个组内的块数与Cache中的分组数相同，组间采用直接映射，组内采用全相联映射。也就是说，将Cache分成2^u组，每组包含2^v块，主存块存放到哪个组是固定的，至于存到该组哪一块则是灵活的。即主存的某块只能映射到Cache的特定组中的任意一块。主存的某块b与Cache的组k之间满足以下关系：k=b%(2^u).
例如，Cache分为8组(u=3)，每组2块(v=1)，主存分为128个区，每个区16块。
 
                                                  图（3）
主存中的各块与Cache的组号之间有固定的映射关系，但可自由映射到对应Cache组中的任何一块。例如：
--主存的第0块、第2^u块、第2×(2^u)块、…第255x(2^u)即255x8=2040块等256块均映射于Cache的第0组，但可映射到其中的第0块或第1块；
--主存的第1块、第2^u+1块、第3^(2^u)+1块、…第255x(2^u+1)即2041块等均映射于Cache的第2组，但可映射到Cache第2组中的任意一块；
--主存的第2块、第2^u+2块、第（2^u）x2+2块、…第2042块等均映射于Cache的第3组，但可映射到Cache第3组中的任意一块；
--主存的第7块、第2^u+7块、第2^(u+1)+7块、…第2047块等均映射于Cache的第8组，但可映射到Cache第8组中的第14块或第15块。
常采用的组相联结构Cache，每组内有2、4、8、16块，称为2路、4路、8路、16路组相联Cache。以上为2路组相联Cache。组相联结构Cache是前两种方法的折中方案，适度兼顾二者的优点，尽量避免二者的缺点，因而得到普遍采用。
实例分析：
1.容量为64块的Cache采用组相联方式映像，字块大小为128字节，每4块为一组，若主容量为4096块，且以字编址，那么主存地址为（19）位，主存区号为（6）位。
解：组相联的地址构成为：区号+组号+块号+块内地址。
主存的每个分区/组大小与整个Cache大小相等，故此主存需要分的区数为：4096/64=64，因为26＝64，因此需要6位来表示区号。每4块为一组，故共有组数 64/4 = 16 ，因为24＝16，因此需要4位表示组号。每组4块，故表示块号需要2位。
块内地址共128字节，27＝128，所以块内地需要7位表示。所以：主存地址的位数＝6+4+2+7 ＝ 19
主存区号的位数＝6
个人见解：Cache有u组，每组有v块，即u = 16，v = 4，Cache大小：64块×128B = 8KB。
主存大小：4096×128B = 2^12*2^7 = 2^19,即主存地址有19位。4096/64= 2^6主存区号为6位。
2.某 32 位计算机的 cache 容量为 16KB，cache 块的大小为 16B，若主存与 cache 的地址映射采用直接映射方式，则主存地址为 1234E8F8（十六进制）的单元装入的 cache 地址为__C__。
A. 00 0100 0100 1101 (二进制)
B. 01 0010 0011 0100 (二进制)
C. 10 1000 1111 1000 (二进制)
D. 11 0100 1110 1000 (二进制)
解：Cache大小为16KB，块大小为16B，所以Cache被分成16KB/16B=1024块，因210＝1024故需要10位来表示块数。
24＝16故块内地址需要4位来表示。所以Cache的地址线位置为14位。
由于采用直接映像的方式，所以主存的后14位就是要装入的到Cache中的位置。故选 C.
个人见解：Cache的容量是16KB = 16×1024B = 16384B，主存的地址为0x1234E8F8/（16×1024B）= 18643. 该地址对应的是主存的第18643块。
根据公式：cache的块地址i = 主存的块地址 % 16384 = 1234E8F8 - 1234C000 = 0x28F8 选C
 
 

映射的内部实现和基础功能

映射是一种数据结构，用于存储一系列无序的键值对，实现基于键的快速检索数据

文章目录
映射的内部实现和基础功能
1.内部实现
2. 创建和初始化
a. make函数声明映射
b. 字面量声明映射
3. 使用映射
a. 映射赋值
b. nil映射
c. 判断键值是否相互匹配
d. 迭代映射
4. 函数间传递映射
参考：

1.内部实现
映射是一个存储键值对的无序集合

a. 可以使用类是处理数组和切片的方式迭代映射中的元素

b. 映射是无序的，每次迭代映射的顺序都有可能不一致

注:无序的原因是映射的实现使用了散列表

散列表

映射的散列表包含一组桶：

a. 在存储删除或者查找键值对的时候，所有的操作都要选择一个桶。

操作时将指定的键传递给映射的散列函数，就能选中对应的桶

散列函数的作用是生成一个索引，并将键值对分布到所有的可用的桶里

随着映射存储的增加，索引分布越均匀，访问键值对的速度就越快


2. 创建和初始化
a. make函数声明映射
// 创建一个键为string值为int的映射
rain_dict := make(map[string]int)

// 输出结果：
// == rain_dict:  map[]

b. 字面量声明映射
映射的初始长度很根据初始化时的键值对的数量来确定

1) 映射的键可以使任意值

  切片、函数以及包含切片的结构类型，由于具有“引用语义”，不能作为键

2) 值的类型可以是内置的类型，也可以是可以用 == 运算符作比较的 结构类型

// 创建一个映射，并初始化数值
rain_dict_1 :=map[string]string{"china": "BeiJing", "america":"NewYork"}

// 输出结果：
// == rain_dict_1:  map[america:NewYork china:BeiJing]

3. 使用映射
a. 映射赋值
// 创建一个空映射
rain_dict_2 := map[string]int{}
// 映射赋值
rain_dict_2["top"] = 5
rain_dict_2["right"] = 6

// 输出结果：
// == rain_dict_2:  map[right:6 top:5]

b. nil映射

nil 映射不能存储键值对，否则会发生一个语法错误

// 声明式创建nil映射
var rain_dict_3 map[string]int

// nil 映射赋值
rain_dict_3["msit"] = 2

// 输出结果：
// panic: assignment to entry in nil map


c. 判断键值是否相互匹配

i. 同时获取值与这个值是否存在的标志

// 创建一个映射
rain_dict_4 := map[string]int{"Chinese": 98, "English": 86}

// 同时获取值和是否存在的标志
// value 零值(不存在)，key bool
value, key := rain_dict_4["math"]
if key{
    fmt.Printf("Both Value: %d", value)
}


d. 迭代映射
使用关键字range迭代映射
// 创建一个映射
rain_ditc_5 := map[string]int{"hight": 120, "width": 45, "kg": 48}
// 迭代打印键值对
for key, value := range rain_dict_5{
    fmt.Printf("Key: %s, Value: %d, Key_addr: %X, Value_addr: %X", key, value, &key, &value)
}

// 输出结果：
// Key: hight, Value: 120, Key_addr: C0000521C0, Value_addr: C000066080
// Key: width, Value: 45, Key_addr: C0000521C0, Value_addr: C000066080
// Key: kg, Value: 48, Key_addr: C0000521C0, Value_addr: C000066080

删除一项元素
// 创建一个映射
rain_dict_6 := map[int]int{1:1, 2:2, 3:3}
// 删除key=2的元素
delete(rain_dict_5, 2)

// 输出结果：
// == Rain_dict_6:  map[1:1 3:3]

4. 函数间传递映射
在函数间传递映射，并不会 复制映射作为副本

当对这个映射修改时，所有对这个映射的映射都会察觉到这个修改
package main

import "fmt"

func main() {
	rain_dict_7 := map[string]int{"Chinese": 98, "English": 86, "Math": 90}

	Rain_map_1(rain_dict_7)
    Rain_map_2(rain_dict_7)
    Rain_map_delete(rain_dict_7, "English")
	fmt.Println("== rain_dict_7: ", rain_dict_7)
}

func Rain_map_1(rain map[string]int) {
	rain["Physical"] = 71
	fmt.Println("== Rain_map_1: ", rain)
}

func Rain_map_2(rain map[string]int) {
	rain["Naturl"] = 82
	fmt.Println("== Rain_map_2: ", rain)
}

func Rain_map_delete(rain  map[string]int, key string){
    fmt.Println("== Pre_delete_map: ", rain)
    delete(rain, key)
}

// 输出结果：
// == Rain_map_1:  map[Chinese:98 English:86 Math:90 Physical:71]
// == Rain_map_2:  map[Chinese:98 English:86 Math:90 Naturl:82 Physical:71]
// == Pre_delete_map:  map[Chinese:98 English:86 Math:90 Naturl:82 Physical:71]
// == rain_dict_7:  map[Chinese:98 Math:90 Naturl:82 Physical:71]

参考：
Go语言程序设计

1. 通俗来说，同构是指具有相同的代数结构。代数结构由一个或多个集合、若干运算及一些运算规则所唯一确定。代数结构相同的含义是指：除了表示集合元素的符号有可能不同外，对应集合的元素个数相同，集合上的运算一致，运算规则也完全一样。

2. 两个代数结构相同是指它们之间至少存在一个同构映射。同构映射要满足两个条件：它是集合之间的双射或一一对应；它保持代数结构的所有运算及一些特殊元素，比如，单位元、零元素等等，尽管有些要求可以由其它主要条件推出。

3. 举个例子，两个群之间的同构映射为集合之间的双射，且该映射保持群的乘法运算。即，先乘积后映射与先映射后乘积的结果一致。

4. 研究代数结构的主要目的是对其进行分类，或者说找出所有的这种代数结构。同构的代数结构可以不加区分，把它们可以看成一样的。因此，代数结构的分类就是找出该代数结构的所有同构类。

5. 如果两个代数结构不同构，为了研究它们之间的关系，可考虑它们之间保持运算的映射，这就是同态的概念。同态比同构更一般、广泛；同构只是同态的特例。

6. 同态不是同构的原因主要体现在：相应的映射不是双射，即，不是单射或不是满射。当然也可能既不是单射也不是满射。当映射不是满射时，我们只需考虑映射的像集，这个像集是原来代数结构的子结构。比如，对群的情形，同态的像集是一个子群。用子结构替换原来的代数结构，原来的映射变成了满射！

7. 当映射不是单射时，不同的元素被映到相同的元素。这时，可以把映到同一个元素的元素看成是一样的，或者说它们是等价的。这样我们将得到一个等价关系，做商集。在这个商集上诱导的映射就是一个单射了。这就是同态基本定理的主要想法。

8. 在这个商集上可以定义类似的代数结构，使得前面提到的映射是同态。从这个商代数到上述提到的子代数诱导的映射就是一个同构映射了。

##映射器的自动映射和驼峰映射

mybatis提供了自动映射功能，在默认情况下是开启的。在setting中有两个可以配置的选项 autoMappingBehavior和mapUnderscoreToCamelCase。它们分别控制自动映射和驼峰式映射。

配置自动映射的取值范围是:
NONE 不自动进行映射
PARTIAL 默认值，只对没有嵌套的结果集进行自动映射
FULL 对于所有的结果集进行映射，包括嵌套结果集。
<select id="getRole" parameterType="role" resultType="role">
  		SELECT 
  			id,roleName , note 
  		FROM 
  			role 
  		WHERE 
  			id = #{id}
  	</select>

当我们数据库中字段名为roleName且对应的pojo中的属性名称也为roleName时，可以完成自动映射。但是当数据库字段名为role_name样式时，可以通过开启驼峰映射方式，完成任务。

配置mapUnderscoreToCamelCase:
<settings>
		<setting name="mapUnderscoreToCamelCase" value="true"/>
	</settings> 

映射文件中的sql语句:
<select id="getRole" parameterType="role" resultType="role">
  		SELECT 
  			id,role_name , note 
  		FROM 
  			role 
  		WHERE 
  			id = #{id}
  	</select>

此时pojo中对应role_name字段的属性名仍为roleName。

但是mybatis会严格按照驼峰式映射规则完成映射，这样pojo和数据字段严格对应，降低了灵活性。在实际开发中有些映射更加复杂，所以一般采用resultMap方式，建立结果集映射。