精华内容
下载资源
问答
  • 转载请注明出处:  温馨提示:本文用到了一些可以在启动memcached设置的全局变量。关于这些全局变量的含义可以参考... assoc.c文件里面的代码构造一个哈希表。memcached快的一个原因使用了哈希表。现在就


            转载请注明出处: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对应的桶有没有被迁移到新表上了。





    展开全文
  • 一、全局变量: // 字典中数据的基本存储单元、条目,可以认为一个链表的结点 private struct Entry { public int hashCode; // 哈希码,Lower 31 bits of hash code, -1 if unused public int next; // 同一...

    今天来学习一下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=49%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方法
    1. 容量不足时扩容,调用HashTableExpandPrime方法先扩大容量为原来的2倍,再取最小质数
    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;
            }
    
    • 字典元素的查找:根据键、值查找
    1. 按照键查找:时间复杂度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;
            }
    
    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;
            }
    

    五、DictionaryHashTable的区别

    1. Dictionary支持泛型,HashTable不支持泛型
    2. 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.
            }
    
    1. 单线程中推荐使用Dictionary,支持泛型,但是是非线程安全的,在多线程中需要自己写lock保护语句,效率降低;HashTable则支持单线程写入,多线程读取,通过调用Synchronized()方法可以获取完全线程安全的类型
    2. key是整型时Dictionary的效率要比HashTable高,而key是字符串时则HashTable的效率更高

    基于.NET Framework 4.8

    展开全文
  • 答:符号表是一张哈希表,里面存储了变量名到变量的zval结构体的地址映射 // zend/zend_globals.h 182行 #哈希表 变量放到全局的符号表active_symbol_table HashTable *active_symbol_table; #正在活动符号表 ...

    变量名字存哪去了? $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后续会写

    展开全文
  • 它作为哈希表,简单易用,既能自动处理哈希碰撞,又能自动扩容或重新内存整理,避免读写性能的下降。这些都要归功于其内部实现的精妙。本文尝试去通过源码去分析一下其背后的故事。我们不会过多在源码分析上展开,只...

    725981ff64cd5478569457ad7a1a3e6e.png
    文章首发:公众号 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的内部结构

    f401a06d93d4e72ccfc8827afc5af58d.png

    在这里我们先弄清楚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扫描。

    mapkeyelem类型都不包含指针时,但其中的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.goalgtype1 函数中可以找到返回ANOEQ(不可比较类型)的类型,如下:

    • func,map,slice
    • 内部元素有这三种类型的array和struct类型

    0x03 map的扩容方式

    map不可以对其值取地址;

    如果值类型为slicestruct,不能直接操作其内部元素

    我们用代码验证如下:

    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的值地址不固定,取地址没有意义。

    也因此,对于值类型为slicestruct, 只有把他们各自当做整体去赋值操作才是安全的。 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

    9b0c7ea874d2fc49838216d889a4de1c.png
    欢迎关注我,不定期深挖技术
    展开全文
  • 所有全局变量放在一张主符号表中(也就是数组$GLOBALS对应的哈希表)。PHP语言有个特性,变量在命名时,$变量标识符后不能以数字开头。例如我们在以下代码: <?php $111= "nowamagic"; ?> 会报如下错误:...
  • 39-诡异的变量

    2016-04-25 12:28:10
    所有全局变量放在一张主符号表中(也就是数组GLOBALS对应的哈希表)。PHP语言有个特性,变量在命名时,GLOBALS对应的哈希表)。PHP语言有个特性,变量在命名时,变量标识符后不能以数字开头。例如我们在以下代码: $111...
  • 全局对象

    2019-07-03 11:28:00
    待补充 待补充 待补充.......... ...window 就是一个哈希表,有很多属性。 window 的属性就是全局变量全局变量分为两种: 一种 ECMAScript 规定的 global.parseInt global.parseFloa...
  • 神秘的变量名特性

    2010-07-20 16:32:00
    所有全局变量放在一张主符号表中(也就是数组$GLOBALS对应的哈希表)。PHP语言有个特性,变量在命名时,$变量标识符后不能以数字开头。例如我们在以下代码: <?php $111= "my"; ?> 会报如下错误:Parse erro.....
  • 所有全局变量放在一张主符号表中(也就是数组$GLOBALS对应的哈希表)。PHP语言有个特性,变量在命名时,$变量标识符后不能以数字开头。例如我们在以下代码: $111= "my"; ?> 会报如下错误:Parse error: ...
  • Lua和C如何交互(一)

    2018-01-18 08:44:30
    要理解Lua和C的交互,先要理解堆栈和全局表两个概念 堆栈 ...Lua和C/C++语言交互的主要方法一个无处不在的虚拟栈,栈的特点先进后出....Lua的全局表可以想象成一个map哈希表结构,比如Lua有一个变量: name
  • 彻底弄懂原型链

    2019-06-26 16:07:32
    window 就是一个哈希表,有很多属性。 window 的属性就是全局变量。 这些全局变量分为两种: 一种 ECMAScript 规定的 • global.parseInt • global.parseFloat • global.Number • glo...
  • JS里的对象

    2017-12-22 02:46:39
    全局对象 window ...window 就是一个哈希表,有很多属性,这些属性就是全局变量全局变量分为两种: 一种 ECMAScript 规定的: global.parseInt global.parseFloat global.Number global.St...
  • 原型与原型链

    2019-06-13 13:52:15
    ECMAScript 规定全局对象叫做 global,但是浏览器把 window 作为全局对象(浏览器先存在的),window 就是一个哈希表,有很多属性。 window 的属性就是全局变量。这些全局变量分为两种: 一种 ECMAScript 规定的...
  • 全局对象 window ...window 就是一个哈希表,有很多属性。 window 的属性就是全局变量。 这些全局变量分为两种: 一种 ECMAScript 规定的  global.parseInt  global.parseFloat  glob...
  • 首先我们要知道浏览器中有哪些全局对象...window 就是一个哈希表,有很多属性。 window 的属性就是全局变量。 这些全局变量分为两种: 1、CEMAScript规定的 global.parseInt global.parseFloat global.Numbe...
  • 2.为什么在旧哈希表中,元素会越来越稀疏。 3.有关异常的困扰 4.关于多态和全局变量的修改 1.列表和元组的内部实现 答:它和list相似,本质也一个array,但是空间大小固定,不同于一般array,python的tuple做了...
  • 3、了解哈希表吗? 根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。 4、...
  • iOS面试之内存管理

    2020-12-24 13:23:07
    内存布局 iOS程序下内存布局 不同内存布局区域的含义 stack(栈):方法调用 heap(堆):通过alloc等分配的对象 bss:未初始化的全局变量 ...SideTables()(非嵌入式系统中包含64个SideTable),实际一个哈希表
  • ThreadLocalMap 原理

    2018-06-22 00:43:21
    https://www.jianshu.com/p/27e309e1d0f5总结:哈希表本质就是一个数组ThreadLocal 使用的Thread 对象的全局变量数据结构为: 数组 Entry[]entry 本质一个Threadlocal的弱引用 当发生gc时一定清楚...
  • C++ 面试题演练

    2019-08-21 16:39:18
    修饰局部变量,修饰全局变量,修饰函数,修饰成员函数2.函数指针 指向函数的指针3.引用和指针 引用别名,指针指向一个地址4.new和malloc的区别 new和运算符,malloc函数5.堆和栈的区别 栈存放局部变量和...
  • php常见面试题

    2018-03-12 19:53:04
    1.哈希冲突解决办法 链地址法(拉链法) :value设置成...静态变量本身就是静态存储方式, 全局变量,局部变量不是 静态存储方式指在程序运行期间分配固定的存储空间,静态存储变量通常在变量定义时就分定
  • 一面(1小时50分钟) ...8.int类型全局变量读、写、自增哪些原子性的 9.volatile的作用 10.stl容器是否线程安全 11.讲一下哈希表的底层细节,让你设计一个线程安全的哈希表,会怎么设计 12.malloc()的底层细节,brk
  • static 和 普通的全局变量有什么不同。它在类里面又有什么特点 malloc和new的区别 malloc分配的物理内存吗 C++程序有哪几个段 可以只有堆没有栈吗 为啥要有页表,直接查物理内存它不快吗 vector内存咋分配的 ...
  • 让Lua和C++牵手

    2014-03-26 11:10:50
    1. Lua的堆栈和全局表 我们来简单解释一下Lua的堆栈和全局表,...可以想象成一个map哈希表结构,比如Lua有一个变量: name = “hello” 那么,全局表就存放了”name”和”hello”的对应关系,Lua可以通过name在

空空如也

空空如也

1 2 3 4
收藏数 70
精华内容 28
关键字:

哈希表是全局变量