内置数据类型的实现

内置的扩充类型皆为结构体

string 字符串

struct string {
  byte* str;
  intgo len;
}

通常string常量是编译器分配到只读段的(.rodata)，对应的数据地址不可写入。fmt.Sprintf生成的字符串分配在堆上，对应数据地址可修改

底层结构（字符串赋值时拷贝的结构）

type StringHeader struct {
	Data uintptr
	Len  int
}

string 与 byte 相互转换

//return GoString's buffer slice(enable modify string)
func StringBytes(s string) Bytes {
    return *(*Bytes)(unsafe.Pointer(&s))
}

// convert b to string without copy
func BytesString(b []byte) String {
    return *(*String)(unsafe.Pointer(&b))
}

func unsafeEqual(a string, b []byte) bool {
    bbp := *(*string)(unsafe.Pointer(&b))
    return a == bbp
}

rune 转成 string 因为内存结构的不同，因此必定会发生内存重分配

var p []byte
buf := make([]byte, 3)
for _, r := range s {
	n := utf8.EncodeRune(buf, r)
	p = append(p, buf[:n]...)
}
return string(p)

本质上，字符串的赋值只是复制了数据地址和对应的长度，不会导致底层字节数组的赋值字符串也支持切片操作

普通数组

有多种初始化方式

var a [3]int // 初始化为零值，3个元素
var b = [...]int{1, 2, 3} // 字面量初始化
var c = [...]int{2: 3, 1: 2} // 下标：值初始化，其余没指定的就是0

slice

type slice struct {
	array unsafe.Pointer
	len   int
	cap   int
}

使用 for-range 的方式进行迭代性能会好一些，因为不会进行越界判断

只根据len次数去迭代，无额外内存代价

for range times {
	// do something
}

使用 append 支持链式操作，不过在添加的时候生成中间临时切片，可以使用下面的方式进行插入元素

a = append(a, 0)
copy(a[i+1:], a[i:]) // 往后挪元素
a[i] = x // 再插入

a = a[:copy(a, a[N:])] // 删除开头N个元素

判断一个切片是否为空的时候，一般通过 len 获取切片的长度来判断，一般通过 len 获取切片的长度来判断，一般很少将切片和 nil 做直接的比较

利用长度为0的切片进行原地修改

// 传入的 s 的底层数组会被 b 修改
func TrimSpace(s []byte) []byte {
	b := s[:0]
	for _, x := range s {
		if x != ' ' {
			b = append(b, x)
		}
	}
	return b
}

高效操作的要点是降低内存分配的次数，尽量保证 append 操作不会超过 cap 的容量

如果我们只是使用很大一段 slice 数组的一小部分，那么其余的部分依然不会被垃圾回收，因此更好的做法是通过 copy 返回一个真正容量上更小的 slice，使得原大 slice 可以被回收

切片强制类型转换时可以通过直接修改切片的头信息来实现转换

// 对浮点切片进行高速排序
func SortFloat64FastV2(a []float64) {
	var c []int
	aHdr := (*reflect.SliceHeader)(unsafe.Pointer(&a))
	cHdr := (*reflect.SliceHeader)(unsafe.Pointer(&c))
	*cHdr = *aHdr
	sort.Ints(c)
}

map

// A header for a Go map.
type hmap struct {
	count int // len()返回的map的大小 即有多少kv对
	flags uint8
	B     uint8  // 表示hash table总共有2^B个buckets 
	hash0 uint32 // hash seed

	buckets    unsafe.Pointer // 按照low hash值可查找的连续分配的数组，初始时为16个Buckets.
	oldbuckets unsafe.Pointer 
	nevacuate  uintptr      

	overflow *[2]*[]*bmap //溢出链 当初始buckets都满了之后会使用overflow
}

buckets 是存放桶的一维数组 overflow 是桶满了之后挂载在桶中的链表

每个桶最多存 8 个KV对，还有指向下一个桶的指针，为了节约内存空间，存储顺序分别为 kkkkkkkkvvvvvvvv，不成对存储防止内存对齐导致空间浪费

增量扩容：同 redis 的实现方式类似，扩容的时候为了降低使用时的延迟，map 中会同时维护当前的桶和旧的桶，新的 kv 使用新的 hash 存到新的桶中，同时在每一次插入或者删除的时候迁移 1 到2个键值对，迁移过的 KV 会进行标记，直到所有的旧表中的数据都迁移到新表中时，解除旧引用并释放内存

插入：hash之后的值，通过低8位来寻找键对应的桶，找到空的位置来存放哈希值的高八位查找：同样对应插入的流程，如果还未迁移到新的 map 就会回到旧的去读，会与桶里的 8 个key高8位进行循环比对，如果桶里没有，那么就去 overflow 溢出链中找

删除：不会收缩不再使用的空间，以备未来使用

map 的所谓泛型其实是在编译时确定好 maptype 和 _type 的值，编译好的程序只含有用户定义的 map 类型的实现

也同样有其他语言所有的 hash 方法和 equal 方法

type typeAlg struct {   // function for hashing objects of this type   // (ptr to object, seed) -> hash
   hash func(unsafe.Pointer, uintptr) uintptr   // function for comparing objects of this type   // (ptr to object A, ptr to object B) -> ==?
      equal func(unsafe.Pointer, unsafe.Pointer) bool 
}

每一个 go 的类型都有对应一个 typeAlg

interface 接口

type _interface struct {
	dynamicTypeInfo *_implementation
	dynamicValue    unsafe.Pointer // 通用指针类型
}

type _implementation struct {
	itype   *_type   // 接口类型
	dtype   *_type   // 运行时类型，必须实现 itype
	methods []*_func // 实现了对应 itype 的方法的函数指针
}

为了避免其他的类型无意中适配了接口，在设计接口的时候可以定义一些特有的名字的函数来避免此问题

纯虚继承：通过嵌入匿名指针对象或者匿名接口，然后再运行时动态注入来实现

byte

byte是uint8的别名

rune

rune是int32的别名

int

比较运算

大部分的类型是可以进行比较运算的，除了 func, map, slice 。如果是接口类型，那么具体类型需要支持 == 和 != 操作

内存分配运行时