Interviewer: what is the internal implementation of hash data type in redis?

interviewer ：Redis What are the basic data types in ？

I ：Redis The basic data types of are ： character string （string）、 Hash （hash）、 list （list）、 aggregate （set）、 Ordered set （zset）.

interviewer ： What is the internal implementation of hash data type ？

I was also immersed in the complacency of the last question , Suddenly, his expression solidified , The palms began to sweat .“ This .. Not much in-depth understanding ”, I hesitated .

interviewer ： Go back and wait for the news .

This sentence is clear , And then there's no then . Failure is the mother of success , I'm not discouraged , Decided to mend it right away .

Encoding of hash

There are two kinds of hash encoding , Compressed list （ziplist） Hash table （hashtable）. When the length of keys and values of all key value pairs is less than hash-max-ziplist-value（ The default is 64 byte ）, And the number of key value pairs is less than hash-max-ziplist-entries（ The default is 512 individual ） When , The hash will be encoded using a compressed list , Otherwise, use hash table as encoding .

Let's give you an example ：

Log in and copy

127.0.0.1:6379> hset one-more-hash name " Wanmao society "
(integer) 1
127.0.0.1:6379> hset one-more-hash gender " male "
(integer) 1
127.0.0.1:6379> object encoding one-more-hash
"ziplist"

     

      
1.
      
2.
      
3.
      
4.
      
5.
      
6.
     

here , The length of keys and values of all key value pairs and the number of key value pairs are relatively small , Hashes are encoded using a compressed list . Let's add a key value pair with a large value ：

Log in and copy

127.0.0.1:6379> hset one-more-hash introduce "Java Quality creators in the field 、CSDN Blog expert certification "
(integer) 1
127.0.0.1:6379> object encoding one-more-hash
"hashtable"

     

      
1.
      
2.
      
3.
      
4.
     

here , The encoding of hash is transformed from compressed list to encoding .

Of course , I haven't fully understood the above details yet “ conquer ” interviewer , We need to go deeper :)

The underlying implementation of hash

When the compressed list is used as the encoding of hash , A new key value pair is added to the hash data type , First, add the compressed list node of the key to the end of the compressed list , Then add the compressed list node of the value to the end of the compressed list .

therefore , In the compressed list of hash data types , The key value pair added first is in the head direction of the compressed list , The added key value pair is at the end of the compressed list ; The two nodes of the same key value pair are close together , The node of the key is first , The node of the value is after .

The compressed list uses a more compact memory structure to realize the continuous storage of multiple key value pairs , Better than hash table in saving memory .

When the hash table is used as the encoding of hash , Each key value pair is saved with a dictionary key value pair , Each key in the dictionary is a string object , Object to save key value pairs ; Each value of the dictionary is also a string object , Object to save the value of the key value pair .

Although hash tables do not compress lists, they save memory , But its reading and writing time complexity is O(1), Better time efficiency than compressed lists .

summary

The internal implementation of hash data type has compressed list （ziplist） Hash table （hashtable） Two kinds of . When the length of keys and values of hash data type is small and the number of key value pairs is small , Use a compressed list as an internal implementation , Otherwise, use the hash table as the internal implementation .

---

I've seen it here , You and I must be predestined friends , Leave your give the thumbs-up and Focus on , It will become a great thing in the future .