dict

The hash is implemented by the dict, but the dict is not only used in the hash, but also the expiration time, score, and value of the zset are implemented by the dict

The dict structure contains two hashtables inside, and usually only one hashtable has a value. However, when the dict is expanded or reduced, new Hashtables need to be allocated and then moved gradually. In this case, the two hashtables store the old hashtable and the new hashtable respectively. After the relocation is complete, the old hashtable is deleted and the new hashtable is replaced.

typedef struct dict{
    // Type specific functions
    dictType *type;
    // Private data
    void *privdata;
    / / a hash table
    dictht ht[2];
    / / rehash index
    // When rehash is not in progress, the value is -1
    int rehashidx;
} dict;

Copy the code

The Type and privData attributes are set for different types of key-value pairs to enrich the usage scenarios of key-value pairs.

  • The type attribute is a structural pointer to dictType. Each dictType structure preserves a cluster of functions used to operate key value pairs of a specific type. Redis sets different types of specific functions for dictionaries with different uses.
typedef struct dictType{
    // The function that calculates the hash value
    unsigned int (*hashFunction)(const void *key);
    // Copy the key function
    void *(*keyDup)(void *privdata,const void *key)
    ...
}
Copy the code
  • The privData attribute holds the optional parameters that need to be passed to those type-specific functions

hashtable

struct dictEntry {
    void* key;
    / / value
    union{
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    dictEntry* next; // Next is a pointer to another hash node that resolves conflicts by concatenating multiple key-value pairs with the same hash value.
}
struct dictht {
    dictEntry** table; / / 2 d
    long size; // The length of the first dimension array
    long used; // Number of elements in hash table
    // Hash table size mask, used to calculate index values
    // always equal to size-1
    unsigned long sizemask;
}
Copy the code

Hash =dict->type->hashFunction(key); Index =hash & dict->ht[x].sizemask;

capacity

  1. Allocates space for the dictionary HT [1] hash table, depending on the operation to be performed and the number of current key-value pairs for HT [0].
  2. Store all key-value pairs saved in HT [0] in the location specified by HT [1].
  3. When all key-value pairs of HT [0] have been migrated, release HT [0] and point to HT [1], and create an empty hash table on HT [1] for the next rehash.
  • The server is not currently executing the BGSAVE or BGREWRITEAOF command, and the hash table load factor is >=1.
  • The server is running the BGSAVE or BGREWRITEAOF command and the hash table load factor is >=5.

The process of progressive rehash

During rehash, the dictionary uses both HT [0] and HT [1] hash tables. Hash table operations are performed on both tables, such as searching for keys in HT [0] first, and continuing to ht[1] if empty. During this period, all new key-value pairs are added to HT [1]. Ht [0] does not undertake any addition operations, ensuring that the number of key-value pairs in HT [0] is reduced.

Please add the following text and link at the end of the article: This article is participating in the “Gold Digging Booklet free learning!” Event, click to view details of the event