How to implement redis hash

0. Preface

redis is a KV type in-memory database. The core of database storage is the Hash table. After we execute the select command to select a stored db, all The operations are all based on the hash table. The hash data structure and implementation of redis will be analyzed below.

1.hash data structure

/*Hash表一个节点包含Key,Value数据对 */
typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; /* 指向下一个节点, 链接表的方式解决Hash冲突 */
} dictEntry;

/* 存储不同数据类型对应不同操作的回调函数 */
typedef struct dictType {
    unsigned int (*hashFunction)(const void *key);
    void *(*keyDup)(void *privdata, const void *key);
    void *(*valDup)(void *privdata, const void *obj);
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    void (*keyDestructor)(void *privdata, void *key);
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

typedef struct dictht {
    dictEntry **table; /* dictEntry*数组,Hash表 */
    unsigned long size; /* Hash表总大小 */
    unsigned long sizemask; /* 计算在table中索引的掩码, 值是size-1 */
    unsigned long used; /* Hash表已使用的大小 */
} dictht;

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2]; /* 两个hash表,rehash时使用*/
    long rehashidx; /* rehash的索引, -1表示没有进行rehash */
    int iterators; /*  */
} dict;

2.hash data structure diagram

3. Progressive hash description

There are two hash tables in ht[2] in dict. When we store the data for the first time, ht[0] A hash table with a minimum size of 4 will be created. Once size and used in ht[0] are equal, a hash table of size*2 will be created in dict in ht[1]. At this time, ht[ will not be directly used. The data in 0] is copied into ht[0], and progressive rehash is performed, that is, it is copied slowly in subsequent operations (find, set, get, etc.), and newly added elements will be added to ht[ in the future. 0], so when ht[1] is full, it will be sure that all the data in ht[0] are copied to ht[1].

4. Create a hash table

The process of creating a hash table is very simple. Just call the dictCreate function, allocate a piece of memory, and initialize intermediate variables.

dict *dictCreate(dictType *type, void *privDataPtr)
{
     /*分配内存*/
    dict *d = zmalloc(sizeof(*d));
     /*初始化操作*/
    _dictInit(d,type,privDataPtr);
    return d;
}

5. Add elements

To add elements to the hash table, first determine whether the space is Enough, then calculate the hash value corresponding to the key, and then put the key and value that need to be added into the table.

int dictAdd(dict *d, void *key, void *val)
{
     /*添加入hash表中, 返回新添加元素的实体结构体*/
    dictEntry *entry = dictAddRaw(d,key);

    if (!entry) return DICT_ERR;
     /*元素val值放入元素实体结构中*/
    dictSetVal(d, entry, val);
    return DICT_OK;
}
/*
*添加元素实体函数
*/
dictEntry *dictAddRaw(dict *d, void *key)
{
    int index;
    dictEntry *entry;
    dictht *ht;

    if (dictIsRehashing(d)) _dictRehashStep(d);

    /*根据key值计算新元素在hash表中的索引, 返回-1则表示元素已存在, 直接返回NULL*/
    if ((index = _dictKeyIndex(d, key)) == -1)
        return NULL;

    /*如果在进行rehash过程,则新元素添加到ht[1]中, 否则添加到ht[0]中 */
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    entry = zmalloc(sizeof(*entry));
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used++;

    /*设置元素key*/
    dictSetKey(d, entry, key);
    return entry;
}
/*
*计算索引的函数
*/
static int _dictKeyIndex(dict *d, const void *key)
{
    unsigned int h, idx, table;
    dictEntry *he;

    /* 判断hash表是否空间足够, 不足则需要扩展 */
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;
         
    /* 计算key对应的hash值 */
    h = dictHashKey(d, key);
    for (table = 0; table <= 1; table++) {
          /*计算索引*/
        idx = h & d->ht[table].sizemask;
        /*遍历冲突列表, 判断需要查找的key是否已经在冲突列表中*/
        he = d->ht[table].table[idx];
        while(he) {
            if (dictCompareKeys(d, key, he->key))
                return -1;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    return idx;
}
/*
*判断hash表是否需要扩展空间
*/
static int _dictExpandIfNeeded(dict *d)
{
    /*redis的rehash采用的渐进式hash, rehash时分配了原来两倍的内存空间, 在rehash阶段空间必定够用*/
    if (dictIsRehashing(d)) return DICT_OK;

    /* hash表是空的需要初始化空间, 默认是4*/
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

    /* 已使用空间满足不了设置的条件*/
    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
    {
          /*扩展空间, 使用空间的两倍*/
        return dictExpand(d, d->ht[0].used*2);
    }
    return DICT_OK;
}

/*
*扩展空间或者初始化hash表空间
*/
int dictExpand(dict *d, unsigned long size)
{
    dictht n;
     /* 对需要分配大小圆整为2的倍数 */
    unsigned long realsize = _dictNextPower(size);

    /* 如果空间足够则表明调用错误 */
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;

    n.size = realsize;
    n.sizemask = realsize-1;
    n.table = zcalloc(realsize*sizeof(dictEntry*));
    n.used = 0;
    
     /*hash表为空初始化hash表*/
    if (d->ht[0].table == NULL) {
        d->ht[0] = n;
        return DICT_OK;
    }

    /*新分配的空间放入ht[1], 后面一步一步进行rehash*/
    d->ht[1] = n;
    d->rehashidx = 0;
    return DICT_OK;
}

6. Find elements

The process of finding elements, first calculate the hash value, and then Calculate the index position in ht[0] and ht[1] and search.

dictEntry *dictFind(dict *d, const void *key)
{
    dictEntry *he;
    unsigned int h, idx, table;

    if (d->ht[0].size == 0) return NULL;
    
     /*如果正在进行rehash, 执行一次rehash*/
    if (dictIsRehashing(d)) _dictRehashStep(d);
    
    h = dictHashKey(d, key);
    
     /*由于可能正在rehash, 因此要从ht[0]和ht[1]中分别进行查找, 找不到返回NULL*/
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
          /*遍历冲突列表查找元素*/
        while(he) {
            if (dictCompareKeys(d, key, he->key))
                return he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) return NULL;
    }
    return NULL;
}

7. Delete elements

To delete an element, first search for the element, and then remove the element from the hash table That's it, calling dictDelete to delete an element will also delete the space occupied by the element

int dictDelete(dict *ht, const void *key) {
    return dictGenericDelete(ht,key,0);
}

static int dictGenericDelete(dict *d, const void *key, int nofree)
{
    unsigned int h, idx;
    dictEntry *he, *prevHe;
    int table;

    if (d->ht[0].size == 0) return DICT_ERR;
    
    if (dictIsRehashing(d)) _dictRehashStep(d);
    h = dictHashKey(d, key);

    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        prevHe = NULL;
          /*查找元素到元素,进行删除操作, 并释放占用的内存*/
        while(he) {
            if (dictCompareKeys(d, key, he->key)) {
                /* Unlink the element from the list */
                if (prevHe)
                    prevHe->next = he->next;
                else
                    d->ht[table].table[idx] = he->next;
                if (!nofree) {
                    dictFreeKey(d, he);
                    dictFreeVal(d, he);
                }
                zfree(he);
                d->ht[table].used--;
                return DICT_OK;
            }
            prevHe = he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    return DICT_ERR; /* not found */
}

hash command

The hash command operation is relatively simple. It should be noted that when we create a hash to represent the default storage structure, It is not a dict, but a ziplist structure. You can refer to the Ziplist data structure of redis. The hash_max_ziplist_entries and hash_max_ziplist_value values ​​are used as thresholds. hash_max_ziplist_entries means that once the number of elements in the ziplist exceeds this value, it needs to be converted to a dict structure; hash_max_ziplist_value Indicates that once the data length in the ziplist is greater than this value, it needs to be converted into a dict structure.

For more Redis-related technical articles, please visit the Redis Tutorial## column to learn!

The above is the detailed content of How to implement redis hash. For more information, please follow other related articles on the PHP Chinese website!