Series of articles:

What does redis do with simple dynamic string SDS

A List of what redis does at the bottom

What Hash is redis doing underneath

Redis values are Hash types (also known as Dict Dict). The underlying implementation is Hash table. A Hash table has multiple Hash table nodes, each Hash table node stores a key value pair

Hash table structure:

An empty hash table structure of size 4 is shown below

tableIs an array in which each element points to a hash table node

The size property records the size of the hash table, that is, the size of the table array

The sizemask attribute always equals size-1. This attribute, along with the hash value, determines which index of the table array a key should be placed on

The used property records the number of non-null points in the table array, which means that the pointer already corresponds to a hash table node

Hash node structure:

Denoted by dictEntry, each dictEntry structure holds a key-value pair

K property save key

The V property holds a value, which can be a pointer or a number

nextProperty is a pointer to another hash table node. Pointers can be used to join multiple key-value pairs with the same hash value together to solve the problem of key conflictsRedis uses dict to package hash table. Dict structure is as follows typeAttribute is a pointer to dictType structure. Each dictType structure preserves a cluster of functions for manipulating key value pairs of a specific type. Redis will set different type-specific functions for dictionaries with different uses.

The privData attribute holds the optional parameters that need to be passed to those type-specific functions

The HT attribute is an array of two entries. Normally, dictionaries only use the HT [0] hash table, and when the hash table is rehashed, the HT [1] hash table is used.

rehashidxThe progress of rehash is logged, with a value of -1 if there is no rehash currently

Hash algorithm:

When a new key-value pair is added to the dictionary, the hash value and index value of the table array are calculated based on the key of the key-value pair. Based on the index value, the key-value pair is added to the specified position in the array.

1. Calculate the hash value of the key using the hash function set by the dictionary

2. Index value = hash value & sizemask (binary and operation)

Rehash operations:

To keep the load factor of the hash table within a reasonable range as key-value pairs are added or removed, rehash is required (using the hash table of HT [1])

1. Allocate space for the dictionary HT [1] hash table, depending on whether it is expanded or shrunk, and the number of key-value pairs ht[0] currently contains (i.e. the value of ht[0]. Used).

(1) If you want to expand the hash table, first calculate x = ht[0]. Used *2, and then find the first value y that is greater than or equal to x to the 2 n power, which is the size of the space ht[1] should allocate.

For example, if x is equal to 5 times 2, then y would be 2 to the fourth is equal to 16 is the first one that is greater than or equal to x to the 2 to the n, so y is equal to 16.Copy the code

(2) If the hash table x = ht[0]. Used is reduced, then find the first value y that is greater than or equal to x to the 2 n power, which is the size of the space ht[1] should allocate.

If x is equal to 5, then y would be 2 to the third is equal to 8 is the first one greater than or equal to x to the 2 to the n, so y is equal to 8Copy the code

2. Recalculate all key/value pairs in HT [0] to the specified position in ht[1]

3. After ht[0] migrates all key pairs to HT [1] (HT [0] is empty), release HT [0], set HT [1] to HT [0], and create a blank hash table for HT [1] to prepare for the next rehash.

Hash syntax:

HSET

Adding key-value pairs to dictionaries A dictionary can add one or more key-value pairs

Grammar:

HSET key field value
Copy the code

HGET

Gets the value of a key in the dictionary

Grammar:

HGET key field
Copy the code

HMGET

Get multiple keys in the dictionary (key1 key2…) Multiple values

Grammar:

HMGET key field [field ...]
Copy the code

HGETALL

Get all the key-value pairs in the dictionary

Grammar:

HGETALL key
Copy the code

HLEN

Gets the number of all key-value pairs in the dictionary

Grammar:

HLEN key
Copy the code

HEXISTS

Determines whether all keys in a dictionary contain a value

Grammar:

HEXISTS key field
Copy the code

HKEYS

Displays all keys in the dictionary

Grammar:

HKEYS key
Copy the code

HVALS

Displays all values in the dictionary

Grammar:

HVALS key
Copy the code