The concept of a dictionary

Dictionaries are abstract data structures that hold key-value pairs and are used in many languages. C doesn’t have them built in, so Redis built its own dictionary implementation

127.0.0.1:6379> set msg "hellow yanglele"
OK
Copy the code

The MSG key and the value “Hellow yanglele” are stored in the dictionary that represents the database. In addition to representing the database, the dictionary is also the underlying implementation of the hash key. If the hash key contains many keys and values in contrast, or the elements in the key-value pair are long strings, Redis uses the dictionary as the underlying implementation of the hash key

The realization of dictionary

  1. Hash table

    The data structure

    Typedef stuct dictht {// Hash table array dictEntry **table; // Hash table size unsigned long size; // Always equal to size-1 unsigned long sizeremark; // Number of existing nodes in this hash table}Copy the code

  2. Hash table node

    Typedef stuct dictEntry {// key void *key; // value union{void *val; unit64_t u64; int64_t s64; } v; // point to the next hash table node to form a linked list} dictEntry;Copy the code

    Next can resolve hash conflicts by concatenating multiple keys with the same hash value.

  3. The dictionary

    • The data structure

      Typedef struct dict {// type specific function dictType *type; // Private data void * privData; Dictht ht[2] // Rehash index // When rehash is no longer performed, the value is -1 int trehashIndex} dict;Copy the code

      Dictht HT [2] contains two arrays, HT [0], and HT [1]. Ht [1] rehashes ht[0]. When the rehash is complete, Ht [1] becomes HT [0];

    • Resolve the conflict

      If you have studied Java HashMap, you can easily understand how Redis solves this problem, because they are roughly the same. First, the index position can be obtained by the hash of the key, but the index position can be conflicting. In this case, the linked list is used. If conflicts occur, elements are added to the linked list

    • rehash

      So this is what I said before, ht0 and HT1, without describing it

    • Progressive rehash

      What if the value is too large to move at once? Redis’s solution is to hash increments, that is, move bits and pieces, and then look at the progress of the move through the TreHashIndex property.