【Redis】基础结构（二）：Hash 类型命令、应用、原理

桃扇骨 2023-01-18 14:28 16阅读 0赞

Redis 的字典相当于Java 语言里面的 HashMap，它是无序字典。内部实现结构上同 Java 的 HashMap 也是一致的，同样的数组 + 链表二维结构。第一维 hash 的数组位置碰撞时，就会将碰撞的元素使用链表串接起来。

优点：

*  同类数据归类整合存储，方便数据管理
 *  相比string操作消耗内存与cpu更小
 *  相比string更节省空间

缺点：

*  过期功能不能用在field上，只能用在key上
 *  Redis集群架构下不适合大规模使用
 *  需要考虑数据量分布的问题（value 值非常大的时候，无法分布到多个节点）

### 1.常用命令 ###

**1.增（hset）**

hset key filed value                              // 存储一个哈希表key的剑指
    
    hmset key filed value [filed value...]      	  // 在一个哈希表key中存储多个键值对
    hsetnx key filed value                            // 存储一个不在的哈希表key的键值

**2.删**

hdel key filed [key filed...]                     // 删除哈希表key中的field键值

**3.原子操作**

hincrby key filed increment  					   // 为哈希表key中field键的值加上增量increment

**4.查（hget）**

hget key filed                                     // 获取哈希表key对应的field键值
    hmget key filed [key filed...]    				   // 批量获取哈希表key中多个field键值
    hlen key                    				       // 返回哈希表key中field的数量
    hgetall key 									   // 返回哈希表中所有的键值

### 2.应用示例 ###

**1.对象缓存**

用hash结构存储对象相较于string：cpu占用小，而且更节省空间

hmset user:1 name zhangsan age 18 
    hmget user:1 name age

**2.模拟购物车（字段修改）**

以用户id为key，商品id为field，商品数量为value  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center][]

hset cart:1001 10088 1    				// 添加商品
    hincrby cart:1001 10088 1			    // 增加数量
    hlen cart:1001						    // 商品总数
    hdel cart:1001							// 删除商品
    hgetall cart:1001						// 获取购物车所有商品

### 3.存储原理 ###

Hash 底层实现采用了 ZipList 和 HashTable 两种实现方式。

当同时满足如下两个条件时底层采用了 ZipList 实现，一旦有一个条件不满足时，就会被转码为 HashTable 进行存储

*  Hash 中存储的所有元素的 key 和 value 的长度都小于等于 64byte
 *  Hash 中存储的元素个数小于 512

/* src/redis.conf 配置 */
    hash-max-ziplist-value 64 	 // ziplist 中最大能存放的值长度
    hash-max-ziplist-entries 512 // ziplist 中最多能存放的 entry 节点数

**ZipList（压缩列表） 方式**

压缩列表是 redis 为了节约内存而开发的，是由一系列的特殊编码的**连续内存块**组成的双向链表。一个压缩列表可以包含任意多个节点(entry)，每个节点可以保存一个字节数组或者一个整数值，值的类型和长度由节点的encoding属性决定。

它不存储指向上一个链表节点和指向下一个链表节点的指针，而是存储上一个节点长度和当前节点长度，也就是和说与数组的区别在于数组的每个元素大小相同，而 ziplist 的每个节点的大小不是固定（保存->计算地址）。

ziplist 通过牺牲部分读写性能，来换取高效的内存空间利用率，是一种时间换空间的思想。只用在字段个数少，字段值小的场景里面。

来看 ziplist 的整体结构：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70]

*  zlbytes：表示当前 list 的存储元素的总长度
 *  zllen：表示当前 list 存储的元素的个数
 *  zltail：表示当前 list 的头结点的地址，通过 zltail 就是可以实现 list 的遍历
 *  zlend：表示当前 list 的结束标识

下面看具体的元素 zlentry 是怎么定义的：

typedef struct zlentry {
        
    	
    	/* 上一个链表节点占用的长度 */
    	unsigned int prevrawlensize; 
    	/* 存储上一个链表节点的长度数值所需要的字节数 */
    	unsigned int prevrawlen; 
    	/* 存储当前链表节点长度数值所需要的字节数 */
    	unsigned int lensize; 
    	/* 当前链表节点占用的长度 */
    	unsigned int len; 
    	/* 当前链表节点的头部大小（prevrawlensize + lensize），即非数据域的大小 */
    	unsigned int headersize; 
    	/* 编码方式 */
    	unsigned char encoding; 
    	/* 压缩链表以字符串的形式保存，该指针指向当前节点起始位置 */
    	unsigned char *p; 
    	
    } zlentry;

> **ZipList 的优缺点比较**
> 
>  *  优点：内存地址连续，省去了每个元素的头尾节点指针占用的内存
>  *  缺点：对于删除和插入操作比较可能会触发连锁更新反应，比如在 list 中间插入删除一个元素时，在插入或删除位置后面的元素可能都需要发生相应的移动操作

最后，来看 ziplist 是如何实现 Hash 结构的：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center 1]

**HashTable 方式**

在 Redis 中，hashtable 被称为字典（dictionary），它是一个数组+链表的结构。

在之前的文章我们介绍了，Redis 的 KV 结构是通过一个 dictEntry 来实现的：

typedef struct dictEntry {
        
    
       /* key 关键字定义 */
       void *key; 
       union {
        
        /* value 定义 */
       void *val; uint64_t u64;
       int64_t s64; double d;
       } v;
       /* 指向下一个键值对节点 */
       struct dictEntry *next; 
       
    } dictEntry;

dictht 又对 dictEntry 进行了多层的封装：

/* This is our hash table structure. Every dictionary has two of this as we
    * implement incremental rehashing, for the old to the new table. */
    typedef struct dictht {
        
    
    	/* 哈希表数组 */
        dictEntry **table; 
        /* 哈希表大小 */
        unsigned long size; 
        /* 掩码大小，用于计算索引值。总是等于 size-1 */
        unsigned long sizemask; 
        /* 已有节点数 */
        unsigned long used; 
        
    } dictht

ht 又放到了 dict 里面：

typedef struct dict {
        
    	
    	/* 字典类型 */
        dictType *type; 
        /* 私有数据 */
        void *privdata; 
        /* 一个字典有两个哈希表 */
        dictht ht[2]; 
        /* rehash 索引 */
        long rehashidx; 
        /* 当前正在使用的迭代器数量 */
        unsigned long iterators; 
        
    } dict;

从最底层到最高层 dictEntry——dictht——dict——OBJ\_ENCODING\_HT

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center 2]

> 注意：dictht 后面是 NULL 说明第二个 ht 还没用到。dictEntry\* 后面是 NULL 说明没有 hash 到这个地址。dictEntry 后面是 NULL 说明没有发生哈希冲突。

问题：为什么要定义两个哈希表呢？

ht\[2\] redis 的 hash，默认使用的是 ht\[0\]，ht\[1\]不会初始化和分配空间。

哈希表 dictht 是用链地址法来解决碰撞问题的。在这种情况下，哈希表的性能取决于它的大小（size 属性）和它所保存的节点的数量（used 属性）之间的比率，比率在 1:1 时，哈希表的性能最好；。

如果节点数量比哈希表的大小要大很多的话（这个比例用 ratio 表示，ratio = used / size），那么哈希表就会退化成多个链表，哈希表本身的性能优势就不再存在，所以，在这种情况下需要扩容。

> dict\_can\_resize 为 1 并且 dict\_force\_resize\_ratio 已使用节点数和字典大小之间的 比率超过 1：5，触发扩容

**rehash** 的步骤：

1.  为字符 ht\[1\] 哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及 ht\[0\] 当前包含的键值对的数量。
2.  将所有的 ht\[0\] 上的节点 rehash 到 ht\[1\]上，重新计算 hash 值和索引，然后放入指定的位置。
3.  当 ht\[0\]全部迁移到了 ht\[1\]之后，释放 ht\[0\] 的空间，将 ht\[1\] 设置为 ht\[0\] 表， 并创建新的 ht\[1\]，为下次 rehash 做准备

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221021/a7aa81c2d6fa42e19f9c1f73be9621e3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70]: /images/20221021/81d83df6fca547ec83504144cd0bcdef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221021/e2271a94145c42c2b1f17db63f7f719a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221021/96f54330b05e46a19a760c7926796905.png