//www.greatytc.com/p/aa0d4808cbb8

1、底层数据结构

    hashmap的定义位于src/runtime/hashmap.go 中,

struct hmap struct {

    count int // 元素个数

    flags uint8 // 状态标志

    B uint8 // 可以最多容纳 6.5 * 2 ^ B 个元素，6.5为装载因子

    noverflow uint16 // 溢出的个数

    hash0 uint32 // 哈希种子

    buckets unsafe.Pointer // 桶的地址

    oldbuckets unsafe.Pointer // 旧桶的地址，用于扩容

    nevacuate uintptr // 搬迁进度，小于nevacuate的已经搬迁

    overflow *[2]*[]*bmap

}

1、overflow是一个指针，指向一个元素个数为2的数组，数组的类型是一个指针，指向一个slice，slice的元素是桶(bmap)的地址，这些桶都是溢出桶；因为Go map在hash冲突过多时，会发生扩容操作，为了不全量搬迁数据，使用了增量搬迁，[0]表示当前使用的溢出桶集合，[1]是在发生扩容时，保存了旧的溢出桶集合；overflow存在的意义在于防止溢出桶被gc。

type bmap struct {

    // 每个元素hash值的高8位，如果tophash[0] < minTopHash，表示这个桶的搬迁状态 
     tophash [bucketCnt]uint8
     // 接下来是8个key、8个value，但是我们不能直接看到；为了优化对齐，go采用了key放在一起，value放在一起的存储方式，
     // 再接下来是hash冲突发生时，下一个溢出桶的地址

}

2、实现原理

        不同于STL中map以红黑树实现的方式，Golang采用了HashTable的实现，解决冲突采用的是链地址法。也就是说，使用数组+链表来实现map。

hashmap-buckets

    map是由数组+链表实现的HashTable，Golang通过hashtop快速试错加快了查找过程，利用空间换时间的思想解决了扩容的问题，利用将8个key(8个value)依次放置减少了padding空间等等。

3、扩容

    在分配assign逻辑中，当没有位置给key使用，而且满足测试条件(装载因子>6.5或有太多溢出通)时，会触发hashGrow逻辑。

    扩容阶段；在assign和delete操作中，都会触发扩容growWork。

    扩容策略：第一个大于count的2^B的B值。

example

4、并发安全

    并发操作，会看到读的时候会检查hashWriting标志， 如果有这个标志，就会报并发错误。

    h.flags |= hashWriting

    如果想在并发情况下使用，就要加锁，而且是加一把大锁。 加大锁大概率都不是最优解，一般都会有效率问题。 通俗说就是加大锁影响其他的元素操作了。

    解决思路：减少加锁时间。

    方法： 1.空间换时间。  2.降低影响范围。

sync.Map的使用：

       说白了，维护了两个字典。写的时候直接写dirty字典，读的时候先读read字典，然后再读dirty字典。

        type Map struct {

            mu Mutex

            read atomic.Value // readOnly

            dirty map[interface{}]*entry

            misses int

        } 

    mu：加锁作用。保护后文的dirty字段

    read：存读的数据。因为是atomic.Value类型，只读，所以并发是安全的。实际存的是readOnly的数据结构。

    misses：计数作用。每次从read中读失败，则计数+1。

    dirty：map[interface{}]*entry。包含最新写入的数据。当misses计数达到一定值，将其赋值给read。

    sync.Map的优缺点：优点：是官方出的，是亲儿子；通过读写分离，降低锁时间来提高效率； 缺点：不适用于大量写的场景，这样会导致read map读不到数据而进一步加锁读取，同时dirty map也会一直晋升为read map，整体性能较差。 适用场景：大量读，少量写