map

Golang的map采用的是hash表来实现的。我们知道hash映射中必须要解决一个问题：如何有效避免hash碰撞。避免hash碰撞的方式大致有：开放地址法，链地址法和建立一个公共溢出区。哈希表采用的是链地址来解决碰撞问题。
我们看下golang给map定义的底层数据结构：

type hmap struct {
    count     int 
    flags     uint8
    B         uint8  
    noverflow uint16 
    hash0     uint32 

    buckets    unsafe.Pointer
    oldbuckets unsafe.Pointer 
    nevacuate  uintptr        
    overflow *[2]*[]*bmap
}

hash表的大小由B字段来决定，大小为：2^B。count是提供给len()使用的。结构体中有一个buckets和一个oldbuckets是用来实现增量扩容的。正常使用的情况下oldbuckets为空，只有在扩容的时候才不为空。扩容的时候，oldbuckets指向buckets之前指向的地址，然后buckets指向重新扩容之后的地址，每次扩容都是上次大小的两倍。

struct Bucket
{
    uint8  tophash[BUCKETSIZE]; // hash值的高8位....低位从bucket的array定位到bucket
    Bucket *overflow;           // 溢出桶链表，如果有
    byte   data[1];             // BUCKETSIZE keys followed by BUCKETSIZE values
};

这里大体上绘制了一幅map的图：

map.png

将key的hash(key)低8位作为桶位置index信息，命中对应的下标之后，利用高8位在第一个bucket里面的tophash里面匹配key是否在这个bucke里面，如果不在就到下一个bucket里面寻找，如果在就取出value返回。至于hashtable的扩容问题，golang源码包里面给出一个扩容参数表格：

LOAD    %overflow  bytes/entry     hitprobe    missprobe
4.00         2.13        20.77         3.00         4.00
4.50         4.05        17.30         3.25         4.50
5.00         6.85        14.77         3.50         5.00
5.50        10.55        12.94         3.75         5.50
6.00        15.27        11.67         4.00         6.00
6.50        20.90        10.79         4.25         6.50
7.00        27.14        10.15         4.50         7.00
7.50        34.03         9.73         4.75         7.50
8.00        41.10         9.40         5.00         8.00

Slice

底层数组相同的不同切片，都是对这个数据的引用，因此改动切片的元素底层数据也会跟随着改变，如果你不想底层数据也变了，可以将切片copy出来，然后修改copy之后的数组（切记）。
slice中golang源码包中的结构如下：

struct    Slice
{
    byte*    array;
    uintgo    len;   
    uintgo    cap;
};

涉及到slice的最常用的操作是：append。在这个过程中会涉及到slice扩容的问题，扩容原则是：

1. 如果新的大小是当前大小2倍以上，则大小增长为新大小
2. 否则循环以下操作：如果当前大小小于1024，按每次2倍增长，否则每次按当前大小1/4增长。直到增长的大小超过或等于新大小。

slice还有一个常见的问题：new和make的区别。我们都知道初始化或者实例化一个slice变量，可以使用new也可以使用make，那么什么时候用new，什么时候用make呢？
new(T)返回一个*T，返回的这个指针可以被隐式地消除引用。而make(T, args)返回一个普通的T。通常情况下，T内部有一些隐式的指针。一句话，new返回一个指向已清零内存的指针，而make返回一个复杂的结构。

channel

channel是go语言中的一等公民啊，什么都可以装，参数和返回值及其他类型的数据。go语言中有一个经典语录：“要让通信来共享内存，而不是共享内存来通信”，那我们来看下channel的结构：

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

其中recvq是因读取而阻塞的goroutine队列，sendq是因写而阻塞的goroutine队列。队列的头部是：

struct    WaitQ
{
    SudoG*    first;
    SudoG*    last;
};

队列中的成员变量的结构是：

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

发送数据时先判断channel类型，如果有缓冲区，判断channel是否还有空间，然后从等待channel中获取等待channel中的接受者，如果取到接收者，则将对象直接传递给接受者，然后将接受者所在的go放入P所在的可运行G队列,发送过程完成，如果未取到接收者，则将发送者enqueue到发送channel，发送者进入阻塞状态，有缓冲的channel需要先判断channel缓冲是否还有空间，如果缓冲空间已满，则将发送者enqueue到发送channel，发送者进入阻塞状态如果缓冲空间未满，则将元素copy到缓冲中，这时发送者就不会进入阻塞状态，最后尝试唤醒等待队列中的一个接受者。(这段总结的话是来自：https://zhuanlan.zhihu.com/p/27295229)

接收channel与发送类似首先也是判断channel的类型，然后如果是有缓冲的channel就判断缓冲中是否有元素，接着从channel中获取接受者，如果取到，则直接从接收者获取元素，并唤醒发送者，本次接收过程完成，如果没有取到接收者，阻塞当前的goroutine并等待发送者唤醒，如果是拥有缓冲的channel需要先判断缓冲中是否有元素，缓冲为空时，阻塞当前goroutine并等待发送者唤醒，缓冲如果不为空，则取出缓冲中的第一个元素，然后尝试唤醒channel中的一个发送者。(这段总结的话是来自：https://zhuanlan.zhihu.com/p/27295229)

interface, select, ..., 都是值得分析的数据结构，后面再补充吧.... end~