Quickly understand what the dictionary in redis is

Dictionary Introduction

A dictionary is a data structure used to hold key value pairs , You can quickly find the corresponding value through the key in the key value pair . stay Redis What is used C In language , No built-in dictionary , therefore Redis I realized the dictionary myself .

Whole Redis All the keys and values of the database form a global dictionary , The operations of adding, deleting, modifying and querying the database are all based on the operation of the dictionary .

Dictionary or Redis Basic data type hash （hash） One of the underlying implementations of , When the length of keys and values of hash data type is large or the number of key value pairs is large ,Redis The dictionary will be used as the underlying implementation of hash data type .

Dictionary or Redis An ordered collection of basic data types （zset） One of the underlying implementations of , When the member length of all elements in the ordered set is long or the number of elements is large ,Redis The jump table and hash table will be the internal implementation of the ordered set .

Dictionary implementation

stay Redis The dictionary in is made up of dict Structure means , Its underlying implementation uses a hash table , A hash table contains multiple hash table nodes , Each hash table node stores a key value pair in the dictionary . Now let's take a detailed look at one by one .

Dictionary structure

Dictionaries are written by dict Structure means , It contains the following properties ：

• type attribute ： A pointer to a dictType Pointer to structure , Every dictType Structures store a set of functions for their specific type of key value pair operation .
• privdata attribute ： Save the optional parameters that need to be passed to its specific type function .
• ht attribute ： An array of two items , Each item is a hash table . In general , The dictionary only uses the first hash table , Only after re hashing （rehash） The second hash table is only used when .
• rehashidx attribute ： Used to record rehash （rehash） Progress , When there is no hashing （rehash） When , Its value is -1.

among ,type Properties and privdata After attribute combination , You can do different processing operations for different types of key value pairs , such as ： Calculate the hash value 、 Copy key 、 Copy value 、 Contrast key 、 Destroy key 、 Destroy value, etc .

Hashtable

Hash table use dictht Structural representation , It contains the following properties ：

• table attribute ： A hash table array , Each item in the array is a pointer to the hash table node , Each hash table node stores a key value pair in the dictionary .
• size attribute ： The size of the hash table , That is, hash table array （table） Size .
• sizemask attribute ： Hash table size mask , Used to calculate index values , Always equal to hash table size （size）-1.
• used attribute ： The number of existing nodes in the hash table .

Hash table node

Hash table nodes use dictEntry Structural representation , It contains the following properties ：

• key attribute ： Used to save the key in the key value pair .
• v attribute ： Used to save the value in the key value pair . It can be a pointer , It can also be a uint64_t The integer of , It can also be a int64_t The integer of .
• next attribute ： A pointer to the next hash table node . When there is a key conflict , It can connect multiple hash table nodes , Form a one-way list .

Dictionary example

Said so much , Are relatively abstract and not easy to understand , Let's give you an example ：

This is the internal structure of a dictionary , Among them is 3 Key value pairs , The keys are ： ten thousand 、 cat 、 study group .