July 26, 2022
July 26, 2022
当我们向 map 插入一条数据，或者是从 map 按 key 查询数据的时候，运行时都会使用哈希函数对 key 做哈希运算，并获得一个哈希值（hashcode）。这个 hashcode 非常关键，运行时会把 hashcode“一分为二”来看待，其中低位区的值用于选定 bucket，高位区的值用于在某个 bucket 中确定 key 的位置。我把这一过程整理成了下面这张示意图，你理解起来可以更直观：
因此，每个 bucket 的 tophash 区域其实是用来快速定位 key 位置的，这样就避免了逐个 key 进行比较这种代价较大的操作。尤其是当 key 是 size 较大的字符串类型时，好处就更突出了。这是一种以空间换时间的思路。
July 26, 2022
Go 运行时使用一张哈希表来实现抽象的 map 类型。运行时实现了 map 类型操作的所有功能，包括查找、插入、删除等。在编译阶段，Go 编译器会将 Go 语法层面的 map 操作，重写成运行时对应的函数调用。大致的对应关系是这样的：
// 创建map类型变量实例
m := make(map[keyType]valType, capacityhint)
→ m := runtime.makemap(maptype, capacityhint, m)
// 插入新键值对或给键重新赋值
m["key"] = "value"
→ v := runtime.mapassign(maptype, m, "key") v是用于后续存储value的空间的地址
// 获取某键的值
v := m["key"] → v := runtime.mapaccess1(maptype, m, "key")
v, ok := m["key"] → v, ok := runtime.mapaccess2(maptype, m, "key")
// 删除某键
delete(m, "key") → runtime.mapdelete(maptype, m, “key”)
这是 map 类型在 Go 运行时层实现的示意图：
July 26, 2022
July 26, 2022
这里我们再看看怎么通过稍微复杂一些的复合字面值，对 map 类型变量进行初始化：
m1 := map[int][]string{
1: []string{"val1_1", "val1_2"},
3: []string{"val3_1", "val3_2", "val3_3"},
7: []string{"val7_1"},
}
type Position struct {
x float64
y float64
}
m2 := map[Position]string{
Position{29.935523, 52.568915}: "school",
Position{25.352594, 113.304361}: "shopping-mall",
Position{73.224455, 111.804306}: "hospital",
}
上面代码虽然完成了对两个 map 类型变量 m1 和 m2 的显式初始化，但作为初值的字面值似乎有些“臃肿”。针对这种情况，Go 提供了“语法糖”。这种情况下，Go 允许省略字面值中的元素类型。因为 map 类型表示中包含了 key 和 value 的元素类型，Go 编译器已经有足够的信息，来推导出字面值中各个值的类型了。我们以 m2 为例，这里的显式初始化代码和上面变量 m2 的初始化代码是等价的：
m2 := map[Position]string{
{29.935523, 52.568915}: "school",
{25.352594, 113.304361}: "shopping-mall",
{73.224455, 111.804306}: "hospital",
}
以后在无特殊说明的情况下，我们都将使用这种简化后的字面值初始化方式。
July 26, 2022
和切片类型变量一样，如果我们没有显式地赋予 map 变量初值，map 类型变量的默认值为 nil。
不过切片变量和 map 变量在这里也有些不同。初值为零值 nil 的切片类型变量，可以借助内置的 append 的函数进行操作，这种在 Go 语言中被称为“零值可用”。定义“零值可用”的类型，可以提升我们开发者的使用体验，我们不用再担心变量的初始状态是否有效。
但 map 类型，因为它内部实现的复杂性，无法“零值可用”。所以，如果我们对处于零值状态的 map 变量直接进行操作，就会导致运行时异常（panic），从而导致程序进程异常退出：
var m map[string]int // m = nil
m["key"] = 1 //panic: assignment to entry in nil map
所以，我们必须对 map 类型变量进行显式初始化后才能使用。
July 26, 2022
July 25, 2022
每次回收中能存活下来的对象占总体的比例都比较小。那么，我们就可以结合这个特点，把 To 空间设置得小一点，来提升空间的利用率。
Hotspot 在实现 copy 算法时做了一些改进。它将 From 空间称为 Eden 空间，
To 空间在算法实现中则被分成 S0 和 S1 两部分，这样 To 空间的浪费就可以减少了。Java 堆的空间关系如下图所示：
在这张图里，Hotspot 的内存管理器在 Eden 空间中分配新的对象，每次 GC 时，如果将 S0 做为 To 空间，则 S1 与 Eden 合起来成为 From 空间。也就是说
To 空间这个空闲区域就大大减小了，这样可以提升空间的总体利用率。
Scavenge 算法是简单 copy 算法的一种改进。在这种算法中，人们习惯于把 S0 和 S1 称为幸存者空间（Survivor Space）。配置 Survivor 空间的大小是 JVM GC 中的重要参数，例如：-XX:SurvivorRatio=8，代表 Eden:S0:S1=8:1:1。
July 25, 2022
July 25, 2022
假设，在 From 空间中对象的内存布局如下所示：
请你注意，图中的空白部分是我为了让图更容易查看而故意加的，真实的情况是每个对象之间的空白是不存在的，它们是紧紧地挨在一起的。
完成了一次 Copy GC 以后堆空间的情况如下所示：
从上面的图片中可以观察到一个特点：To 空间中的对象排列顺序和 From 空间中的对象排列顺序发生了变化。具有引用关系的对象在新空间中距离更近了。
因为 CPU 有缓存机制，所以在读取某个对象的时候，有很大概率会把它后面的对象也一起读进来。通常情况下，我们在写 Java 代码时，经常访问一个变量后，马上就会访问它的属性。如果在读 A 对象的时候，把它后面的 B 和 C 对象都能加载进缓存，那么，a.b1.c1 这种写法就可以立即命中缓存。这是深度优先搜索的 copy 算法的最大的优点。
同时，从代码里也能分析出它的缺点，那就是采用递归的写法，效率比较差。深度优先遍历也有非递归实现，它需要额外的辅助数据结构，也就是说需要手工维护一个栈结构。非递归的写法，可以使用以下伪代码表示：
void copy_gc() {
for (obj in roots) {
stack.push(obj);
}
while (!stack.empty()) {
obj = stack.pop();
*obj = copy(obj);
for (child in obj) {
stack.push(child);
}
}
}
与深度优先搜索相对应的是广度优先搜索。它的优缺点刚好与深度优先搜索相反。如果使用广度优先算法将对象从 From 空间拷贝到 To 空间，那么有引用关系的对象之间的距离就会比较远，这将不利于业务线程运行期的缓存命中。它的优点则在于可以节省 GC 算法执行过程中的空间，提升拷贝过程的效率。
...