Redis散列类型能够存储一组无序的键值对，它特地实用于存储一个对象数据。
> HSET fruit name apple price 7.6 origin china3> HGET fruit price"7.6"本文剖析Redis中散列类型以及其底层数据结构--字典的实现原理。
字典
Redis通常应用字典构造存储用户散列数据。
字典是Redis的重要数据结构。除了散列类型，Redis数据库也应用了字典构造。
Redis应用Hash表实现字典构造。剖析Hash表，咱们通常关注以下几个问题：
（1）应用什么Hash算法？
（2）Hash抵触如何解决？
（3）Hash表如何扩容？
提醒：本章代码如无特地阐明，均在dict.h、dict.c中。
定义
字典中键值对的定义如下：
typedef struct dictEntry { void *key; union { void *val; uint64_t u64; int64_t s64; double d; } v; struct dictEntry *next;} dictEntry;- key、v：键、值。
next：下一个键值对指针。可见Redis字典应用链表法解决Hash抵触的问题。
提醒：C语言union关键字用于申明共用体，共用体的所有属性共用同一空间，同一时间只能贮存其中一个属性值。也就是说，dictEntry.v能够寄存val、u64、s64、d中的一个属性值。应用sizeof函数计算共用体大小，后果不会小于共用体中最大的成员属性大小。
字典中Hash表的定义如下：
typedef struct dictht { dictEntry **table; unsigned long size; unsigned long sizemask; unsigned long used;} dictht;- table：Hash表数组，负责存储数据。
- used：记录存储键值对的数量。
- size：Hash表数组长度。
dictht的构造如图3-1所示。
字典的定义如下：
typedef struct dict { dictType *type; void *privdata; dictht ht[2]; long rehashidx; unsigned long iterators;} dict;- type：指定操作数据的函数指针。
- ht[2]：定义两个Hash表用于实现字典扩容机制。通常场景下只应用ht[0]，而在扩容时，会创立ht[1]，并在操作数据时中逐渐将ht[0]的数据移到ht[1]中。
- rehashidx：下一次执行扩容单步操作要迁徙的ht[0]Hash表数组索引，-1代表以后没有进行扩容操作。
- iterators：以后运行的迭代器数量，迭代器用于遍历字典键值对。
dictType定义了字典中用于操作数据的函数指针，这些函数负责实现数据复制、比拟等操作。
typedef struct dictType { uint64_t (*hashFunction)(const void *key); void *(*keyDup)(void *privdata, const void *key); void *(*valDup)(void *privdata, const void *obj); int (*keyCompare)(void *privdata, const void *key1, const void *key2); void (*keyDestructor)(void *privdata, void *key); void (*valDestructor)(void *privdata, void *obj);} dictType;通过dictType指定操作数据的函数指针，字典就能够寄存不同类型的数据了。但在一个字典中，键、值能够是不同的类型，但键必须类型雷同，值也必须类型雷同。
Redis为不同的字典定义了不同的dictType，如数据库应用的server.c/dbDictType，散列类型应用的server.c/setDictType等。
操作剖析
dictAddRaw函数能够在字典中插入或查找键：
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing){ long index; dictEntry *entry; dictht *ht; // [1] if (dictIsRehashing(d)) _dictRehashStep(d); // [2] if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1) return NULL; // [3] ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0]; // [4] entry = zmalloc(sizeof(*entry)); entry->next = ht->table[index]; ht->table[index] = entry; ht->used++; // [5] dictSetKey(d, entry, key); return entry;}参数阐明：
- existing：如果字典中已存在参数key，则将对应的dictEntry指针赋值给*existing，并返回null，否则返回创立的dictEntry。
【1】如果该字典正在扩容，则执行一次扩容单步操作。
【2】计算参数key的Hash表数组索引，返回-1，代表键已存在，这时dictAddRaw函数返回NULL，代表该键已存在。
【3】如果该字典正在扩容，则将新的dictEntry增加到ht[1]中，否则增加到ht[0]中。
【4】创立dictEntry，头插到Hash表数组对应地位的链表中。Redis字典应用链表法解决Hash抵触，Hash表数组的元素都是链表。
【5】将键设置到dictEntry中。
dictAddRaw函数只会插入键，并不插入对应的值。能够应用返回的dictEntry插入值：
entry = dictAddRaw(dict,mykey,NULL); if (entry != NULL) dictSetSignedIntegerVal(entry,1000);Hash算法
dictHashKey宏调用dictType.hashFunction函数计算键的Hash值：
#define dictHashKey(d, key) (d)->type->hashFunction(key)Redis中字典根本都应用SipHash算法（server.c/dbDictType、server.c/setDictType等dictType的hashFunction属性指向的函数都应用了SipHash算法）。该算法能无效地避免Hash表碰撞攻打，并提供不错的性能。
Hash算法波及较多的数学知识，本书并不探讨Hash算法的原理及实现，读者能够自行浏览相干代码。
提醒：Redis 4.0之前应用的Hash算法是MurmurHash。即便输出的键是有法则的，该算法计算的后果仍然有很好的离散性，并且计算速度十分快。Redis 4.0开始更换为SipHash算法，应该是出于平安的思考。
计算键的Hash值后，还须要计算键的Hash表数组索引：
static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing){ unsigned long idx, table; dictEntry *he; if (existing) *existing = NULL; // [1] if (_dictExpandIfNeeded(d) == DICT_ERR) return -1; // [2] for (table = 0; table <= 1; table++) { idx = hash & d->ht[table].sizemask; he = d->ht[table].table[idx]; while(he) { if (key==he->key || dictCompareKeys(d, key, he->key)) { if (existing) *existing = he; return -1; } he = he->next; } // [3] if (!dictIsRehashing(d)) break; } return idx;}【1】依据须要进行扩容或初始化Hash表操作。
【2】遍历ht[0]、ht[1]，计算Hash表数组索引，并判断Hash表中是否已存在参数key。若已存在，则将对应的dictEntry赋值给*existing。
【3】如果以后没有进行扩容操作，则计算ht[0]索引后便退出，不须要计算ht[1]。
扩容
Redis应用了一种渐进式扩容形式，这样设计，是因为Redis是单线程的。如果在一个操作内将ht[0]所有数据都迁徙到ht[1]，那么可能会引起线程长期阻塞。所以，Redis字典扩容是在每次操作数据时都执行一次扩容单步操作，扩容单步操作行将ht[0].table[rehashidx]的数据迁徙到ht[1]。等到ht[0]的所有数据都迁徙到ht[1]，便将ht[0]指向ht[1]，实现扩容。
_dictExpandIfNeeded函数用于判断Hash表是否须要扩容：
static int _dictExpandIfNeeded(dict *d){ ... if (d->ht[0].used >= d->ht[0].size && (dict_can_resize || d->ht[0].used/d->ht[0].size > dict_force_resize_ratio)) { return dictExpand(d, d->ht[0].used*2); } return DICT_OK;}扩容须要满足两个条件：
（1）d->ht[0].used≥d->ht[0].size：Hash表存储的键值对数量大于或等于Hash表数组的长度。
（2）开启了dict_can_resize或者负载因子大于dict_force_resize_ratio。
d->ht[0].used/d->ht[0].size，即Hash表存储的键值对数量/Hash表数组的长度，称之为负载因子。dict_can_resize默认开启，即负载因子等于1就扩容。负载因子等于1可能呈现比拟高的Hash抵触率，但这样能够进步Hash表的内存使用率。dict_force_resize_ratio敞开时，必须等到负载因子等于5时才强制扩容。用户不能通过配置敞开dict_force_resize_ratio，该值的开关与Redis长久化无关，等咱们剖析Redis长久化时再探讨该值。
dictExpand函数开始扩容操作：
int dictExpand(dict *d, unsigned long size){ ... // [1] dictht n; unsigned long realsize = _dictNextPower(size); ... // [2] n.size = realsize; n.sizemask = realsize-1; n.table = zcalloc(realsize*sizeof(dictEntry*)); n.used = 0; // [3] if (d->ht[0].table == NULL) { d->ht[0] = n; return DICT_OK; } // [4] d->ht[1] = n; d->rehashidx = 0; return DICT_OK;}参数阐明：
- size：新Hash表数组长度。
【1】_dictNextPower函数会将size调整为2的n次幂。
【2】构建一个新的Hash表dictht。
【3】ht[0].table==NULL，代表字典的Hash表数组还没有初始化，将新dictht赋值给ht[0]，当初它就能够存储数据了。这里并不是扩容操作，而是字典第一次应用前的初始化操作。
【4】否则，将新dictht赋值给ht[1]，并将rehashidx赋值为0。rehashidx代表下一次扩容单步操作要迁徙的ht[0] Hash表数组索引。
为什么要将size调整为2的n次幂呢？这样是为了ht[1] Hash表数组长度是ht[0] Hash表数组长度的倍数，有利于ht[0]的数据平均地迁徙到ht[1]。
咱们看一下键的Hash表数组索引计算方法：idx=hash&ht.sizemask，因为sizemask= size-1，计算方法等价于：idx=hash%(ht.size)。
因而，如果ht[0].size为n，ht[1].size为2×n，对于ht[0]上的元素，ht[0].table[k]的数据，要不迁徙到ht[1].table[k]，要不迁徙到ht[1].table[k+n]。这样能够将ht[0].table中一个索引位的数据拆分到ht[1]的两个索引位上。
图3-2展现了一个简略示例。
_dictRehashStep函数负责执行扩容单步操作，将ht[0]中一个索引位的数据迁徙到ht[1]中。 dictAddRaw、dictGenericDelete、dictFind、dictGetRandomKey、dictGetSomeKeys等函数都会调用该函数，从而逐渐将数据迁徙到新的Hash表中。
_dictRehashStep调用dictRehash函数实现扩容单步操作：
int dictRehash(dict *d, int n) { int empty_visits = n*10; // [1] if (!dictIsRehashing(d)) return 0; while(n-- && d->ht[0].used != 0) { dictEntry *de, *nextde; assert(d->ht[0].size > (unsigned long)d->rehashidx); // [2] while(d->ht[0].table[d->rehashidx] == NULL) { d->rehashidx++; if (--empty_visits == 0) return 1; } // [3] de = d->ht[0].table[d->rehashidx]; while(de) { uint64_t h; nextde = de->next; h = dictHashKey(d, de->key) & d->ht[1].sizemask; de->next = d->ht[1].table[h]; d->ht[1].table[h] = de; d->ht[0].used--; d->ht[1].used++; de = nextde; } d->ht[0].table[d->rehashidx] = NULL; d->rehashidx++; } // [4] if (d->ht[0].used == 0) { zfree(d->ht[0].table); d->ht[0] = d->ht[1]; _dictReset(&d->ht[1]); d->rehashidx = -1; return 0; } return 1;}参数阐明：
- n：本次操作迁徙的Hash数组索引的数量。
【1】如果字典以后并没有进行扩容，则间接退出函数。
【2】从rehashidx开始，找到第一个非空索引位。
如果这里查找的的空索引位的数量大于n×10，则间接返回。
【3】遍历该索引位链表上所有的元素。
计算每个元素在ht[1]的Hash表数组中的索引，将元素挪动到ht[1]中。
【4】ht[0].used==0，代表ht[0]的数据曾经全副移到ht[1]中。
开释ht[0].table，将ht[0]指针指向ht[1]，并重置rehashidx、d->ht[1]，扩容实现。
缩容
执行删除操作后，Redis会查看字典是否须要缩容，当Hash表长度大于4且负载因子小于0.1时，会执行缩容操作，以节俭内存。缩容实际上也是通过dictExpand函数实现的，只是函数的第二个参数size是缩容后的大小。
dict罕用的函数如表3-1所示。
| 函数 | 作用 |
|---|---|
| dictAdd | 插入键值对 |
| dictReplace | 替换或插入键值对 |
| dictDelete | 删除键值对 |
| dictFind | 查找键值对 |
| dictGetIterator | 生成不平安迭代器，能够对字典进行批改 |
| dictGetSafeIterator | 生成平安迭代器，不可对字典进行批改 |
| dictResize | 字典缩容 |
| dictExpand | 字典扩容 |
编码
散列类型有OBJ_ENCODING_HT和OBJ_ENCODING_ZIPLIST两种编码，别离应用dict、ziplist构造存储数据（redisObject.ptr指向dict、ziplist构造）。Redis会优先应用ziplist存储散列元素，应用一个ziplist节点存储键，后驱节点寄存值，查找时须要遍历ziplist。应用dict存储散列元素，字典的键和值都是sds类型。散列类型应用OBJ_ENCODING_ZIPLIST编码，需满足以下条件：
（1）散列中所有键或值的长度小于或等于server.hash_max_ziplist_value，该值可通过hash-max-ziplist-value配置项调整。
（2）散列中键值对的数量小于server.hash_max_ziplist_entries，该值可通过hash-max- ziplist-entries配置项调整。
散列类型的实现代码在t_hash.c中，读者能够查看源码理解更多实现细节。
数据库
Redis是内存数据库，外部定义了数据库对象server.h/redisDb负责存储数据，redisDb也应用了字典构造治理数据。
typedef struct redisDb { dict *dict; dict *expires; dict *blocking_keys; dict *ready_keys; dict *watched_keys; int id; ...} redisDb;- dict：数据库字典，该redisDb所有的数据都存储在这里。
- expires：过期字典，存储了Redis中所有设置了过期工夫的键及其对应的过期工夫，过期工夫是long long类型的UNIX工夫戳。
- blocking_keys：处于阻塞状态的键和相应的客户端。
- ready_keys：筹备好数据后能够解除阻塞状态的键和相应的客户端。
- watched_keys：被watch命令监控的键和相应客户端。
- id：数据库ID标识。
Redis是一个键值对数据库，全称为Remote Dictionary Server（近程字典服务），它自身就是一个字典服务。redisDb.dict字典中的键都是sds，值都是redisObject。这也是redisObject作用之一，它将所有的数据结构都封装为redisObject构造，作为redisDb字典的值。
一个简略的redisDb构造如图3-3所示。
当咱们须要操作Redis数据时，都须要从redisDb中找到该数据。
db.c中定义了hashTypeLookupWriteOrCreate、lookupKeyReadOrReply等函数，能够通过键找到redisDb.dict中对应的redisObject，这些函数都是通过调用dict API实现的，这里不一一展现，感兴趣的读者能够自行浏览代码。
总结：
- Redis字典应用SipHash算法计算Hash值，并应用链表法解决Hash抵触。
- Redis字典应用渐进式扩容形式，在每次数据操作中都执行一次扩容单步操作，直到扩容实现。
- 散列类型的编码格局能够为OBJ_ENCODING_HT、OBJ_ENCODING_ZIPLIST。
本文内容摘自作者新书《Redis外围原理与实际》，这本书深刻地剖析了Redis罕用个性的外部机制与实现形式，大部分内容源自对Redis 6.0源码的剖析，并从中总结出设计思路、实现原理。通过浏览本书，读者能够疾速、轻松地理解Redis的外部运行机制。
通过该书编辑批准，我会持续在集体技术公众号（binecy）公布书中局部章节内容，作为书的预览内容，欢送大家查阅，谢谢。
京东链接
豆瓣链接