Redis系列(九):数据结构Hash之HDEL、HEXISTS、HGETALL、HKEYS、HLEN、HVALS命令
阅读原文时间:2023年07月12日阅读:1

从 key 指定的哈希集中移除指定的域。在哈希集中不存在的域将被忽略。

如果 key 指定的哈希集不存在,它将被认为是一个空的哈希集,该命令将返回0。

时间复杂度:O(N) N是被删除的字段数量

127.0.0.1:> hset myhash field1 "foo"
(integer)
127.0.0.1:> hdel myhash field1
(integer)
127.0.0.1:>

源码解析

// t_hash.c,
void hdelCommand(client *c) {
robj *o;
int j, deleted = , keyremoved = ;

if ((o = lookupKeyWriteOrReply(c,c->argv\[\],shared.czero)) == NULL ||  
    checkType(c,o,OBJ\_HASH)) return;  
// 循环删除给定字段列表  
for (j = ; j < c->argc; j++) {  
    if (hashTypeDelete(o,c->argv\[j\]->ptr)) {  
        deleted++;  
        // 当没有任何元素后,直接将key删除  
        if (hashTypeLength(o) == ) {  
            dbDelete(c->db,c->argv\[\]);  
            keyremoved = ;  
            break;  
        }  
    }  
}  
if (deleted) {  
    signalModifiedKey(c->db,c->argv\[\]);  
    notifyKeyspaceEvent(NOTIFY\_HASH,"hdel",c->argv\[\],c->db->id);  
    if (keyremoved)  
        notifyKeyspaceEvent(NOTIFY\_GENERIC,"del",c->argv\[\],  
                            c->db->id);  
    server.dirty += deleted;  
}  
addReplyLongLong(c,deleted);  

}
// 具体删除 field, 同样区分编码类型,不同处理逻辑
/* Delete an element from a hash.
* Return 1 on deleted and 0 on not found. */
int hashTypeDelete(robj *o, sds field) {
int deleted = ;

if (o->encoding == OBJ\_ENCODING\_ZIPLIST) {  
    unsigned char \*zl, \*fptr;

    zl = o->ptr;  
    fptr = ziplistIndex(zl, ZIPLIST\_HEAD);  
    if (fptr != NULL) {  
        // ziplist 删除,依次删除 field, value  
        fptr = ziplistFind(fptr, (unsigned char\*)field, sdslen(field), );  
        if (fptr != NULL) {  
            // ziplistDelete 为原地删除,所以只要调用2次,即把kv删除  
            zl = ziplistDelete(zl,&fptr);  
            zl = ziplistDelete(zl,&fptr);  
            o->ptr = zl;  
            deleted = ;  
        }  
    }  
} else if (o->encoding == OBJ\_ENCODING\_HT) {  
    if (dictDelete((dict\*)o->ptr, field) == C\_OK) {  
        deleted = ;

        /\* Always check if the dictionary needs a resize after a delete. \*/  
        // hash 删除的,可能需要进行缩容操作,这种处理方法相对特殊些  
        if (htNeedsResize(o->ptr)) dictResize(o->ptr);  
    }

} else {  
    serverPanic("Unknown hash encoding");  
}  
return deleted;  

}
// server.c, 是否需要进行 resize
int htNeedsResize(dict *dict) {
long long size, used;

size = dictSlots(dict);  
used = dictSize(dict);  
// HASHTABLE\_MIN\_FILL=10, 即使用率小于 1/10 时,可以进行缩容操作了  
return (size && used && size > DICT\_HT\_INITIAL\_SIZE &&  
        (used\*/size < HASHTABLE\_MIN\_FILL));  

}

返回hash里面field是否存在

时间复杂度:O(1)

127.0.0.1:> hset myhash field1 "foo"
(integer)
127.0.0.1:> hexists myhash field1
(integer)
127.0.0.1:> hexists myhash field2
(integer)
127.0.0.1:>

源码解析

void hexistsCommand(client *c) {
robj *o;
if ((o = lookupKeyReadOrReply(c,c->argv[],shared.czero)) == NULL ||
checkType(c,o,OBJ_HASH)) return;

addReply(c, hashTypeExists(o,c->argv\[\]->ptr) ? shared.cone : shared.czero);  

}

hashTypeExists

int hashTypeExists(robj *o, sds field) {
if (o->encoding == OBJ_ENCODING_ZIPLIST) {
unsigned char *vstr = NULL;
unsigned int vlen = UINT_MAX;
long long vll = LLONG_MAX;

    if (hashTypeGetFromZiplist(o, field, &vstr, &vlen, &vll) == ) return ;  
} else if (o->encoding == OBJ\_ENCODING\_HT) {  
    if (hashTypeGetFromHashTable(o, field) != NULL) return ;  
} else {  
    serverPanic("Unknown hash encoding");  
}  
return ;  

}

ziplist的类型判断

/* Get the value from a ziplist encoded hash, identified by field.
* Returns -1 when the field cannot be found. */
int hashTypeGetFromZiplist(robj *o, sds field,
unsigned char **vstr,
unsigned int *vlen,
long long *vll)
{
unsigned char *zl, *fptr = NULL, *vptr = NULL;
int ret;

serverAssert(o->encoding == OBJ\_ENCODING\_ZIPLIST);

zl = o->ptr;  
fptr = ziplistIndex(zl, ZIPLIST\_HEAD);  
if (fptr != NULL) {  
    fptr = ziplistFind(fptr, (unsigned char\*)field, sdslen(field), );  
    if (fptr != NULL) {  
        /\* Grab pointer to the value (fptr points to the field) \*/  
        vptr = ziplistNext(zl, fptr);  
        serverAssert(vptr != NULL);  
    }  
}

if (vptr != NULL) {  
    ret = ziplistGet(vptr, vstr, vlen, vll);  
    serverAssert(ret);  
    return ;  
}

return -;  

}

ziplistFind

/* Find pointer to the entry equal to the specified entry. Skip 'skip' entries
* between every comparison. Returns NULL when the field could not be found. */
unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip) {
int skipcnt = ;
unsigned char vencoding = ;
long long vll = ;

while (p\[\] != ZIP\_END) {  
    unsigned int prevlensize, encoding, lensize, len;  
    unsigned char \*q;

    ZIP\_DECODE\_PREVLENSIZE(p, prevlensize);  
    ZIP\_DECODE\_LENGTH(p + prevlensize, encoding, lensize, len);  
    q = p + prevlensize + lensize;

    if (skipcnt == ) {  
        /\* Compare current entry with specified entry \*/  
        if (ZIP\_IS\_STR(encoding)) {  
            if (len == vlen && memcmp(q, vstr, vlen) == ) {  
                return p;  
            }  
        } else {  
            /\* Find out if the searched field can be encoded. Note that  
             \* we do it only the first time, once done vencoding is set  
             \* to non-zero and vll is set to the integer value. \*/  
            if (vencoding == ) {  
                if (!zipTryEncoding(vstr, vlen, &vll, &vencoding)) {  
                    /\* If the entry can't be encoded we set it to  
                     \* UCHAR\_MAX so that we don't retry again the next  
                     \* time. \*/  
                    vencoding = UCHAR\_MAX;  
                }  
                /\* Must be non-zero by now \*/  
                assert(vencoding);  
            }

            /\* Compare current entry with specified entry, do it only  
             \* if vencoding != UCHAR\_MAX because if there is no encoding  
             \* possible for the field it can't be a valid integer. \*/  
            if (vencoding != UCHAR\_MAX) {  
                long long ll = zipLoadInteger(q, encoding);  
                if (ll == vll) {  
                    return p;  
                }  
            }  
        }

        /\* Reset skip count \*/  
        skipcnt = skip;  
    } else {  
        /\* Skip entry \*/  
        skipcnt--;  
    }

    /\* Move to next entry \*/  
    p = q + len;  
}

return NULL;  

}

hashtable类型的

/* Get the value from a hash table encoded hash, identified by field.
* Returns NULL when the field cannot be found, otherwise the SDS value
* is returned. */
sds hashTypeGetFromHashTable(robj *o, sds field) {
dictEntry *de;

serverAssert(o->encoding == OBJ\_ENCODING\_HT);

de = dictFind(o->ptr, field);  
if (de == NULL) return NULL;  
return dictGetVal(de);  

}

dictFInd

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

if (dictSize(d) == ) return NULL; /\* dict is empty \*/  
if (dictIsRehashing(d)) \_dictRehashStep(d);  
h = dictHashKey(d, key);  
for (table = ; table <= ; table++) {  
    idx = h & d->ht\[table\].sizemask;  
    he = d->ht\[table\].table\[idx\];  
    while(he) {  
        if (key==he->key || dictCompareKeys(d, key, he->key))  
            return he;  
        he = he->next;  
    }  
    if (!dictIsRehashing(d)) return NULL;  
}  
return NULL;  

}

HGetAll:返回 key 指定的哈希集中所有的字段和值。返回值中,每个字段名的下一个是它的值,所以返回值的长度是哈希集大小的两倍

时间复杂度:O(N)

HKeys:返回 key 指定的哈希集中所有字段的名字。

时间复杂度:O(N)

HVals:返回 key 指定的哈希集中所有字段的值。

时间复杂度:O(N)

127.0.0.1:> hset myhash field1 "Hello"
(integer)
127.0.0.1:> hset myhash field2 "World"
(integer)
127.0.0.1:> hkeys myhash
) "field1"
) "field2"
127.0.0.1:> hgetall myhash
) "field1"
) "Hello"
) "field2"
) "World"
127.0.0.1:> hvals myhash
) "Hello"
) "World"
127.0.0.1:>

源码解析

void hkeysCommand(client *c) {
genericHgetallCommand(c,OBJ_HASH_KEY);
}

void hvalsCommand(client *c) {
genericHgetallCommand(c,OBJ_HASH_VALUE);
}

void hgetallCommand(client *c) {
genericHgetallCommand(c,OBJ_HASH_KEY|OBJ_HASH_VALUE);
}

void genericHgetallCommand(client *c, int flags) {
robj *o;
hashTypeIterator *hi;
int length, count = ;

if ((o = lookupKeyReadOrReply(c,c->argv\[\],shared.emptymap\[c->resp\]))  
    == NULL || checkType(c,o,OBJ\_HASH)) return;

/\* We return a map if the user requested keys and values, like in the  
 \* HGETALL case. Otherwise to use a flat array makes more sense. \*/  
length = hashTypeLength(o);  
if (flags & OBJ\_HASH\_KEY && flags & OBJ\_HASH\_VALUE) {  
    addReplyMapLen(c, length);  
} else {  
    addReplyArrayLen(c, length);  
}

hi = hashTypeInitIterator(o);  
while (hashTypeNext(hi) != C\_ERR) {  
    if (flags & OBJ\_HASH\_KEY) {  
        addHashIteratorCursorToReply(c, hi, OBJ\_HASH\_KEY);  
        count++;  
    }  
    if (flags & OBJ\_HASH\_VALUE) {  
        addHashIteratorCursorToReply(c, hi, OBJ\_HASH\_VALUE);  
        count++;  
    }  
}

hashTypeReleaseIterator(hi);

/\* Make sure we returned the right number of elements. \*/  
if (flags & OBJ\_HASH\_KEY && flags & OBJ\_HASH\_VALUE) count /= ;  
serverAssert(count == length);  

}

返回 key 指定的哈希集包含的字段的数量。

时间复杂度:O(1)

127.0.0.1:> hlen myhash
(integer)
127.0.0.1:>

void hlenCommand(client *c) {
robj *o;

if ((o = lookupKeyReadOrReply(c,c->argv\[\],shared.czero)) == NULL ||  
    checkType(c,o,OBJ\_HASH)) return;

addReplyLongLong(c,hashTypeLength(o));  

}

/* Return the number of elements in a hash. */
unsigned long hashTypeLength(const robj *o) {
unsigned long length = ULONG_MAX;

if (o->encoding == OBJ\_ENCODING\_ZIPLIST) {  
    length = ziplistLen(o->ptr) / ;  
} else if (o->encoding == OBJ\_ENCODING\_HT) {  
    length = dictSize((const dict\*)o->ptr);  
} else {  
    serverPanic("Unknown hash encoding");  
}  
return length;  

}