Memcache源码阅读（5）---哈希表管理

傷城~ 2022-07-13 01:24 481阅读 0赞

我看的源码版本是1.2.4

memcached使用的哈希函数是用Dr Dobbs的Hash方法，哈希函数的原理我就不说了，它可以将一个k个字节的数据通过转换，变为一个32位的二进制数。它有那样的特性，这k个字节的二进制稍微有一点变动，得到的32为二进制数就会有很大区别。这也就是哈希函数的作用。

虽然说他哈希之后是32位，也就是可以分为2^32这么多个哈希桶，如果我们不需要这么大的哈希桶，可以对得到这32位的哈希值进行掩码处理。比如说我只需要将数据分到2^8这么多个哈希桶，那么我用0x000000FF & hash(data)就可以了。

### 哈希表的初始化 ###

#define hashsize(n) ((ub4)1<<(n))  // 2^n
    #define hashmask(n) (hashsize(n)-1)
    
    //只是简单的分配内存，primary_hashtable就是我们的哈希表
    void assoc_init(void) {
        unsigned int hash_size = hashsize(hashpower) * sizeof(void*);
        primary_hashtable = malloc(hash_size);
        memset(primary_hashtable, 0, hash_size);
    }

### 哈希表的插入 ###

这里的冲突处理是采用拉链法,下面的代码省略了哈希表增容的内容，哈希表增容是当哈希表存储的元素多于哈希表大小的1.5倍时，就对哈希表进行增容。因为此时取元素的效率会大大降低，只有增大哈希表的容量才能提高效率。

//求得哈希值，往哈希表对应的位置插入数据。
    int assoc_insert(item *it) {
        uint32_t hv;
    
        hv = hash(ITEM_key(it), it->nkey, 0);
        it->h_next = primary_hashtable[hv & hashmask(hashpower)];
        primary_hashtable[hv & hashmask(hashpower)] = it;
        hash_items++;
        return 1;
    }

### 哈希表的增容 ###

增容就是新创建一个哈希表，然后将就的哈希表遍历一遍，将数据重新哈希一次填到新的哈希表中。当然，这个重新哈希一次肯定得花一段时间，那么在转移的过程中，新的数据可不可以插入呢，答案是肯定的。

`expand_bucket`这个变量很关键。`expand_bucket`这个变量就是遍历一次就哈希表。在增容的时候插入数据的时候会判断得到的旧哈希表的值是否大于expand\_bucket，如果大于就说明重新哈希还没到那里，可以插入到旧哈希表中，否则就可以插入到新的哈希表中。如果少了这个判断，增容的途中直接将数据插入到新表中，那么哈希表扩容这个操作需要一段比较长的时间，在扩容分配内存的时候插入数据，整个程序就崩溃了。有了这个判断，扩容分配内存的时候，数据是插入到旧表中的。

后面我发现这个我先前的想法是错的。这个expand\_bucket是在我们调用assoc\_find的时候有用的，没有转移的，就可以到旧表找，转移之后的就到新表找。上面我提到到的那个问题根本不存在。对于primary\_hashtable这个变量存在两种情况，未初始化好新内存，初始化好新内存。未初始化好新内存，primary\_hashtable一直指向旧表，插入数据没问题。初始化好新内存，它就指向新表，插入数据仍然没问题。根本不存在那个正在初始化，然后插入到新表的问题。

int assoc_insert(item *it) {
        uint32_t hv;
        unsigned int oldbucket;
    
        hv = hash(ITEM_key(it), it->nkey, 0);
        //这里到底有什么用呢？？？？？？？
        if (expanding &&
            (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++;
        //哈希表存储的元素多于哈希表大小的1.5倍时,哈希表增容
        if (! expanding && hash_items > (hashsize(hashpower) * 3) / 2) {
            assoc_expand();
        }
    
        return 1;
    }
    
    static void assoc_expand(void) {
        old_hashtable = primary_hashtable;
    
        primary_hashtable = calloc(hashsize(hashpower + 1), sizeof(void *));
        if (primary_hashtable) {
            if (settings.verbose > 1)
                fprintf(stderr, "Hash table expansion starting\n");
            hashpower++;
            expanding = true;
            expand_bucket = 0;
            do_assoc_move_next_bucket();
        } else {
            primary_hashtable = old_hashtable;
            /* Bad news, but we can keep running. */
        }
    }
    
    void do_assoc_move_next_bucket(void) {
        item *it, *next;
        int bucket;
    
        if (expanding) {
                //哈希表中一项的链表遍历
            for (it = old_hashtable[expand_bucket]; NULL != it; it = next) {
                next = it->h_next;
    
                bucket = hash(ITEM_key(it), it->nkey, 0) & hashmask(hashpower);
                it->h_next = primary_hashtable[bucket];
                primary_hashtable[bucket] = it;
            }
    
            old_hashtable[expand_bucket] = NULL;
            //哈希表中的下一个
            expand_bucket++;
            if (expand_bucket == hashsize(hashpower - 1)) {
                expanding = false;
                free(old_hashtable);
                if (settings.verbose > 1)
                    fprintf(stderr, "Hash table expansion done\n");
            }
        }
    }

### 哈希查找 ###

这个很简单，就是找到key对应的位置之后，搜一下那里所有的项的key，返回相等的那一个。

### 哈希删除 ###

寻找删除item前一项那里我觉得很有意思，画了个图来解释。

![memcached\_assoc\_delete][memcached_assoc_delete]

void assoc_delete(const char *key, const size_t nkey) {
        //*before是指向当前这个key的item，但是before是指向这个item的前一项的h_next。
        item **before = _hashitem_before(key, nkey);
    
        if (*before) {
            item *nxt = (*before)->h_next;
            (*before)->h_next = 0;   /* probably pointless, but whatever. */
            *before = nxt;
            hash_items--;
            return;
        }
        /* Note:  we never actually get here.  the callers don't delete things
           they can't find. */
        assert(*before != 0);
    
    }
    
    
    static item** _hashitem_before (const char *key, const size_t nkey) {
        uint32_t hv = hash(key, nkey, 0);
        item **pos;
        unsigned int oldbucket;
    
        while (*pos && ((nkey != (*pos)->nkey) || memcmp(key, ITEM_key(*pos), nkey))) {
            //这个很关键！！
            pos = &(*pos)->h_next;
        }
        return pos;
    }

[memcached_assoc_delete]: http://7xqdjj.com1.z0.glb.clouddn.com/memcached_assoc_delete.png