转载请注明出处：http://blog.csdn.net/luotuo44/article/details/42773231


        温馨提示：本文用到了一些可以在启动memcached设置的全局变量。关于这些全局变量的含义可以参考《memcached启动参数详解》。对于这些全局变量，处理方式就像《如何阅读memcached源代码》所说的那样直接取其默认值。



        assoc.c文件里面的代码是构造一个哈希表。memcached快的一个原因是使用了哈希表。现在就来看一下memcached是怎么使用哈希表的。

哈希结构：

        main函数会调用assoc_init函数申请并初始化哈希表。为了减少哈希表发生冲突的可能性，memcached的哈希表是比较长的，并且哈希表的长度为2的幂。全局变量hashpower用来记录2的幂次。main函数调用assoc_init函数时使用全局变量settings.hashpower_init作为参数，用于指明哈希表初始化时的幂次。settings.hashpower_init可以在启动memcached的时候设置，具体可以参考《memcached启动参数详解以及关键配置的默认值》。

//memcached.h文件
#define HASHPOWER_DEFAULT 16

//assoc.h文件
unsigned int hashpower = HASHPOWER_DEFAULT;

#define hashsize(n) ((ub4)1<<(n))//这里是1 左移 n次
//hashsize(n)为2的幂，所以hashmask的值的二进制形式就是后面全为1的数。这就很像位操作里面的 & 
//value & hashmask(n)的结果肯定是比hashsize(n)小的一个数字.即结果在hash表里面
//hashmask(n)也可以称为哈希掩码
#define hashmask(n) (hashsize(n)-1)

//哈希表数组指针
static item** primary_hashtable = 0;


//默认参数值为0。本函数由main函数调用，参数的默认值为0
void assoc_init(const int hashtable_init) {
    if (hashtable_init) {
        hashpower = hashtable_init;
    }

	//因为哈希表会慢慢增大，所以要使用动态内存分配。哈希表存储的数据是一个
	//指针，这样更省空间。
	//hashsize(hashpower)就是哈希表的长度了
    primary_hashtable = calloc(hashsize(hashpower), sizeof(void *));
    if (! primary_hashtable) {
        fprintf(stderr, "Failed to init hashtable.\n");
        exit(EXIT_FAILURE);//哈希表是memcached工作的基础，如果失败只能退出运行
    }
	
}


        说到哈希表，那么就对应有两个问题：哈希算法，怎么解决冲突。
        对于哈希函数(算法)，memcached直接使用开源的MurmurHash3和jenkins_hash两个中的一个。默认是使用jenkins，可以在启动memcached的时候设置设置为MurmurHash3。memcached是直接把客户端输入的键值作为哈希算法的输入，得到一个32位的无符号整型输出(用变量hv存储)。因为哈希表的长度没有2^32- 1这么大，所以需要一个函数将hv映射在哈希表的范围之内。memcached采用了最简单的取模运算作为映射函数，即hv%hashsize(hashpower)。对于CPU而言，取模运算是一个比较耗时的操作。所以memcached利用哈希表的长度是2的幂的性质，采用位操作进行优化，即:
 hv & hashmask(hashpower)。因为对哈希表进行增删查操作都需要定位，所以经常本文的代码中经常会出现hv & hashmask(hashpower)。
        memcached使用最常见的链地址法解决冲突问题。从前面的代码可以看到，primary_hashtable是一个的二级指针变量，它指向的是一个一维指针数组，数组的每一个元素指向一条链表(链表上的item节点具有相同的哈希值)。数组的每一个元素，在memcached里面也称为桶(bucket)，所以后文的表述中会使用桶。下图是一个哈希表，其中第0号桶有2个item，第2、3、5号桶各有一个item。item就是用来存储用户数据的结构体。
        




基本操作：


插入item:

        接着看一下怎么在哈希表中插入一个item。它是直接根据哈希值找到哈希表中的位置(即找到对应的桶)，然后使用头插法插入到桶的冲突链中。item结构体有一个专门的h_next指针成员变量用于连接哈希冲突链。
static unsigned int hash_items = 0;//hash表中item的个数

/* Note: this isn't an assoc_update.  The key must not already exist to call this */
//hv是这个item键值的哈希值
int assoc_insert(item *it, const uint32_t hv) {
    unsigned int oldbucket;

	//使用头插法 插入一个item
	//第一次看本函数，直接看else部分
    if (expanding &&
        (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
    {
		...
    } else {
		//使用头插法插入哈希表中
        it->h_next = primary_hashtable[hv & hashmask(hashpower)];
        primary_hashtable[hv & hashmask(hashpower)] = it;
    }

    hash_items++;//哈希表的item数量加一
	…
    return 1;
}


查找item：

        往哈希表插入item后，就可以开始查找item了。下面看一下怎么在哈希表中查找一个item。item的键值hv只能定位到哈希表中的桶位置，但一个桶的冲突链上可能有多个item，所以除了查找的时候除了需要hv外还需要item的键值。
//由于哈希值只能确定是在哈希表中的哪个桶(bucket)，但一个桶里面是有一条冲突链的
//此时需要用到具体的键值遍历并一一比较冲突链上的所有节点。虽然key是以'\0'结尾
//的字符串，但调用strlen还是有点耗时(需要遍历键值字符串)。所以需要另外一个参数
//nkey指明这个key的长度
item *assoc_find(const char *key, const size_t nkey, const uint32_t hv) {
    item *it;
    unsigned int oldbucket;

	//直接看else部分
    if (expanding &&
        (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
    {
        it = old_hashtable[oldbucket];
    } else {
    	//由哈希值判断这个key是属于那个桶(bucket)的
        it = primary_hashtable[hv & hashmask(hashpower)];
    }

	//到这里，已经确定这个key是属于那个桶的。 遍历对应桶的冲突链即可

    item *ret = NULL;
    while (it) {
		//长度相同的情况下才调用memcmp比较，更高效
        if ((nkey == it->nkey) && (memcmp(key, ITEM_key(it), nkey) == 0)) {
            ret = it;
            break;
        }
        it = it->h_next;
    }
    return ret;
}


删除item：

        下面看一下从哈希表中删除一个item是怎么实现的。从链表中删除一个节点的常规做法是：先找到这个节点的前驱节点，然后使用前驱节点的next指针进行删除和拼接操作。memcached的做法差不多，实现如下：
void assoc_delete(const char *key, const size_t nkey, const uint32_t hv) {
    item **before = _hashitem_before(key, nkey, hv);//得到前驱节点的h_next成员地址

    if (*before) {//查找成功
        item *nxt;
        hash_items--;
		//因为before是一个二级指针，其值为所查找item的前驱item的h_next成员地址.
		//所以*before指向的是所查找的item.因为before是一个二级指针，所以
		//*before作为左值时，可以给h_next成员变量赋值。所以下面三行代码是
		//使得删除中间的item后，前后的item还能连得起来。
        nxt = (*before)->h_next;
        (*before)->h_next = 0;   /* probably pointless, but whatever. */
        *before = nxt;
        return;
    }
    /* Note:  we never actually get here.  the callers don't delete things
       they can't find. */
    assert(*before != 0);
}



//查找item。返回前驱节点的h_next成员地址,如果查找失败那么就返回冲突链中最后
//一个节点的h_next成员地址。因为最后一个节点的h_next的值为NULL。通过对返回值
//使用 * 运算符即可知道有没有查找成功。
static item** _hashitem_before (const char *key, const size_t nkey, const uint32_t hv) {
    item **pos;
    unsigned int oldbucket;

	//同样，看的时候直接跳到else部分
    if (expanding &&//正在扩展哈希表
        (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
    {
        pos = &old_hashtable[oldbucket];
    } else {
    	//找到哈希表中对应的桶位置
        pos = &primary_hashtable[hv & hashmask(hashpower)];
    }

	//遍历桶的冲突链查找item
    while (*pos && ((nkey != (*pos)->nkey) || memcmp(key, ITEM_key(*pos), nkey))) {
        pos = &(*pos)->h_next;
    }
	//*pos就可以知道有没有查找成功。如果*pos等于NULL那么查找失败，否则查找成功。
    return pos;
}




扩展哈希表：
        当哈希表中item的数量达到了哈希表表长的1.5倍时，那么就会扩展哈希表增大哈希表的表长。memcached在插入一个item时会检查当前的item总数是否达到了哈希表表长的1.5倍。由于item的哈希值是比较均匀的，所以平均来说每个桶的冲突链长度大概就是1.5个节点。所以memcached的哈希查找还是很快的。



迁移线程：

        扩展哈希表有一个很大的问题：扩展后哈希表的长度变了，item哈希后的位置也是会跟着变化的(回忆一下memcached是怎么根据键值的哈希值确定桶的位置的)。所以如果要扩展哈希表，那么就需要对哈希表中所有的item都要重新计算哈希值得到新的哈希位置(桶位置)，然后把item迁移到新的桶上。对所有的item都要做这样的处理，所以这必然是一个耗时的操作。后文会把这个操作称为数据迁移。
        因为数据迁移是一个耗时的操作，所以这个工作由一个专门的线程(姑且把这个线程叫做迁移线程吧)负责完成。这个迁移线程是由main函数调用一个函数创建的。看下面代码：
#define DEFAULT_HASH_BULK_MOVE 1
int hash_bulk_move = DEFAULT_HASH_BULK_MOVE;

//main函数会调用本函数，启动数据迁移线程
int start_assoc_maintenance_thread() {
    int ret;
    char *env = getenv("MEMCACHED_HASH_BULK_MOVE");
    if (env != NULL) {
		//hash_bulk_move的作用在后面会说到。这里是通过环境变量给hash_bulk_move赋值
        hash_bulk_move = atoi(env);
        if (hash_bulk_move == 0) {
            hash_bulk_move = DEFAULT_HASH_BULK_MOVE;
        }
    }
    if ((ret = pthread_create(&maintenance_tid, NULL,
                              assoc_maintenance_thread, NULL)) != 0) {
        fprintf(stderr, "Can't create thread: %s\n", strerror(ret));
        return -1;
    }
    return 0;
}

        迁移线程被创建后会进入休眠状态(通过等待条件变量)，当worker线程插入item后，发现需要扩展哈希表就会调用assoc_start_expand函数唤醒这个迁移线程。
static bool started_expanding = false;

//assoc_insert函数会调用本函数，当item数量到了哈希表表长的1.5倍才会调用的
static void assoc_start_expand(void) {
    if (started_expanding)
        return;
    started_expanding = true;
    pthread_cond_signal(&maintenance_cond);
}


static bool expanding = false;//标明hash表是否处于扩展状态
static volatile int do_run_maintenance_thread = 1;
static void *assoc_maintenance_thread(void *arg) {

	//do_run_maintenance_thread是全局变量，初始值为1，在stop_assoc_maintenance_thread
	//函数中会被赋值0，终止迁移线程
    while (do_run_maintenance_thread) {
        int ii = 0;

		//上锁
        item_lock_global();
        mutex_lock(&cache_lock);

		...//进行item迁移

		//遍历完就释放锁
        mutex_unlock(&cache_lock);
        item_unlock_global();


        if (!expanding) {//不需要迁移数据(了)。
            /* We are done expanding.. just wait for next invocation */
            mutex_lock(&cache_lock);
            started_expanding = false; //重置

			//挂起迁移线程，直到worker线程插入数据后发现item数量已经到了1.5倍哈希表大小，
			//此时调用worker线程调用assoc_start_expand函数，该函数会调用pthread_cond_signal
			//唤醒迁移线程
            pthread_cond_wait(&maintenance_cond, &cache_lock);
            mutex_unlock(&cache_lock);

			...

            mutex_lock(&cache_lock);
            assoc_expand();//申请更大的哈希表,并将expanding设置为true
            mutex_unlock(&cache_lock);
        }
    }
    return NULL;
}


逐步迁移数据：

        为了避免在迁移的时候worker线程增删哈希表，所以要在数据迁移的时候加锁，worker线程抢到了锁才能增删查找哈希表。memcached为了实现快速响应(即worker线程能够快速完成增删查找操作)，就不能让迁移线程占锁太久。但数据迁移本身就是一个耗时的操作，这是一个矛盾。
        memcached为了解决这个矛盾，就采用了逐步迁移的方法。其做法是，在一个循环里面：加锁-》只进行小部分数据的迁移-》解锁。这样做的效果是：虽然迁移线程会多次抢占锁，但每次占有锁的时间都是很短的，这就增加了worker线程抢到锁的概率，使得worker线程能够快速完成它的操作。一小部分是多少个item呢？前面说到的全局变量hash_bulk_move就指明是多少个桶的item，默认值是1个桶，后面为了方便叙述也就认为hash_bulk_move的值为1。
        逐步迁移的具体做法是，调用assoc_expand函数申请一个新的更大的哈希表，每次只迁移旧哈希表一个桶的item到新哈希表，迁移完一桶就释放锁。此时就要求有一个旧哈希表和新哈希表。在memcached实现里面，用primary_hashtable表示新表(也有一些博文称之为主表)，old_hashtable表示旧表(副表)。
        前面说到，迁移线程被创建后就会休眠直到被worker线程唤醒。当迁移线程醒来后，就会调用assoc_expand函数扩大哈希表的表长。assoc_expand函数如下：
static void assoc_expand(void) {
    old_hashtable = primary_hashtable;

	//申请一个新哈希表，并用old_hashtable指向旧哈希表
    primary_hashtable = calloc(hashsize(hashpower + 1), sizeof(void *));
    if (primary_hashtable) {

        hashpower++;
        expanding = true;//标明已经进入扩展状态
        expand_bucket = 0;//从0号桶开始数据迁移
    } else {
        primary_hashtable = old_hashtable;
        /* Bad news, but we can keep running. */
    }
}


        现在看一下完整一点的assoc_maintenance_thread线程函数，体会迁移线程是怎么逐步数据迁移的。为什么说完整一点呢？因为该函数里面还是有一些东西本篇博文是没有解释的，但这并不妨碍我们阅读该函数。后面还会有其他博文对这个线程函数进行讲解的。


static unsigned int expand_bucket = 0;//指向待迁移的桶

#define DEFAULT_HASH_BULK_MOVE 1
int hash_bulk_move = DEFAULT_HASH_BULK_MOVE;

static volatile int do_run_maintenance_thread = 1;

static void *assoc_maintenance_thread(void *arg) {

	//do_run_maintenance_thread是全局变量，初始值为1，在stop_assoc_maintenance_thread
	//函数中会被赋值0，终止迁移线程
    while (do_run_maintenance_thread) {
        int ii = 0;

		//上锁
        item_lock_global();
        mutex_lock(&cache_lock);

		//hash_bulk_move用来控制每次迁移，移动多少个桶的item。默认是一个.
		//如果expanding为true才会进入循环体，所以迁移线程刚创建的时候，并不会进入循环体
		for (ii = 0; ii < hash_bulk_move && expanding; ++ii) {
            item *it, *next;
            int bucket;

			//在assoc_expand函数中expand_bucket会被赋值0
			//遍历旧哈希表中由expand_bucket指明的桶,将该桶的所有item
			//迁移到新哈希表中。
            for (it = old_hashtable[expand_bucket]; NULL != it; it = next) {
                next = it->h_next;

				//重新计算新的哈希值,得到其在新哈希表的位置
                bucket = hash(ITEM_key(it), it->nkey) & hashmask(hashpower);

				//将这个item插入到新哈希表中
				it->h_next = primary_hashtable[bucket];
                primary_hashtable[bucket] = it;
            }

			//不需要清空旧桶。直接将冲突链的链头赋值为NULL即可
            old_hashtable[expand_bucket] = NULL;

			//迁移完一个桶，接着把expand_bucket指向下一个待迁移的桶
            expand_bucket++;
			
            if (expand_bucket == hashsize(hashpower - 1)) {//全部数据迁移完毕
                expanding = false; //将扩展标志设置为false
                free(old_hashtable);
            }
        }

		//遍历完hash_bulk_move个桶的所有item后，就释放锁
        mutex_unlock(&cache_lock);
        item_unlock_global();


        if (!expanding) {//不再需要迁移数据了。
            /* finished expanding. tell all threads to use fine-grained(细粒度的) locks */
			//进入到这里，说明已经不需要迁移数据(停止扩展了)。

			...
            mutex_lock(&cache_lock);
            started_expanding = false; //重置

			//挂起迁移线程，直到worker线程插入数据后发现item数量已经到了1.5倍哈希表大小，
			//此时调用worker线程调用assoc_start_expand函数，该函数会调用pthread_cond_signal
			//唤醒迁移线程
            pthread_cond_wait(&maintenance_cond, &cache_lock);
            /* Before doing anything, tell threads to use a global lock */
            mutex_unlock(&cache_lock);

			...
            mutex_lock(&cache_lock);
            assoc_expand();//申请更大的哈希表,并将expanding设置为true
            mutex_unlock(&cache_lock);
        }
    }
    return NULL;
}



回马枪：

        现在再回过头来再看一下哈希表的插入、删除和查找操作，因为这些操作可能发生在哈希表迁移阶段。有一点要注意，在assoc.c文件里面的插入、删除和查找操作，是看不到加锁操作的。但前面已经说了，需要和迁移线程抢占锁，抢到了锁才能进行对应的操作。其实，这锁是由插入、删除和查找的调用者(主调函数)负责加的，所以在代码里面看不到。
        因为插入的时候可能哈希表正在扩展，所以插入的时候要面临一个选择：插入到新表还是旧表？memcached的做法是：当item对应在旧表中的桶还没被迁移到新表的话，就插入到旧表，否则插入到新表。下面是插入部分的代码。
/* Note: this isn't an assoc_update.  The key must not already exist to call this */
//hv是这个item键值的哈希值
int assoc_insert(item *it, const uint32_t hv) {
    unsigned int oldbucket;


	//使用头插法 插入一个item
    if (expanding &&//目前处于扩展hash表状态
        (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)//数据迁移时还没迁移到这个桶
    {
    	//插入到旧表
        it->h_next = old_hashtable[oldbucket];
        old_hashtable[oldbucket] = it;
    } else {
    	//插入到新表
        it->h_next = primary_hashtable[hv & hashmask(hashpower)];
        primary_hashtable[hv & hashmask(hashpower)] = it;
    }

    hash_items++;//哈希表的item数量加一
	//当hash表的item数量到达了hash表容量的1.5倍时，就会进行扩展
	//当然如果现在正处于扩展状态，是不会再扩展的
    if (! expanding && hash_items > (hashsize(hashpower) * 3) / 2) {
        assoc_start_expand();//唤醒迁移线程，扩展哈希表
    }

    return 1;
}

        这里有一个疑问，为什么不直接插入到新表呢？直接插入到新表对于数据一致性来说完全是没有问题的啊。网上有人说是为了保证同一个桶item的顺序，但由于迁移线程和插入线程对于锁抢占的不确定性，任何顺序都不能通过assoc_insert函数来保证。本文认为是为了快速查找。如果是直接插入到新表，那么在查找的时候就可能要同时查找新旧两个表才能找到item。查找完一个表，发现没有，然后再去查找另外一个表，这样的查找被认为是不够快速的。
        如果按照assoc_insert函数那样的实现，不用查找两个表就能找到item。看下面的查找函数。
//由于哈希值只能确定是在哈希表中的哪个桶(bucket)，但一个桶里面是有一条冲突链的
//此时需要用到具体的键值遍历并一一比较冲突链上的所有节点。因为key并不是以'\0'结尾
//的字符串，所以需要另外一个参数nkey指明这个key的长度
item *assoc_find(const char *key, const size_t nkey, const uint32_t hv) {
    item *it;
    unsigned int oldbucket;

    if (expanding &&//正在扩展哈希表
        (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)//该item还在旧表里面
    {
        it = old_hashtable[oldbucket];
    } else {
    	//由哈希值判断这个key是属于那个桶(bucket)的
        it = primary_hashtable[hv & hashmask(hashpower)];
    }

	//到这里已经确定了要查找的item是属于哪个表的了，并且也确定了桶位置。遍历对应桶的冲突链即可

    item *ret = NULL;
    while (it) {
		//长度相同的情况下才调用memcmp比较，更高效
        if ((nkey == it->nkey) && (memcmp(key, ITEM_key(it), nkey) == 0)) {
            ret = it;
            break;
        }
        it = it->h_next;
    }

    return ret;
}



        删除操作和查找操作差不多，这里直接贴出，不多说了。删除操作也是要进行查找操作的。
void assoc_delete(const char *key, const size_t nkey, const uint32_t hv) {
    item **before = _hashitem_before(key, nkey, hv);//得到前驱节点的h_next成员地址

    if (*before) {//查找成功
        item *nxt;
        hash_items--;

		//因为before是一个二级指针，其值为所查找item的前驱item的h_next成员地址.
		//所以*before指向的是所查找的item.因为before是一个二级指针，所以
		//*before作为左值时，可以给h_next成员变量赋值。所以下面三行代码是
		//使得删除中间的item后，前后的item还能连得起来。
        nxt = (*before)->h_next;
        (*before)->h_next = 0;   /* probably pointless, but whatever. */
        *before = nxt;
        return;
    }
    /* Note:  we never actually get here.  the callers don't delete things
       they can't find. */
    assert(*before != 0);
}


//查找item。返回前驱节点的h_next成员地址,如果查找失败那么就返回冲突链中最后
//一个节点的h_next成员地址。因为最后一个节点的h_next的值为NULL。通过对返回值
//使用 * 运算符即可知道有没有查找成功。
static item** _hashitem_before (const char *key, const size_t nkey, const uint32_t hv) {
    item **pos;
    unsigned int oldbucket;

    if (expanding &&//正在扩展哈希表
        (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
    {
        pos = &old_hashtable[oldbucket];
    } else {
    	//找到哈希表中对应的桶位置
        pos = &primary_hashtable[hv & hashmask(hashpower)];
    }

	//到这里已经确定了要查找的item是属于哪个表的了，并且也确定了桶位置。遍历对应桶的冲突链即可
	
	//遍历桶的冲突链查找item
    while (*pos && ((nkey != (*pos)->nkey) || memcmp(key, ITEM_key(*pos), nkey))) {
        pos = &(*pos)->h_next;
    }
	//*pos就可以知道有没有查找成功。如果*pos等于NULL那么查找失败，否则查找成功。
    return pos;
}



        由上面的讨论可以知道，插入和删除一个item都必须知道这个item对应的桶有没有被迁移到新表上了。

今天来学习一下Dictionary的源码底层实现
一、全局变量
		// 字典中数据的基本存储单元、条目，可以认为是一个链表的结点
        private struct Entry 
        {
            public int hashCode;    // 哈希码，Lower 31 bits of hash code, -1 if unused
            public int next;        // 同一个槽位上，下一个链表结点在entries数组中对应的索引，Index of next entry, -1 if last
            public TKey key;        // 字典的key，Key of entry
            public TValue value;    // 字典的value，Value of entry
        }

		// hash桶，长度size为比字典容量capacity大的最小质数，索引相当于桶的槽位targetBucket，值为key映射到Entry数组的索引
		// 值其实就是所有碰撞到该槽位的链表的根结点在Entry数组中的索引（这里比较绕）
        private int[] buckets;
        // Entry数组存放实际的数据，长度size为比容量capacity大的最小质数
        private Entry[] entries;
        private int count; 	   // entries数组中所有曾经添加过的长度，只增不减，Clear时清0，删除操作count不会变，freeCount会+1
        private int version;
        private int freeList;  // 被删除元素所在Entry组成链表的头结点，插入时先插入到这里
        private int freeCount; // 已经删除元素的数量，初始为0
        private IEqualityComparer<TKey> comparer;
        private KeyCollection keys;
        private ValueCollection values;
        private Object _syncRoot;

二、初始化
		// HashTable中预存的int类型的所有质数
        public static readonly int[] primes = 
        {
            3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919,
            1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591,
            17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437,
            187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263,
            1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369
        };

        private void Initialize(int capacity) 
        {
        	// 调用HashTable的方法获取比字典容量大的最小质数，如果没有手动设置容量，程序会在Insert时以capacity = 0进行初始化，此时容量是0，但得到的size是3
            int size = HashHelpers.GetPrime(capacity);
            buckets = new int[size];
            for (int i = 0; i < buckets.Length; i++) buckets[i] = -1;
            entries = new Entry[size];
            freeList = -1;
        }

三、Hash碰撞

HashCode

0x7FFFFFFF是16进制表示的最大正整型数，此处是为了忽略符号位，获取非负数哈希码

		int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;


原理

主要是为了得到桶的槽位信息，首先根据key获取hashCode，然后hashCode与hash桶进行碰撞，以获取碰撞到的槽位，根据槽位上的值即可确定该元素在entries中的位置

		int targetBucket = hashCode % buckets.Length;


冲突

不同的key有可能碰撞到同一个槽位上，如：4%5=4和9%5=4，不同的键4,9都碰撞到了索引为4的槽上
拉链法

将每一个元素视为一个单链表结点，如果该槽位只对应一个元素，则该单链表只有一个结点，碰撞到同一个槽位上的元素之间通过next指针建立联系，查找时如果链表不止一个结点，遍历该单链表即可

四、属性与方法


注意各种长度

size： Entry数组与Hash桶数组（以下简称数组）的总长度，质数，扩容的临界长度，所有长度中最大

capacity： 程序员可以手动设置的容量，只在字典初始化时用，用于决定数组的大小，程序员没有手动设置时，程序会在Insert方法时以0进行初始化，此时得到的size是最小质数3

count： 所有数组中曾经添加过元素的长度，等于size时扩容

freeCount： 数组中某位置之前添加元素了，后又被删除了，目前没有元素，这样的位置的总和

Count： 所有字典或数组中实际目前存在的元素个数，暴露给外界的接口


获取字典的长度：总长度减去删除的长度


        public int Count 
        {
            get { return count - freeCount; }
        }


字典元素的增加：字典的Add过程

        private void Insert(TKey key, TValue value, bool add) {
            if( key == null ) {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
            }
            if (buckets == null) Initialize(0);
            // hash碰撞
            int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
            int targetBucket = hashCode % buckets.Length;
#if FEATURE_RANDOMIZED_STRING_HASHING
            int collisionCount = 0;
#endif
			// 如果i >= 0说明之前已经有元素碰撞到这个槽位，该槽位至少有一个结点
            for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next) {
            	// 先检查是否字典中是否已经存在该键
                if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) {
                    if (add) { 
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
                    }
                    entries[i].value = value;
                    version++;
                    return;
                } 
#if FEATURE_RANDOMIZED_STRING_HASHING
                collisionCount++;
#endif
            }
            int index;
            // 字典之前有元素被删除，优先插入到被删除的部位
            if (freeCount > 0) {
                index = freeList;
                freeList = entries[index].next;
                freeCount--;
            }
            else {
                if (count == entries.Length) // 字典装不下了扩容
                {
                    Resize();
                    targetBucket = hashCode % buckets.Length;
                }
                index = count;
                count++;
            }
            // 将该结点设为头结点，指向原来的头结点
            entries[index].hashCode = hashCode;
            entries[index].next = buckets[targetBucket];
            entries[index].key = key;
            entries[index].value = value;
            buckets[targetBucket] = index;
            version++;
#if FEATURE_RANDOMIZED_STRING_HASHING
#if FEATURE_CORECLR
            // In case we hit the collision threshold we'll need to switch to the comparer which is using randomized string hashing
            // in this case will be EqualityComparer<string>.Default.
            // Note, randomized string hashing is turned on by default on coreclr so EqualityComparer<string>.Default will 
            // be using randomized string hashing
            if (collisionCount > HashHelpers.HashCollisionThreshold && comparer == NonRandomizedStringEqualityComparer.Default) 
            {
                comparer = (IEqualityComparer<TKey>) EqualityComparer<string>.Default;
                Resize(entries.Length, true);
            }
#else
			// 如果碰撞次数超过阀值进行扩容，注意该次扩容并没有扩大容量，而是重新计算了hashCode（更改了comparer）
            if(collisionCount > HashHelpers.HashCollisionThreshold && HashHelpers.IsWellKnownEqualityComparer(comparer)) 
            {
                comparer = (IEqualityComparer<TKey>) HashHelpers.GetRandomizedEqualityComparer(comparer);
                Resize(entries.Length, true); // 注意这里长度并没有变，注意这里的2个参数
            }
#endif // FEATURE_CORECLR
#endif
        } 

public const int HashCollisionThreshold = 100; // 默认碰撞次数阀值为100


字典的扩容：两种情况，重建hash链，触发详见Insert方法


容量不足时扩容，调用HashTable的ExpandPrime方法先扩大容量为原来的2倍，再取最小质数
碰撞次数超过阀值时扩容，根据源码并没有扩大数组的大小，只是重新计算了HashCode（更改了comparer）

        private void Resize() 
        {
            Resize(HashHelpers.ExpandPrime(count), false);
        }

        public static int ExpandPrime(int oldSize)
        {
            int newSize = 2 * oldSize;
            // Allow the hashtables to grow to maximum possible size (~2G elements) before encoutering capacity overflow.
            // Note that this check works even when _items.Length overflowed thanks to the (uint) cast
            if ((uint)newSize > MaxPrimeArrayLength && MaxPrimeArrayLength > oldSize)
            {
                Contract.Assert( MaxPrimeArrayLength == GetPrime(MaxPrimeArrayLength), "Invalid MaxPrimeArrayLength");
                return MaxPrimeArrayLength;
            }
            return GetPrime(newSize);
        }

        // 第二个参数是否强制更新hashCode、是否由于碰撞次数过多引起的扩容
        private void Resize(int newSize, bool forceNewHashCodes) 
        {
            Contract.Assert(newSize >= entries.Length);
            int[] newBuckets = new int[newSize];
            for (int i = 0; i < newBuckets.Length; i++) newBuckets[i] = -1;
            Entry[] newEntries = new Entry[newSize];
            Array.Copy(entries, 0, newEntries, 0, count); // 将原来的数据拷贝过来
            if(forceNewHashCodes) {
                for (int i = 0; i < count; i++) {
                    if(newEntries[i].hashCode != -1) {
                        newEntries[i].hashCode = (comparer.GetHashCode(newEntries[i].key) & 0x7FFFFFFF);
                    }
                }
            }
            // 重建hash链
            for (int i = 0; i < count; i++) {
                if (newEntries[i].hashCode >= 0) {
                    int bucket = newEntries[i].hashCode % newSize;
                    // 如果该槽位已经有元素，则更新链表的头结点为当前元素
                    newEntries[i].next = newBuckets[bucket];
                    newBuckets[bucket] = i;
                }
            }
            buckets = newBuckets;
            entries = newEntries;
        }


字典元素的删除：只需要删除键，有一个bool返回值

        public bool Remove(TKey key) {
            if(key == null) {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
            }
            if (buckets != null) {
                int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
                int bucket = hashCode % buckets.Length;
                int last = -1; // 用于标识该链表的上一个结点
                // entries[buckets[bucket]]头结点
                for (int i = buckets[bucket]; i >= 0; last = i, i = entries[i].next) {
                    if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) {
                        if (last < 0) { // 删除的是头结点
                            buckets[bucket] = entries[i].next;
                        }
                        else { // 链表中中间结点的删除
                            entries[last].next = entries[i].next;
                        }
                        entries[i].hashCode = -1;
                        entries[i].next = freeList;
                        entries[i].key = default(TKey);
                        entries[i].value = default(TValue);
                        freeList = i;
                        freeCount++;
                        version++;
                        return true;
                    }
                }
            }
            return false;
        }


字典元素的查找：根据键、值查找


按照键查找：时间复杂度O(1)，利用hash碰撞而不是遍历数组，时间较快

        public bool ContainsKey(TKey key) 
        {
            return FindEntry(key) >= 0;
        }

        private int FindEntry(TKey key) 
        {
            if( key == null) {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
            }
            if (buckets != null) {
                int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
                for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next) {
                    if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i;
                }
            }
            return -1;
        }


按照值查找：时间复杂度O(n)，需要遍历数组中的所有元素，时间较慢

        public bool ContainsValue(TValue value) 
        {
            if (value == null) {
                for (int i = 0; i < count; i++) {
                    if (entries[i].hashCode >= 0 && entries[i].value == null) return true;
                }
            }
            else {
                EqualityComparer<TValue> c = EqualityComparer<TValue>.Default;
                for (int i = 0; i < count; i++) {
                    if (entries[i].hashCode >= 0 && c.Equals(entries[i].value, value)) return true;
                }
            }
            return false;
        }

五、Dictionary与HashTable的区别

Dictionary支持泛型，HashTable不支持泛型
HashTable中的元素是Object类型，需要进行类型转换，耗时，在存储和检索值类型时会导致装箱与拆箱操作

        private struct bucket {
            public Object key;
            public Object val;
            public int hash_coll;   // Store hash code; sign bit means there was a collision.
        }


单线程中推荐使用Dictionary，支持泛型，但是是非线程安全的，在多线程中需要自己写lock保护语句，效率降低；HashTable则支持单线程写入，多线程读取，通过调用Synchronized()方法可以获取完全线程安全的类型
key是整型时Dictionary的效率要比HashTable高，而key是字符串时则HashTable的效率更高

基于.NET Framework 4.8

变量名字存哪去了? $a
符号表是什么?

答:符号表是一张哈希表,里面存储了变量名到变量的zval结构体的地址映射

// zend/zend_globals.h 182行
#哈希表  变量放到全局的符号表active_symbol_table
HashTable *active_symbol_table; #正在活动符号表 
HashTable symbol_table;		/* main symbol table */  全局

同时，全局符号表中，多了3条记录  都是指向

a  --> 0x123 —> 结构体(3)

b --> 0x21D --> 结构体(4.321)

c --> 0x3A0 --> 结构体(hello)
生成了3条件记录，相当于结构体生成3条记录，和符号表多了3条记录
php7后续会写

 文章首发：公众号 newbmiao
 Dig101: dig more, simplified more and know more
在golang中，map是一个不可或缺的存在。
它作为哈希表，简单易用，既能自动处理哈希碰撞，又能自动扩容或重新内存整理，避免读写性能的下降。
这些都要归功于其内部实现的精妙。本文尝试去通过源码去分析一下其背后的故事。
我们不会过多在源码分析上展开，只结合代码示例对其背后设计实现上做些总结，希望可以简单明了一些。
希望看完后，会让你对 map 的理解有一些帮助。网上也有很多不错的源码分析，会附到文末，感兴趣的同学自行查看下。
（本文分析基于 Mac 平台上go1.14beta1版本。长文预警 ... ）
我们先简单过下map实现hash表所用的数据结构，这样方便后边讨论。
文章目录
0x01 map 的内部结构
0x02 map 的 hash 方式
0x03 map 的扩容方式
0x04 map 的初始化
0x05 map 的读取
0x06 map 的赋值
0x07 map 的删除
0x08 map 的遍历
0x01 map的内部结构
在这里我们先弄清楚map实现的整体结构
map本质是hash表（hmap），指向一堆桶（buckets）用来承接数据，每个桶（bmap）能存8组k/v。
当有数据读写时，会用key的hash找到对应的桶。
为加速hash定位桶，bmap里记录了tophash数组（hash的高8位）
hash表就会有哈希冲突的问题（不同key的hash值一样，即hash后都指向同一个桶），为此map使用桶后链一个溢出桶（overflow）链表来解决当桶8个单元都满了，但还有数据需要存入此桶的问题。
剩下noverflow,oldbuckets,nevacuate,oldoverflow 会用于扩容，暂时先不展开
具体对应的数据结构详细注释如下：
（虽然多，先大致过一遍，后边遇到会在提到）
// runtime/map.go
// A header for a Go map.
type hmap struct {
  //用于len(map)
  count     int
  //标志位
  // iterator     = 1 // 可能有遍历用buckets
  // oldIterator  = 2 // 可能有遍历用oldbuckets，用于扩容期间
  // hashWriting  = 4 // 标记写，用于并发读写检测
  // sameSizeGrow = 8 // 用于等大小buckets扩容，减少overflow桶
  flags     uint8

  // 代表可以最多容纳loadFactor * 2^B个元素（loadFactor=6.5）
  B         uint8
  // overflow桶的计数，当其接近1<<15 - 1时为近似值
  noverflow uint16
  // 随机的hash种子，每个map不一样，减少哈希碰撞的几率
  hash0     uint32

  // 当前桶，长度为（0-2^B）
  buckets    unsafe.Pointer
  // 如果存在扩容会有扩容前的桶
  oldbuckets unsafe.Pointer
  // 迁移数，标识小于其的buckets已迁移完毕
  nevacuate  uintptr

  // 额外记录overflow桶信息，不一定每个map都有
  extra *mapextra
}

// 额外记录overflow桶信息
type mapextra struct {
  overflow    *[]*bmap
  oldoverflow *[]*bmap

  // 指向下一个可用overflow桶
  nextOverflow *bmap
}

const(
  // 每个桶8个k/v单元
  BUCKETSIZE  = 8
  // k或v类型大小大于128转为指针存储
  MAXKEYSIZE  = 128
  MAXELEMSIZE = 128
)

// 桶结构 （字段会根据key和elem类型动态生成，见下边bmap）
type bmap struct {
  // 记录桶内8个单元的高8位hash值，或标记空桶状态，用于快速定位key
  // emptyRest      = 0 // 此单元为空，且更高索引的单元也为空
  // emptyOne       = 1 // 此单元为空
  // evacuatedX     = 2 // 用于表示扩容迁移到新桶前半段区间
  // evacuatedY     = 3 // 用于表示扩容迁移到新桶后半段区间
  // evacuatedEmpty = 4 // 用于表示此单元已迁移
  // minTopHash     = 5 // 最小的空桶标记值，小于其则是空桶标志
  tophash [bucketCnt]uint8
}

// cmd/compile/internal/gc/reflect.go
// func bmap(t *types.Type) *types.Type {
// 每个桶内k/v单元数是8
type bmap struct{
  topbits [8]uint8 //tophash
  keys [8]keytype
  elems [8]elemtype
  // overflow 桶
  // otyp 类型为指针*Type,
  // 若keytype及elemtype不含指针，则为uintptr
  // 使bmap整体不含指针,避免gc去scan此类map
  overflow otyp
}
这里有几个字段需要解释一下：
hmap.B
这个为啥用2的对数来表示桶的数目呢？
这里是为了hash定位桶及扩容方便
比方说，hash%n可以定位桶， 但%操作没有位运算快。
而利用 n=2^B，则hash%n=hash&(n-1)
则可优化定位方式为: hash&(1<<B-1)， (1<<B-1)即源码中BucketMask
再比方扩容，hmap.B=hmap.B+1 即为扩容到二倍
bmap.keys, bmap.elems
在桶里存储k/v的方式不是一个k/v一组, 而是k放一块，v放一块。
这样的相对k/v相邻的好处是，方便内存对齐。比如map[int64]int8, v是int8,放一块就避免需要额外内存对齐。
另外对于大的k/v也做了优化。
正常情况key和elem直接使用用户声明的类型，但当其size大于128(MAXKEYSIZE/MAXELEMSIZE)时，
则会转为指针去存储。（也就是indirectkey、indirectelem）
hmap.extra
这个额外记录溢出桶意义在哪？
具体是为解决让gc不需要扫描此类bucket。
只要bmap内不含指针就不需gc扫描。
当map的key和elem类型都不包含指针时，但其中的overflow是指针。
此时bmap的生成函数会将overflow的类型转化为uintptr。
而uintptr虽然是地址，但不会被gc认为是指针，指向的数据有被回收的风险。
此时为保证其中的overflow指针指向的数据存活，就用mapextra结构指向了这些buckets，这样bmap有被引用就不会被回收了。
关于uintptr可能被回收的例子，可以看下 go101 - Type-Unsafe Pointers 中 Some Facts in Go We Should Know
0x02 map的hash方式
了解map的基本结构后，我们通过下边代码分析下map的hash
var m = map[interface{}]int{}
var i interface{} = []int{}
//panic: runtime error: hash of unhashable type []int
println(m[i])
//panic: runtime error: hash of unhashable type []int
delete(m, i)
为什么不可以用[]int作为key呢？
查找源码中hash的调用链注释如下：
// runtime/map.go
// mapassign，mapaccess1中 获取key的hash
hash := t.hasher(key, uintptr(h.hash0))

// cmd/compile/internal/gc/reflect.go
func dtypesym(t *types.Type) *obj.LSym {
  switch t.Etype {
    // ../../../../runtime/type.go:/mapType
  case TMAP:
    ...
    // 依据key构建hash函数
    hasher := genhash(t.Key())
    ...
  }
}

// cmd/compile/internal/gc/alg.go
func genhash(t *types.Type) *obj.LSym {
  switch algtype(t) {
  ...
  //具体针对interface调用interhash
  case AINTER:
    return sysClosure("interhash")
  ...
  }
}

// runtime/alg.go
func interhash(p unsafe.Pointer, h uintptr) uintptr {
  //获取interface p的实际类型t，此处为slice
  a := (*iface)(p)
  tab := a.tab
  t := tab._type
  // slice类型不可比较，没有equal函数
  if t.equal == nil {
    panic(errorString("hash of unhashable type " + t.string()))
  }
  ...
}
如上，我们会发现map的hash函数并不唯一。
它会对不同key类型选取不同的hash方式，以此加快hash效率
这个例子slice不可比较，所以不能作为key。
也对，不可比较的类型作为key的话，找到桶但没法比较key是否相等，那map用这个key读写都会是个问题。
还有哪些不可比较？
cmd/compile/internal/gc/alg.go的 algtype1 函数中可以找到返回ANOEQ（不可比较类型）的类型,如下：
func,map,slice
内部元素有这三种类型的array和struct类型
0x03 map的扩容方式
map不可以对其值取地址；
如果值类型为slice或struct，不能直接操作其内部元素
我们用代码验证如下：
m0 := map[int]int{}
// ❎ cannot take the address of m0[0]
_ = &m0[0]

m := make(map[int][2]int)
// ✅
m[0] = [2]int{1, 0}
// ❎ cannot assign to m[0][0]
m[0][0] = 1
// ❎ cannot take the address of m[0]
_ = &m[0]

type T struct{ v int }
ms := make(map[int]T)
// ✅
ms[0] = T{v: 1}
// ❎ cannot assign to struct field ms[0].v in map
ms[0].v = 1
// ❎ cannot take the address of ms[0]
_ = &ms[0]
}
为什么呢？
这是因为map内部有渐进式扩容，所以map的值地址不固定，取地址没有意义。
也因此，对于值类型为slice和struct, 只有把他们各自当做整体去赋值操作才是安全的。 go有个issue讨论过这个问题：issues-3117
针对扩容的方式，有两类，分别是：
sameSizeGrow
过多的overflow使用，使用等大小的buckets重新整理，回收多余的overflow桶，提高map读写效率，减少溢出桶占用
这里借助hmap.noverflow来判断溢出桶是否过多
hmap.B<=15 时，判断是溢出桶是否多于桶数1<<hmap.B
否则只判断溢出桶是否多于 1<<15
这也就是为啥hmap.noverflow，当其接近1<<15 - 1时为近似值, 只要可以评估是否溢出桶过多不合理就行了
biggerSizeGrow
count/size > 6.5 (装载因子 :overLoadFactor）, 避免读写效率降低。
扩容一倍，并渐进的在赋值和删除（mapassign和mapdelete）期间，
对每个桶重新分流到x（原来桶区间）和y（扩容后的增加的新桶区间）
这里overLoadFactor （count/size）是评估桶的平均装载数据能力，即map平均每个桶装载多少个k/v。
这个值太大，则桶不够用，会有太多溢出桶；太小，则分配了太多桶，浪费了空间。
6.5是测试后对map装载能力最大化的一个的选择。
源码中扩容代码注释如下：
// mapassign 中创建新bucket时检测是否需要扩容
if !h.growing() && //非扩容中
  (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
  // 提交扩容，生成新桶，记录旧桶相关。但不开始
  // 具体开始是后续赋值和删除期间渐进进行
  hashGrow(t, h)
}

//mapassign 或 mapdelete中 渐进扩容
bucket := hash & bucketMask(h.B)
if h.growing() {
  growWork(t, h, bucket)
}

// 具体迁移工作执行，每次最多两个桶
func growWork(t *maptype, h *hmap, bucket uintptr) {
  // 迁移对应旧桶
  // 若无迭代器遍历旧桶，可释放对应的overflow桶或k/v
  // 全部迁移完则释放整个旧桶
  evacuate(t, h, bucket&h.oldbucketmask())

  // 如果还有旧桶待迁移，再迁移一个
  if h.growing() {
    evacuate(t, h, h.nevacuate)
  }
}
具体扩容evacuate（迁移）时，判断是否要将旧桶迁移到新桶后半区间（y）有段代码比较有趣, 注释如下：
newbit := h.noldbuckets()
var useY uint8
if !h.sameSizeGrow() {
  // 获取hash
  hash := t.hasher(k2, uintptr(h.hash0))
  if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equal(k2, k2) {
  // 这里 key != key 是指key为NaNs，
  // 此时 useY = top & 1 意味着有50%的几率到新桶区间
    useY = top & 1
    top = tophash(hash)
  } else {
    if hash&newbit != 0 {
  // 举例来看 若扩容前h.B=3时, newbit=1<<3
  // hash&newbit != 0 则hash形如 xxx1xxx
  // 新hmap的BucketMask= 1<<4 - 1 (1111: 15)
  // 则 hash&新BucketMask > 原BucketMask 1<<3-1 (111: 7)
  // 所以去新桶区间
      useY = 1
    }
  }
}

// 补充一个 key != key 的代码示例
n1, n2 := math.NaN(), math.NaN()
m := map[float64]int{}
m[n1], m[n2] = 1, 2
println(n1 == n2, m[n1], m[n2])
// output: false 0 0
// 所以NaN做key没有意义。。。
弄清楚map的结构、hash和扩容，剩下的就是初始化、读写、删除和遍历了，我们就不详细展开了，简单过下。
0x04 map的初始化
map不初始化时为nil，是不可以操作的。可以通过make方式初始化
// 不指定大小
s := make(map[int]int)
// 指定大小
b := make(map[int]int,10)
对于这两种map内部调用方式是不一样的
small map
当不指定大小或者指定大小不大于8时，调用
func makemap_small() *hmap {
只需要直接在堆上初始化hmap和hash种子（hash0）就行。
bigger map
当大小大于8， 调用
func makemap(t *maptype, hint int, h *hmap) *hmap {
hint溢出则置0
初始化hmap和hash种子
根据overLoadFactor:6.5的要求, 循环增加h.B， 获取 hint/(1<<h.B) 最接近 6.5的h.B
预分配hashtable的bucket数组
h.B 大于4的话，多分配至少1<<(h.B-4)（需要内存对齐）个bucket，用于可能的overflow桶使用，
并将 h.nextOverflow设置为第一个可用的overflow桶。
最后一个overflow桶指向h.buckets(方便后续判断已无overflow桶)
0x05 map的读取
对于map的读取有着三个函数，主要区别是返回参数不同
mapaccess1: m[k]
mapaccess2: a,b = m[i]
mapaccessk: 在map遍历时若grow已发生，key可能有更新，需用此函数重新获取k/v
计算key的hash,定位当前buckets里桶位置
如果当前处于扩容中，也尝试去旧桶取对应的桶，需考虑扩容前bucket大小是否为现在一半，且其所指向的桶未迁移
然后就是按照bucket->overflow链表的顺序去遍历，直至找到tophash匹配且key相等的记录（entry）
期间，如果key或者elem是转过指针（size大于128），需转回对应值。
map为空或无值返回elem类型的零值
0x06 map的赋值
计算key的hash，拿到对应的桶
如果此时处于扩容期间，则执行扩容growWork
对桶bucket->overflow链表遍历
 若有空桶(对应tophash[i]为空)，则准备在此空桶存储k/v
 若非空，且和tophash相等，且key相等，则更新对应elem
 若无可用桶，则分配一个新的overflow桶来存储k/v, 会判断是否需要扩容
最后若使用了空桶或新overflow桶，则要将对应tophash更新回去, 如果需要的话，也更新count
0x07 map的删除
获取待删除key对应的桶，方式和mapassign的查找方式基本一样，找到则清除k/v。
这里还有个额外操作：
如果当前tophash状态是：当前cell为空（emptyOne），
若其后桶或其后的overflow桶状态为：当前cell为空前索引高于此cell的也为空（emptyRest）,则将当前状态也更新为emptyRest
倒着依次往前如此处理，实现 emptyOne -> emptyRest的转化
这样有什么好处呢？
答案是为了方便读写删除（mapaccess,mapassign,mapdelete）时做桶遍历（bucketLoop）能减少不必要的空bucket遍历
截取代码如下：
bucketloop:
  for ; b != nil; b = b.overflow(t) {
    for i := uintptr(0); i < bucketCnt; i++ {
      if b.tophash[i] != top {
        // 减少空cell的遍历
        if b.tophash[i] == emptyRest {
          break bucketloop
        }
        continue
      }
    ...
  }
0x08 map的遍历
先调用mapiterinit 初始化用于遍历的 hiter结构体, 这里会用随机定位出一个起始遍历的桶hiter.startBucket, 这也就是为啥map遍历无序。
随机获取起始桶的代码如下：
r := uintptr(fastrand())
// 随机数不够用得再加一个32位
if h.B > 31-bucketCntBits {
  r += uintptr(fastrand()) << 31
}
it.startBucket = r & bucketMask(h.B)
在调用mapiternext去实现遍历, 遍历中如果处于扩容期间，如果当前桶已经迁移了，那么就指向新桶，没有迁移就指向旧桶
至此，map的内部实现我们就过完了。
里边有很多优化点，设计比较巧妙，简单总结一下：
以2的对数存储桶数，便于优化hash模运算定位桶，也利于扩容计算
每个map都随机hash种子，减少哈希碰撞的几率
map以key的类型确定hash函数，对不同类型针对性优化hash计算方式
桶内部k/v并列存储，减少不必要的内存对齐浪费；对于大的k/v也会转为指针，便于内存对齐和控制桶的整体大小
桶内增加tophash数组加快单元定位，也方便单元回收（空桶）标记
当桶8个单元都满了，还存在哈希冲突的k/v，则在桶里增加overflow桶链表存储
桶内若只有overflow桶链表是指针，则overflow类型转为uintptr，并使用mapextra引用该桶，避免桶的gc扫描又保证其overflow桶存活
写操作增加新桶时如果需要扩容，只记录提交，具体执行会分散到写操作和删除操作中渐进进行，将迁移成本打散
哈希表的装载因子不满足要求是，扩容一倍，保证桶的装载能力
哈希表overflow桶过多，则内存重新整理，减少不必要的overflow桶，提升读写效率
对指定不同大小的map初始化，区别对待，不必要的桶预分配就避免；桶较多的情况下，也增加overflow桶的预分配
每次遍历起始位置随机，严格保证map无序语义
使用flags位标记检测map的并发读写，发现时panic，一定程度上预防数据不一致发生
趁热打铁，建议你再阅读一遍源码，加深一下理解。
附上几篇不错的源码分析文章，代码对应的go版本和本文不一致，但变化不大，可以对照着看。
cch123 - map
理解 Golang 哈希表 Map 的原理
SVz - go-源码研读-map
本文代码见  NewbMiao/Dig101-Go