go语言学习--4.方法和接口

1.方法

2.接口

2.1结构体类型

2.2具体类型向接口类型赋值

1.方法

方法一般是面向对象编程(OOP)的一个特性，在C++语言中方法对应一个类对象的成员函数，是关联到具体对象上的虚表中的。但是Go语言的方法却是关联到类型的，这样可以在编译阶段完成方法的静态绑定。一个面向对象的程序会用方法来表达其属性对应的操作，这样使用这个对象的用户就不需要直接去操作对象，而是借助方法来做这些事情。

实现C语言中的一组函数如下：

// 文件对象
type File struct {
    fd int
}

// 打开文件
func OpenFile(name string) (f *File, err error) {
    // ...
}

// 关闭文件
func CloseFile(f *File) error {
    // ...
}

// 读文件数据
func ReadFile(f *File, offset int64, data []byte) int {
    // ...
}

以上的三个函数都是普通的函数，需要占用包级空间中的名字资源。不过CloseFile和ReadFile函数只是针对File类型对象的操作，这时候我们更希望这类函数和操作对象的类型紧密绑定在一起。

所以在go语言中我们修改如下：

// 关闭文件
func (f *File) CloseFile() error {
    // ...
}

// 读文件数据
func (f *File) ReadFile(offset int64, data []byte) int {
    // ...
}

将CloseFile和ReadFile函数的第一个参数移动到函数名的开头，这两个函数就成了File类型独有的方法了（而不是File对象方法）

从代码角度看虽然只是一个小的改动，但是从编程哲学角度来看，Go语言已经是进入面向对象语言的行列了。我们可以给任何自定义类型添加一个或多个方法。每种类型对应的方法必须和类型的定义在同一个包中，因此是无法给int这类内置类型添加方法的（因为方法的定义和类型的定义不在一个包中）。对于给定的类型，每个方法的名字必须是唯一的，同时方法和函数一样也不支持重载。

2.接口

Go 语言提供了另外一种数据类型即接口，它把所有的具有共性的方法定义在一起，任何其他类型只要实现了这些方法就是实现了这个接口。

Go的接口类型是对其它类型行为的抽象和概括；因为接口类型不会和特定的实现细节绑定在一起，通过这种抽象的方式我们可以让对象更加灵活和更具有适应能力。很多面向对象的语言都有相似的接口概念，但Go语言中接口类型的独特之处在于它是满足隐式实现的鸭子类型。

所谓鸭子类型说的是：只要走起路来像鸭子、叫起来也像鸭子，那么就可以把它当作鸭子。Go语言中的面向对象就是如此，如果一个对象只要看起来像是某种接口类型的实现，那么它就可以作为该接口类型使用。

就比如说在c语言中，使用printf在终端输出的时候只能输出有限类型的几个变量，而在go中可以使用fmt.Printf，实际上是fmt.Fprintf向任意自定义的输出流对象打印，甚至可以打印到网络甚至是压缩文件，同时打印的数据不限于语言内置的基础类型，任意隐士满足fmt.Stringer接口的对象都可以打印，不满足fmt.Stringer接口的依然可以通过反射的技术打印。

2.1结构体类型

interface实际上就是一个结构体，包含两个成员。其中一个成员是指向具体数据的指针，另一个成员中包含了类型信息。空接口和带方法的接口略有不同，下面分别是空接口的数据结构：

struct Eface
{
    Type*    type;
    void*    data;
};

其中的Type指的是：

struct Type
{
    uintptr size;
    uint32 hash;
    uint8 _unused;
    uint8 align;
    uint8 fieldAlign;
    uint8 kind;
    Alg *alg;
    void *gc;
    String *string;
    UncommonType *x;
    Type *ptrto;
};

和带方法的接口使用的数据结构：

struct Iface
{
    Itab*    tab;
    void*    data;
};

其中的Iface指的是：

struct    Itab
{
    InterfaceType*    inter;
    Type*    type;
    Itab*    link;
    int32    bad;
    int32    unused;
    void    (*fun[])(void);   // 方法表
};

2.2具体类型向接口类型赋值

将一个具体类型数据赋值给interface这样的抽象类型，需要进行类型转换。这个转换过程中涉及哪些操作呢？

如果转换为空接口，返回一个Eface，将Eface中的data指针指向原型数据，type指针会指向数据的Type结构体。

如果将其转化为带方法的interface，需要进行一次检测，该类型必须实现interface中声明的所有方法才可以进行转换，这个检测将会在编译过程中进行。检测过程具体实现式通过比较具体类型的方法表和接口类型的方法表来进行的。

具体类型方法表：Type的UncommonType中有一个方法表，某个具体类型实现的所有方法都会被收集到这张表中。
接口类型方法表：Iface的Itab的InterfaceType中也有一张方法表，这张方法表中是接口所声明的方法。Iface中的Itab的func域也是一张方法表，这张表中的每一项就是一个函数指针，也就是只有实现没有声明。

这两处方法表都是排序过的，只需要一遍顺序扫描进行比较，应该可以知道Type中否实现了接口中声明的所有方法。最后还会将Type方法表中的函数指针，拷贝到Itab的fun字段中。Iface中的Itab的func域也是一张方法表，这张表中的每一项就是一个函数指针，也就是只有实现没有声明。

2.3获取接口类型数据的具体类型信息

接口类型转换为具体类型(也就是反射，reflect)，也涉及到了类型转换。reflect包中的TypeOf和ValueOf函数来得到接口变量的Type和Value。

3.channel

go中的channel是可以被存储在变量中，可以作为参数传递给函数，也可以作为函数返回值返回，我们先来看一下channel的结构体定义：

struct    Hchan
{
    uintgo    qcount;            // 队列q中的总数据数量
    uintgo    dataqsize;        // 环形队列q的数据大小
    uint16    elemsize;			// 当前队列的使用量
    bool    closed;				
    uint8    elemalign;
    Alg*    elemalg;        // interface for element type
    uintgo    sendx;            // 发送index
    uintgo    recvx;            // 接收index
    WaitQ    recvq;            // 因recv而阻塞的等待队列
    WaitQ    sendq;            // 因send而阻塞的等待队列
    Lock;
};

Hchan结构体中的核心部分是存放channel数据的环形队列，相关数据的作用已经在其后做出了备注。在该结构体中没有存放数据的域，如果是带缓冲区的chan，则缓冲区数据实际上是紧接着Hchan结构体中分配的。

另一个重要部分就是recvq和sendq两个链表，一个是因读这个通道而导致阻塞的goroutine，另一个是因为写这个通道而阻塞的goroutine。如果一个goroutine阻塞于channel了，那么它就被挂在recvq或sendq中。WaitQ是链表的定义，包含一个头结点和一个尾结点，该链表中中存放的成员是一个sudoG结构体变量，具体定义如下：

struct    SudoG
{
    G*    g;        // g and selgen constitute
    uint32    selgen;        // a weak pointer to g
    SudoG*    link;
    int64    releasetime;
    byte*    elem;        // data element
};

该结构体中最主要的是g和elem。elem用于存储goroutine的数据。读通道时，数据会从Hchan的队列中拷贝到SudoG的elem域。写通道时，数据则是由SudoG的elem域拷贝到Hchan的队列中。

Hchan结构如下：

3.1阻塞式读写channel操作

写操作代码如下，其中的c就是channel，v指的是数据：

c <- v

事实上基本的阻塞模式写channel操作在底层运行时库中对应的是一个runtime.chansend函数。具体如下：

void runtime·chansend(ChanType *t, Hchan *c, byte *ep, bool *pres, void *pc)

其中的ep指的是变量v的地址，这里的传值约定是调用者负责分配好ep的空间，仅需要简单的取变量地址就好了，pres是在select中的通道操作中使用的。

阻塞模式读操作的核心函数有两种包装如下：

chanrecv(c *hchan, ep unsafe.Pointer, block bool) (selected, received bool)

以及

chanrecv(c *hchan, ep unsafe.Pointer, block bool) (selected)

这两种的区别主要在于返回值是否会返回一个bool类型值，该值只是用于判断channel是否能读取出数据。

读写操作的以上阻塞的过程类似，故而不再做出说明，我们补充三个细节：

以上我们都强调是阻塞式的读写操作，其实相对应的也有非阻塞的读写操作，使用过select-case来进行调用的。
空通道，指的是将一个channel赋值为nil，或者调用后不适用make进行初始化。读写空通道是永远阻塞的。
关闭的通道，永远不会阻塞，会返回一个通道数据类型的零值。首先将closed置为1，第二步收集读等待队列recvq的所有sg，每个sg的elem都设为类型零值，第三步收集写等待队列sendq的所有sg，每个sg的elem都设为nil，最后唤醒所有收集的sg。

2.3非阻塞式读写channel操作

如上文所说，非阻塞式其实就是使用select-case来实现，在编译时将会被编译为if-else。

如：

select {
case v = <-c:
        ...foo
default:
        ...bar
}

就会被编译为：

if selectnbrecv(&v, c) {
        ...foo
} else {
        ...bar
}

至于其中的selectnbrecv相关的函数简单地调runtime.chanrecv函数，设置了一个参数，告诉runtime.chanrecv函数，当不能完成操作时不要阻塞，而是返回失败。

但是select中的case的执行顺序是随机的，而不像switch中的case那样一条一条的顺序执行。让每一个select都对应一个Select结构体。在Select数据结构中有个Scase数组，记录下了每一个case，而Scase中包含了Hchan。然后pollorder数组将元素随机排列，这样就可以将Scase乱序了。

4.map

map表的底层原理是哈希表，其结构体定义如下：

type Map struct {
    Key  *Type // Key type
    Elem *Type // Val (elem) type

    Bucket *Type // 哈希桶
    Hmap   *Type // 底层使用的哈希表元信息
    Hiter  *Type // 用于遍历哈希表的迭代器
}

其中的Hmap 的具体化数据结构如下：

type hmap struct {
    // Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go.
    // Make sure this stays in sync with the compiler's definition.
    count     int // map目前的元素数目
    flags     uint8 // map状态（正在被遍历/正在被写入）
    B         uint8  // 哈希桶数目以2为底的对数（哈希桶的数目都是 2 的整数次幂，用位运算来计算取余运算的值, 即 N mod M = N & (M-1))）
    noverflow uint16 //溢出桶的数目, 这个数值不是恒定精确的, 当其 B>=16 时为近似值
    hash0     uint32 // 随机哈希种子

    buckets    unsafe.Pointer // 指向当前哈希桶的指针
    oldbuckets unsafe.Pointer // 扩容时指向旧桶的指针
    nevacuate  uintptr        // 桶进行调整时指示的搬迁进度

    extra *mapextra // 表征溢出桶的变量
}

以上hmap基本都是涉及到了哈希桶和溢出桶，我们首先看一下它的数据结构，如下：

type bmap struct {
    topbits  [8]uint8    // 键哈希值的高8位
    keys     [8]keytype  // 哈希桶中所有键
    elems    [8]elemtype	// 哈希桶中所有值
    //pad      uintptr(新的 go 版本已经移除了该字段, 我未具体了解此处的 change detail, 之前设置该字段是为了在 nacl/amd64p32 上的内存对齐)
    overflow uintptr
}

我们会发现哈希桶bmap一般指定其能保存8个键值对，如果多于8个键值对，就会申请新的buckets，并将其于之前的buckets链接在一起。

其中的联系如图所示：

在具体插入时，首先会根据key值采用相应的hash算法计算对应的哈希值，将哈希值的低8位作为Hmap结构体中buckets数组的索引，找到key值所对应的bucket，将哈希值的高8位催出在bucket的tophash中。

特点如下：

map是无序的（原因为无序写入以及扩容导致的元素顺序发生变化），每次打印出来的map都会不一样，它不能通过index获取，而必须通过key获取

map的长度是不固定的，也就是和slice一样，也是一种引用类型内置的len函数同样适用于map，返回map拥有的key的数量

map的key可以是所有可比较的类型，如布尔型、整数型、浮点型、复杂型、字符串型……也可以键。

如下方式即可进行初始化：

var a map[keytype]valuetype

类型名	意义
a	map表名字
keytype	键类型
valuetype	键对应的值的类型

除此以外还可以使用make进行初始化，代码如下：

map_variable = make(map[key_data_type]value_data_type)

我们还可以使用初始值进行初始化，如下：

var m map[string]int = map[string]int{"hunter":12,"tony":10}

4.1插入数据

map的数据插入代码如下：

map_variable["mars"] = 27

插入过程如下：

根据key值计算出哈希值
取哈希值低位和hmap.B取模确定bucket位置
查找该key是否已经存在，如果存在则直接更新值
如果没有找到key，则将这一对key-value插入

4.2删除数据

delete(map, key) 函数用于删除集合的元素, 参数为 map 和其对应的 key。删除函数不返回任何值。相关代码如下：

   countryCapitalMap := map[string] string {"France":"Paris","Italy":"Rome","Japan":"Tokyo","India":"New Delhi"}
   /* 删除元素 */
   delete(countryCapitalMap,"France");

4.3查找数据

通过key获取map中对应的value值。语法为：map[key] .

但是当key如果不存在的时候，我们会得到该value值类型的默认值，比如string类型得到空字符串，int类型得到0。但是程序不会报错。

所以我们可以使用ok-idiom获取值，如下：value, ok := map[key] ，其中的value是返回值，ok是一个bool值，可知道key/value是否存在。

在map表中的查找过程如下：

查找或者操作map时，首先key经过hash函数生成hash值
通过哈希值的低8位来判断当前数据属于哪个桶
找到桶之后，通过哈希值的高八位与bucket存储的高位哈希值循环比对
如果相同就比较刚才找到的底层数组的key值，如果key相同，取出value
如果高八位hash值在此bucket没有，或者有，但是key不相同，就去链表中下一个溢出bucket中查找，直到查找到链表的末尾
如果查找不到，也不会返回空值，而是返回相应类型的0值。

4.4扩容

哈希表就是以空间换时间，访问速度是直接跟填充因子相关的，所以当哈希表太满之后就需要进行扩容。

如果扩容前的哈希表大小为2B扩容之后的大小为2(B+1)，每次扩容都变为原来大小的两倍，哈希表大小始终为2的指数倍，则有(hash mod 2B)等价于(hash & (2B-1))。这样可以简化运算，避免了取余操作。

1.触发扩容的条件？

负载因子(负载因子 = 键数量/bucket数量) > 6.5时，也即平均每个bucket存储的键值对达到6.5个。
溢出桶（overflow）数量 > 2^15时，也即overflow数量超过32768时。

什么是增量扩容呢？

如果负载因子>6.5时，进行增量扩容。这时会新建一个桶（bucket），新的bucket长度是原来的2倍，然后旧桶数据搬迁到新桶。每个旧桶的键值对都会分流到两个新桶中

主要是缩短map容器的响应时间。

假如我们直接将map用作某个响应实时性要求非常高的web应用存储，如果不采用增量扩容，当map里面存储的元素很多之后，扩容时系统就会卡往，导致较长一段时间内无法响应请求。不过增量扩容本质上还是将总的扩容时间分摊到了每一次哈希操作上面。