Redis本身就是一个key-value结构，它的value可以是map类型，此类型的value内部又是一个subkey-subvalue。
map内部的key和value不能再嵌套map，它只能是String型能表达的内容:整形、浮点型、字节串。
内存数据结构
map可以使用hashtable和ziplist两种承载方式来实现，对于数据量较小的map，采用ziplist来实现。
hashtable实现
哈希表在Redis中分为三层，自底向上分别是：
dictEntry：管理一个key-value对，同时保留同一个桶中相邻元素的指针，以此维护哈希桶的内部链。
dictht：维护哈希表的所有桶链
dict：当dictht需要扩容/缩容时，用于dictht的迁移
哈希表
哈希表的核心结构是dictht，它的table字段维护着hash桶，它是一个数组，每个元素指向桶的第一个元素(dictEntry)：
typedef struct dictht{
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
}
当一个新的key(例如key3)访问时，首先通过MurmurHash算法求出key的hash值，再对桶的个数(即dictht的size字段)取模，得到key3对应的桶，再进入桶中，遍历全部entry，判定是否已有相同的key，如果没有，则将新key对应的键值对插入到桶头，并且更新dictht的used数量，used表示当前hash表中已经存了多少元素。
由于桶的个数永远是2的n次方，可以用size-1做位运算&快速得到哈希值的模，因此在dictht中，引入了sizemask，它的值恒等于size-1。
每次插入key-value对时，都需要对某一个桶中的全部entry进行遍历，确保没有重复的key。当一个桶中的entry很多时，hash表的插入性能会线性下降。当它下降到一定程度时，需要增加桶的个数以减少hash冲突。
扩容
Redis引入负载因子判定是否需要增加桶数，负载因子=哈希表中已有元素和哈希桶数的比值，目前有两个阀值：
小于1时一定不扩容
大于5时一定扩容
介于1-5时，Redis如果没有进行bgsave/bgrewrite操作时则会扩容
哈希表随着业务的访问，key-value会越来越少，造成大量桶空置，无效占用内存，需要缩容。Redis同样根据负载因子决定是否缩容，目前缩容的阀值是0.1。
桶的数量均是指数变化，扩容时新的桶的数目是现有桶的2n倍，扩到刚好大于used值，缩容后新的桶数是原有的0.5n倍，也是锁到刚好大于used值。
扩/缩容都是通过新建哈希表的方式实现。也就是说，扩容发生时，并存了两个哈希表，一个是源表，一个是目标表。通过将源表的桶逐步迁移到目标表，以数据迁移的方式实现扩容。迁移完成后，目标表覆盖源表。
dict对象维护着哈希表的迁移状态:
typedef struct dict{
dictType *type;
void *privdata;
dictht ht[2];
long rehashindex;
int iterators;
} dict;
h[0]代表源表，也就是正常情况下访问的表。仅在迁移过程中，h[1]可用，作为目标表。此时首先访问源表，如果发现key对应的源表桶已经完成迁移，则重新访问目标表，否则在源表中操作。dict通过rehashindex记录已经完成迁移的桶。
ziplist实现
ziplist和List的ziplist实现类似，都是通过entry存放element。和List不同的是，map对应ziplist的entry个数总是2的整数倍，第奇数个entry存放key，key对应entry的下一个相邻entry存放该key对应的value。
ziplist实现的map，由hash遍历变成了链表的顺序遍历，复杂度变成O(N)。通常情况下，只有很少几个kv对的map采用ziplist效率反而更高，省去了hash计算、内存寻址等操作。长字符串的key，hash值计算本身的开销甚至远大于顺序遍历时字符串比较的开销。
