Golang_包解析

Go map

底层实现

Go语言的map的底层实现基于Hash散列，Hash散列是一种著名的广义上的算法，它能将任意长度的数据映射到有限的值域当中。在实际工程中输入数据范围是无限的，而输出值域范围是有限的，因此必然存在不同的输入数据经过映射后得到相同的输出值，这种现象称为hash冲突，go底层通过链表解决hash冲突。值得注意的是：==Java1.8中使用平衡树来优化局部链表过长的性能问题。==

使用哈希表的目的就是要快速查找到目标key，然而，随着向map中添加的key越来越多，key发生碰撞的概率也越来越大，bucket中的8个cell会被逐渐塞满，插入、查找和删除key的效率也会越来越低，最理想的情况是bucket只装入一个key，这样，就能达到$O(1)$的效率，但这样空间消耗太大，代价太高。

底层源码如下所示：

// A header for a Go map.
type hmap struct {
	count     int // # live cells == size of map.  Must be first (used by len() builtin)
	flags     uint8
	B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
	noverflow uint16 
	hash0     uint32 // hash seed

	buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
	oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
	nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)

	extra *mapextra // optional fields
}

其中，buckets unsafe.Pointer指向具体的buckets数组，这个数组是bmap结构，如下所示：

// A bucket for a Go map.
type bmap struct {
	tophash [bucketCnt]uint8
}

在实际编译期间，Go语言的bmap会经过反射生成真正的bmap类型：

type bmap struct {
  topbits  [8]uint8
  keys     [8]keytype
  values   [8]valuetype
  pad      uintptr
  overflow uintptr
}

map的访问即通过给定的key在map中寻找其对应value，过程如下：

原始的key通过hash函数映射成64位二进制；
末尾x位代表bmap的位置，从[]bmap中找到对应的bmap，值得注意的是，bmap的数量一般是2的幂，如果末尾x位代表bmap的位置就代表有$2^x$个bmap；
首8位对应key的tophash，在bmap中进行检索，首先会比较bmap顶层的tophash与原始key的tophash是否相同，若不相同则直接跳过比较下一个；若相同则进一步比较key是否相同。

`container`

众所周知，Go对于一些基本的数据结构封装得不是很好，在container中也只有三种常见的数据结构——链表、环形链表和堆。

`container/list`

我们先来看看list的写入与打印：

l := list.New()
l.PushBack(1) //尾插
l.PushBack(2)
fmt.Println(l)

我们看看打印结果：

1	`&{{0xc00007c180 0xc00007c1b0 <nil> <nil>} 2}`

为什么打印结果是这样的，如果我们弄懂list的底层结构，就能知道答案了。list的底层结构如下：

type Element struct {
	// Next and previous pointers in the doubly-linked list of elements.
	// To simplify the implementation, internally a list l is implemented
	// as a ring, such that &l.root is both the next element of the last
	// list element (l.Back()) and the previous element of the first list
	// element (l.Front()).
	next, prev *Element

	// The list to which this element belongs.
	list *List

	// The value stored with this element.
	Value interface{}
}

// List represents a doubly linked list.
// The zero value for List is an empty list ready to use.
type List struct {
	root Element // sentinel list element, only &root, root.prev, and root.next are used
	len  int     // current list length excluding (this) sentinel element
}

结合上面的打印，我们可以发现，{0xc00007c180 0xc00007c1b0 <nil> <nil>} 是root Element，2是len int。我们接着打印：

l := list.New()//初始化
l.PushBack(1) //尾插
l.PushBack(2)
fmt.Println(l.Front())
fmt.Println(l.Back())
fmt.Println(l)

其打印结果如下：

1
2
3

&{0xc00007c1b0 0xc00007c150 0xc00007c150 1}
&{0xc00007c150 0xc00007c180 0xc00007c150 2}
&{{0xc00007c180 0xc00007c1b0 <nil> <nil>} 2}

从这个结果我们不难看出，list其实是一个环形结构。其中，root的next指向链表的front，root的pre指向链表的back，而root自身是不存储数据的。如果我们再加上一个数据，就会变成这样了：

l := list.New()//初始化
l.PushBack(1) //尾插
l.PushBack(2)
l.PushBack(3)
fmt.Println(l.Front())
fmt.Println(l.Back())
fmt.Println(l)

其打印结果如下：

1
2
3

&{0xc00007c1b0 0xc00007c150 0xc00007c150 1}
&{0xc00007c150 0xc00007c1b0 0xc00007c150 3}
&{{0xc00007c180 0xc00007c1e0 <nil> <nil>} 3}

`container/heap`

我们来看看如何初始化一个heap，如下所示：

type Student struct {
	name  string
	score int
}
h := &StudentHeap{
	{name: "xiaoming", score: 82},
	{name: "xiaozhang", score: 88},
	{name: "laowang", score: 85}
}
heap.Init(h)

先来读读Init()函数，如下所示：

func Init(h Interface) {
	// heapify
	n := h.Len()
	for i := n/2 - 1; i >= 0; i-- {
		down(h, i, n)
	}
}
func down(h Interface, i0, n int) bool {
	i := i0
	for {
		j1 := 2*i + 1
		if j1 >= n || j1 < 0 { // j1 < 0 after int overflow
			break
		}
		j := j1 // left child
		if j2 := j1 + 1; j2 < n && h.Less(j2, j1) {
			j = j2 // = 2*i + 2  // right child
		}
		if !h.Less(j, i) {
			break
		}
		h.Swap(i, j)
		i = j
	}
	return i > i0
}

可以看到，这两个函数跟我们的堆排序很像，还是讲一下，

`container/ring`

环的结构有点特殊，环的尾部就是头部，所以每个元素实际上就可以代表自身的这个环。它不需要像 list 一样保持 list 和 element 两个结构，只需要保持一个结构就行。

——[1. 3.3 container — 容器数据类型：heap、list 和 ring][https://books.studygolang.com/The-Golang-Standard-Library-by-Example/chapter03/03.3.html]

我觉得这句话总结得很好，

`reflect`

`reflect.DeepEqual`

DeepEqual函数用来判断两个值是否深度一致。这和==有什么不同吗？我们来看看下面例子：

type S struct{
	name string
    age	 int
}
func main(){
     a := S{
        name:    "aa",
        age:     1,
    }
    b := S{
        name:    "aa",
        age:     1,
    }

   fmt.Println(a == b)
}

其中a==b为true。如果我们将结构体中加入一个指针，就会返回false，这是因为指针指向的地址不一样，如下所示：

type S struct {
    Name    string
    Age     int
    Address *int
}

func main() {
    a := S{
        Name:    "aa",
        Age:     1,
        Address: new(int),
    }
    b := S{
        Name:    "aa",
        Age:     1,
        Address: new(int),
    }

   fmt.Println(a == b)
}

这时会返回false。

值得注意的是：slice、map、function是不能参与比较的，如果在结构体中出现以上类型，会panic。在这里我们就有一个疑问？到底是什么原因导致slice、map、function不能进行比较，如果是因为引用类型的原因，channel却可以进行比较。我们先来看看比较slice的时候返回的错误，如下所示：

1	`invalid operation: a == b (struct containing []int cannot be compared)`

有的博主说slice不可比较有两个原因：

引用类型，比较地址没有意义。
切片有len，cap，比较的维度不好衡量，因此go设计的时候就不允许切片可比较。

但是我们来看看这个情况：

type S struct {
	Name    string
	Age     int
	Ch	chan []int
}

func main() {
	a := S{
		Name:    "aa",
		Age:     1,
		Ch:      make(chan []int),
	}
	b := S{
		Name:    "aa",
		Age:     1,
		Ch:      make(chan []int),
	}

	fmt.Println(a == b)
}

但是在[]int的channel是可以比较的，这就会比较迷惑。

无独有偶，两个interface{}是能比较的，其规则如下：

两个类型相同且值相同的接口比较结果为true；
两个类型相同且值不同的接口比较结果为false；
两个类型不同的接口比较结果为false；
如果空接口保存了上面的slice、map和function的值，则不能比较。

总结：类型不同的空接口间的比较结果不相同，不能比较空接口中的动态值。

回到正题，我们来看看reflect.DeepEqual，reflect.DeepEqual在可以时（主要是基本类型）会使用==；但还会比较array、slice的成员，map的键值对，结构体字段进行深入比对。如下所示：

func main() {
	m1 := map[int]interface{}{1: []int{1, 2, 3}, 2: 3, 3: "a"}
	m2 := map[int]interface{}{1: []int{1, 2, 3}, 2: 3, 3: "a"}
	if reflect.DeepEqual(m1, m2) {
		fmt.Println("相等")
	}
}
//输出”相等”

当然，我们还是要从它的源码进行分析:

func DeepEqual(x, y interface{}) bool {
	if x == nil || y == nil {
		return x == y
	}
	v1 := ValueOf(x)
	v2 := ValueOf(y)
	if v1.Type() != v2.Type() {
		return false
	}
	return deepValueEqual(v1, v2, make(map[visit]bool))
}

我们可以看到，如果x==nil或者y==nil，就比较二者的指针，否则比较二者的类型，如果类型相同，那么我们就用deepValueEqual函数进行比较。我们看到这个函数：

```

### `unsafe`

>**Unsafe code**是一种绕过go类型安全和内存安全检查的Go代码。大多数情况，unsafe code是和指针相关的。但是要记住使用unsafe code有可能会损害你的程序，所以，如果你不完全确定是否需要用到unsafe code就不要使用它。
>
>[关于go中的unsafe包][https://studygolang.com/articles/22265]

Golang里面没有`warnning`这个说法啊，相比于C/C++，Golang里面一些危险的操作都是由`unsafe`包提供。

#### `unsafe.Pointer`

我以前有一个疑问：既然指针代表的是地址，那为什么还要分类呢？原来，针区分类型是为了在通过指针访问它所指向的存储空间的时候，能够正确访问，如果通过一个char类型的指针操作一个int的变量，如果值的二进制数据超过1字节，那么就造成数据错误。

我们先看如下例子：

```go
func main() {
	var value int64 = 5
	var p1 = &value
	var p2 = (*int32)(unsafe.Pointer(p1))
	fmt.Println(p1)
	fmt.Println(p2)
}

输出结果如下：

1 2	`0xc00001e0d0 0xc00001e0d0`

可以发现这两个指针所指向的地址是一样的，这个方法能让你创造一个int32的p2指针去指向一个int64的value变量，而这个变量是使用p1指针去访问的。我们通过以下例子来说明：

x := int32(5)
var p=(*byte)(unsafe.Pointer(&x))
s:=*p
fmt.Println(s)
//输出5

但是从byte转换成int32的时候会出现问题：

b:='5'
var p=(*int32)(unsafe.Pointer(&b))
i:=*p
fmt.Println(i)
//输出53

这是因为存放的b中存放的实际是ASCII码，故而转换成int时输出53。那么为什么转换成byte时就会输出5呢，我们用反射来看s的实际类型，显示是uint8，也就是说我们只是在这只是修改了指针类型或者说只是修改了编译器解释他的类型。

`uintptr`和`unsafe.Pointer`的区别

uintptr本质是一个无符号的整型，它的长度可以用来保存一个指针地址。unsafe包提供的Pointer表示可以指向任意类型的指针。

uintptr往往用来进行指针计算，因为它是整型，所以很容易计算出下一个指针所指向的位置。

unsafe.Pointer只是单纯的通用指针类型，用于转换不同类型指针，它不可以参与指针运算；
而uintptr是用于指针运算的，GC 不把 uintptr 当指针，也就是说 uintptr 无法持有对象， uintptr 类型的目标会被回收；
unsafe.Pointer 可以和普通指针进行相互转换；
unsafe.Pointer 可以和 uintptr 进行相互转换。

`sync`

sync包中提供了常见的并发编程同步原语，所谓原语，一般是指由若干条指令组成的程序段，用来实现某个特定的功能，在执行过程中不可被中断，否则就会出现操作错误，造成系统混乱。

`sync.Mutex`

sync.Mutex是sync包中使用最广泛的原语，它允许在共享资源上互斥访问。

type mutex struct{
	state	int32
	sema	uint32
}

上述是mutex的结构，state表示当前互斥锁的状态，sema是用于控制锁状态的信号量。在state中有一个标志位叫mutexStarving，表示当前的互斥锁是否进入了饥饿状态，在正常状态下，锁的等待者会按照先进先出的顺序获取锁；在饥饿模式下，互斥锁会直接交给等待队列最前面的 Goroutine。新的 Goroutine 在该状态下不能获取锁、也不会进入自旋状态，它们只会在队列的末尾等待。如果一个 Goroutine 获得了互斥锁并且它在队列的末尾或者它等待的时间少于 1ms，那么当前的互斥锁就会切换回正常模式。

`sync.Mutex.Lock`

func (m *Mutex) Lock() {
	if atomic.CompareAndSwapInt32(&m.state, 0, mutexLocked) {
		return
	}
	m.lockSlow()
}

在这里用到原子操作CAS，常常被用于自旋机制，具体讲解在下面。当锁的状态是0时，就会将mutexLocked位置设置为1，如果互斥锁的状态不是0就会调用lockSlow尝试通过自旋等待锁的释放。

`sync.Mutex.Unlock`

func (m *Mutex) Unlock() {
	new := atomic.AddInt32(&m.state, -mutexLocked)
	if new != 0 {
		m.unlockSlow(new)
	}
}

在Unlock中，用到了原子操作Add，这里这个原子操作的意思是：如果只是mutexLocked位为1，那么我们将state设置为0，return；否则，调用UnlockSlow进行缓慢解锁。也就是说如果有其他goroutine等待着，那么我们就会进入缓慢解锁的状态——移交锁的所有权给下一个goroutine。

`sync.RWMutex`

type RWMutex struct {
	w           Mutex  // held if there are pending writers
	writerSem   uint32 // semaphore for writers to wait for completing readers
	readerSem   uint32 // semaphore for readers to wait for completing writers
	readerCount int32  // number of pending readers
	readerWait  int32  // number of departing readers
}

我们可以看到，RWMutex继承了Mutex，并且增加了几个成员。我们先来说说这几个成员：

writerSem：写者等待读者完成的信号量；
readerSem：读者等待写者完成的信号量；
readerCount：当前有几个读者共享锁；
readerWait：离开的读者数。

`Rlock`&`RUnlock`

if atomic.AddInt32(&rw.readerCount, 1) < 0 {
	// A writer is pending, wait for it.
	runtime_SemacquireMutex(&rw.readerSem, false, 0)
}

如上述所示，上读锁的就是给readerCount+1，如果有写者占用，就

if r := atomic.AddInt32(&rw.readerCount, -1); r < 0 {
	// Outlined slow-path to allow the fast-path to be inlined
	rw.rUnlockSlow(r)
}

如上述所示，解读锁就是给readerCount-1，如果有

`Lock`&`Unlock`

r := atomic.AddInt32(&rw.readerCount, rwmutexMaxReaders)
if r >= rwmutexMaxReaders {
	race.Enable()
	throw("sync: Unlock of unlocked RWMutex")
}
// Unblock blocked readers, if any.
for i := 0; i < int(r); i++ {
	runtime_Semrelease(&rw.readerSem, false, 0)
}

`sync/atomic`

CPU执行一条汇编语句就是一个原子操作吗？

原子操作是指不会被多线程调度机制打断的操作，这种操作一旦开始，就一直运行到结束，中间不会有任何context switch。原子操作是不可分割的，在执行完毕之前不会被任何其它任务或事件中断。在单处理器系统（UniProcessor）中，能够在单条指令中完成的操作都可以认为是” 原子操作”，因为中断只能发生于指令之间。

说到这里，我们来看看维基百科上对原子操作的判定：

如果这个操作所处的层(layer)的更高层不能发现其内部实现与结构，那么这个操作是一个原子(atomic)操作。

再看看其定义：

原子操作可以是一个步骤，也可以是多个操作步骤，但是其顺序不可以被打乱，也不可以被切割而只执行其中的一部分。将整个操作视作一个整体是原子性的核心特征。

也就是说，绝大多数情况下，一个机器指令就是一个原子操作。在Intel的参考手册，CPU基于以下三种机制保证了多核中加锁的原子操作：

（1）一些基本的内存读写操作是本身已经被硬件提供了原子性保证（例如读写单个字节的操作）；
（2）一些需要保证原子性但是没有被第（1）条机制提供支持的操作（例如read-modify-write）可以通过使用”LOCK#”来锁定总线，从而保证操作的原子性
（3）因为很多内存数据是已经存放在L1/L2 cache中了，对这些数据的原子操作只需要与本地的cache打交道，而不需要与总线打交道，所以CPU就提供了cache coherency机制来保证其它的那些也cache了这些数据的processor能读到最新的值。

上面（1）就是由硬件保持的原子操作，具体来说有以下操作：

• Reading or writing a byte（一个字节的读写）
• Reading or writing a word aligned on a 16-bit boundary（对齐到16位边界的字的读写）
• Reading or writing a doubleword aligned on a 32-bit boundary（对齐到32位边界的双字的读写）

• Reading or writing a quadword aligned on a 64-bit boundary（对齐到64位边界的四字的读写）
• 16-bit accesses to uncached memory locations that fit within a 32-bit data bus（未缓存且在32位数据总线范围之内的内存地址的访问）

• Unaligned 16-, 32-, and 64-bit accesses to cached memory that fit within a cache line（对单个cache line中缓存地址的未对齐的16/32/64位访问)

参考文章

下面我们再看看（2）总线锁。

总线锁

处理器会自动保证基本的内存操作的原子性。处理器保证从系统内存当中读取或者写入一个字节是原子的，意思是当一个处理器读取一个字节时，其他处理器不能访问这个字节的内存地址。

上述操作就是通过总线锁实现的，在x86 平台上，CPU提供了在指令执行期间对总线加锁的手段，这样能实现并行时的原子操作。

Go支持的原子操作概述

Win32 API中常用的原子操作主要有三类，一种是加一减一操作，二是比较交换操作，三赋值操作。对于一个整数类型T，sync/atomic标准库包提供了下列原子操作函数。其中T可以是内置int32、int64、uint32、uint64和uintptr类型。

func AddT(addr *T, delta T)(new T)
func LoadT(addr *T) (val T)
func StoreT(addr *T, val T)
func SwapT(addr *T, new T) (old T)
func CompareAndSwapT(addr *T, old, new T) (swapped bool)

我们看看CompareAndSwap的源码：

Go语言的常量有个不同寻常之处。虽然一个常量可以有任意有一个确定的基础类型，例如int或float64，或者是类似time.Duration这样命名的基础类型，但是许多常量并没有一个明确的基础类型。编译器为这些没有明确的基础类型的数字常量提供比基础类型更高精度的算术运算；你可以认为至少有256bit的运算精度。这里有六种未明确类型的常量类型，分别是无类型的布尔型、无类型的整数、无类型的字符、无类型的浮点数、无类型的复数、无类型的字符串。

panic需要等defer结束后才会向上传递。出现panic的时候，会先按照defer的**先出的顺序执行，最后才会执行panic。

`encoding/json`

`Marshal`

`UnMarshal`

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

Golang与IO多路复用上一篇

Go runtime 下一篇

Golang_包解析

Go map

底层实现

container

container/list

container/heap

container/ring

reflect

reflect.DeepEqual

uintptr和unsafe.Pointer的区别

sync

sync.Mutex

sync.Mutex.Lock

sync.Mutex.Unlock

sync.RWMutex

Rlock&RUnlock

Lock&Unlock

sync/atomic

总线锁