HashTable 实现

HashTable在Redis 中分为3 层，自底向上分别是：

• dictEntry：管理一个field - value 对，保留同一桶中相邻元素的指针，以此维护Hash 桶中的内部链
• dictht：维护Hash表的所有桶链
• dict：当dictht需要扩容/缩容时，用户管理dictht的迁移

dict是Hash表存储的顶层结构

// 哈希表（字典）数据结构，Redis 的所有键值对都会存储在这里。其中包含两个哈希表。
typedef struct dict {
    // 哈希表的类型，包括哈希函数，比较函数，键值的内存释放函数
    dictType *type;
    // 存储一些额外的数据
    void *privdata;
    // 两个哈希表
    dictht ht[2];
    // 哈希表重置下标，指定的是哈希数组的数组下标
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
    // 绑定到哈希表的迭代器个数
    int iterators; /* number of iterators currently running */
} dict;

Hash表的核心结构是dictht，它的table 字段维护着 Hash 桶，桶（bucket）是一个数组，数组的元素指向桶中的第一个元素（dictEntry）。

typedef struct dictht { 
    //槽位数组
    dictEntry **table; 
    //槽位数组长度
    unsigned long size; 
    //用于计算索引的掩码 
    unsigned long sizemask;
    //真正存储的键值对数量
    unsigned long used; 
} dictht;

结构图

Hash表使用【链地址法】解决Hash冲突。当一个 bucket 中的 Entry 很多时，Hash表的插入性能会下降，此时就需要增加bucket的个数来减少Hash冲突。

Hash表扩容

和大多数Hash表实现一样，Redis引入负载因子判定是否需要增加bucket个数：

负载因子 = Hash表中已有元素 / bucket数量

扩容后，bucket 数量是原先2倍。目前有2 个阀值：

• 小于1 时一定不扩容
• 大于5 时一定扩容
• 在1 ~ 5 之间时，Redis 如果没有进行bgsave/bdrewrite 操作时则会扩容
• 当key - value 对减少时，低于0.1时会进行缩容。缩容之后，bucket的个数是原先的0.5倍

ziplist 实现

这里的 ziplist 和List#ziplist的实现类似，都是通过Entry 存放元素。

不同的是，Map#ziplist的Entry个数总是2的整数倍：

• 第奇数个Entry存放key
• 下个相邻Entry存放value

ziplist承载时，Map的大多数操作不再是O(1)了，而是由Hash表遍历，变成了链表的遍历，复杂度变为O(N)

由于Map相对较小时采用ziplist，采用Hash表时计算hash值的开销较大，因此综合起来ziplist的性能相对好一些

哈希键值结构

特点：

• Map的map
• Small redis
• field不能相同，value可相同

hget key field O(1)
# 获取 hash key 对应的 field 的 value
hset key field value O(1)
#  设置 hash key 对应的 field 的 value
hdel key field O(1)
# 删除 hash key 对应的 field 的 value

实操

127.0.0.1:6379> hset user:1:info age 23
(integer) 1
127.0.0.1:6379> hget user:1:info age
"23"
127.0.0.1:6379> hset user:1:info name JavaEdge
(integer) 1
127.0.0.1:6379> hgetall user:1:info
1) "age"
2) "23"
3) "name"
4) "JavaEdge"
127.0.0.1:6379> hdel user:1:info age
(integer) 1
127.0.0.1:6379> hgetall user:1:info
1) "name"
2) "JavaEdge"

hexists key field O(1)
# 判断hash key是否有field
hlen key O(1)
# 获取hash key field的数量

127.0.0.1:6379> hgetall user:1:info
1) "name"
2) "JavaEdge"
127.0.0.1:6379> HEXISTS user:1:info name
(integer) 1
127.0.0.1:6379> HLEN user:1:info
(integer) 1

hmget key field1 field2... fieldN O(N)
# 批量获取 hash key 的一批 field 对应的值
hmset key field1 value1 field2 value2...fieldN valueN O(N)
# 批量设置 hash key的一批field value

Redis Hashes 保存String域和String值之间的映射，所以它们是用来表示对象的绝佳数据类型（比如一个有着用户名，密码等属性的User对象）

| `1` | `@cli` |
| `2` | `HMSET user:1000 username antirez password P1pp0 age 34` |
| `3` | `HGETALL user:1000` |
| `4` | `HSET user:1000 password 12345` |
| `5` | `HGETALL user:1000` |

一个有着少量数据域（这里的少量大概100上下）的hash，其存储方式占用很小的空间，所以在一个小的Redis实例中就可以存储上百万的这种对象

Hash的最大长度是2^32 – 1个域值对（4294967295，一个Hash中可以有多达40多亿个域值对）

Sorted sets(zset)

有序集合，去重但可排序，写进去时候给个分数，可以自定义排序规则。比如想根据时间排序，则写时可以使用时间戳作为分数。

排行榜：将每个用户以及其对应的什么分数写进去。

127.0.0.1:6379> zadd board 1.0 JavaEdge
(integer) 1

获取排名前100的用户：

127.0.0.1:6379> zrevrange board 0 99
1) "JavaEdge"

用户在排行榜里的排名：

127.0.0.1:6379> zrank board JavaEdge
(integer) 0

127.0.0.1:6379> zadd board 85 zhangsan
(integer) 1
127.0.0.1:6379> zadd board 72 wangwu
(integer) 1
127.0.0.1:6379> zadd board 96 lisi
(integer) 1
127.0.0.1:6379> zadd board 62 zhaoliu
(integer) 1
# 获取排名前3的用户
127.0.0.1:6379> zrevrange board 0 3
1) "lisi"
2) "zhangsan"
3) "wangwu"
4) "zhaoliu"
127.0.0.1:6379> zrank board zhaoliu
(integer) 1

类似于Map的key-value对，但有序

• key ：key-value对中的键，在一个Sorted-Set中不重复
• value ： 浮点数，称为 score
• 有序 ：内部按照score 从小到大的顺序排列

基本操作

由于Sorted-Set 本身包含排序信息，在普通Set 的基础上，Sorted-Set 新增了一系列和排序相关的操作：

• Sorted-Set的基本操作

内部数据结构

Sorted-Set类型的valueObject 内部结构有两种：

1. ziplist

实现方式和Map类似，由于Sorted-Set包含了Score的排序信息，ziplist内部的key-value元素对的排序方式也是按照Score递增排序的，意味着每次插入数据都要移动之后的数据，因此ziplist适于元素个数不多，元素内容不大的场景。

2.skiplist+hashtable

更通用的场景，Sorted-Set使用sliplist来实现。

8.2.1 zskiplist

和通用的跳表不同的是，Redis为每个level 对象增加了span 字段，表示该level 指向的forward节点和当前节点的距离，使得getByRank类的操作效率提升

• 数据结构

• 结构示意图

每次向skiplist 中新增或者删除一个节点时，需要同时修改图标中红色的箭头，修改其forward和span的值。

需要修改的箭头和对skip进行查找操作遍历并废弃过的路径是吻合的。span修改仅是+1或-1。

zskiplist 的查找平均时间复杂度 O(Log(N))，因此add / remove的复杂度也是O(Log(N))。因此Redis中新增的span 提升了获取rank（排序）操作的性能，仅需对遍历路径相加即可（矢量相加）。

还有一点需要注意的是，每个skiplist的节点level 大小都是随机生成的（1-32之间）。

• zskiplistNode源码

8.2.2 hashtable

zskiplist 是zset 实现顺序相关操作比较高效的数据结构，但是对于简单的zscore操作效率并不高。Redis在实现时，同时使用了Hashtable和skiplist，代码结构如下：

Hash表的存在使得Sorted-Set中的Map相关操作复杂度由O(N)变为O(1)。

Redis有序集合类型与Redis的集合类型类似，是非重复的String元素的集合。不同之处在于，有序集合中的每个成员都关联一个Score，Score是在排序时候使用的，按照Score的值从小到大进行排序。集合中每个元素是唯一的，但Score有可能重复。

使用有序集合可以很高效的进行，添加，移除，更新元素的操作（时间消耗与元素个数的对数成比例）。由于元素在集合中的位置是有序的，使用get ranges by score或者by rank（位置）来顺序获取或者随机读取效率都很高。（本句不确定，未完全理解原文意思，是根据自己对Redis的浅显理解进行的翻译）访问有序集合中间部分的元素也非常快，所以可以把有序集合当做一个不允许重复元素的智能列表，你可以快速访问需要的一切：获取有序元素，快速存在测试，快速访问中间的元素等等。

简短来说，使用有序集合可以实现很多高性能的工作，这一点在其他数据库是很难实现的。

应用

• 在大型在线游戏中创建一个排行榜，每次有新的成绩提交，使用[ZADD]命令加入到有序集合中。可以使用[ZRANGE]命令轻松获得成绩名列前茅的玩家，你也可以使用[ZRANK]根据一个用户名获得该用户的分数排名。把ZRANK 和 ZRANGE结合使用你可以获得与某个指定用户分数接近的其他用户。这些操作都很高效。
• 有序集合经常被用来索引存储在Redis中的数据。比如，如果你有很多用户，用Hash来表示，可以使用有序集合来为这些用户创建索引，使用年龄作为Score，使用用户的ID作为Value，这样的话使用[ZRANGEBYSCORE]命令可以轻松和快速的获得某一年龄段的用户。zset有个ZSCORE的操作，用于返回单个集合member的分数，它的操作复杂度是O(1)，这就是收益于你这看到的hash table。这个hash table保存了集合元素和相应的分数，所以做ZSCORE操作时，直接查这个表就可以，复杂度就降为O(1)了。

而跳表主要服务范围操作，提供O(logN)的复杂度。

Bitmaps

位图类型，String类型上的一组面向bit操作的集合。由于 strings是二进制安全的blob，并且它们的最大长度是512m，所以bitmaps能最大设置 2^32个不同的bit。

HyperLogLogs

pfadd/pfcount/pfmerge。

在redis的实现中，使用标准错误小于1％的估计度量结束。这个算法的神奇在于不再需要与需要统计的项相对应的内存，取而代之，使用的内存一直恒定不变。最坏的情况下只需要12k，就可以计算接近2^64个不同元素的基数。

GEO

geoadd/geohash/geopos/geodist/georadius/georadiusbymember

Redis的GEO特性在 Redis3.2版本中推出，这个功能可以将用户给定的地理位置（经、纬度）信息储存起来，并对这些信息进行操作。