几乎所有的编程语言都提供了哈希类型，在不同的语言中又被称为字符表、字典、关联数组、映射等。在redis中，哈希类型是指键值本身又是一个键值对结构，类似value={{field1，value1}，{field2， value2}}，redis键值对和哈希类型关系如下图所示：
哈希数据结构基本命令
- 设置值： hset key field value
- 获取值： hget key field
- 删除键： hdel key field
- 判断field是否存在 hexist key field
- 获取所有value： hval key
- 获取所有field： hkeys key
- 获取所有field-value: hgetall user:1
hset user:1 name tom
hget user:1 name
tom
hdel user:1 name
hexists user:1 name
hkeys user:1
hvals user:1
当使用hgetall时，若哈希元素个数比较多，会存在阻塞redis的可能。
哈希类型的内部编码
ziplist（压缩列表）： 当哈希类型元素个数小于hash-max-ziplist-entries（默认512）并且所有值都小于64字节（hash-max-ziplist-value的默认配置），redis会采用ziplist作为哈希的内部实现，ziplist相比hashtable存储结构更紧凑，它是连续存储，更节省内存。但ziplist随着元素的增多，读写效率会下降。
hashtable（哈希表）： 当哈希类型不满足使用ziplist的条件时，redis会使用hashtable作为哈希的内部实现，hashtable相比ziplist读写效率更快，时间复杂度为O(1)。
127.0.0.1:6379> hmset key f1 v1 f2 v2
OK
127.0.0.1:6379> object encoding key
"ziplist"
127.0.0.1:6379> hset longkey f3 "my name is tracy i like playing basketball and love wangziyan very much, strive for success we can make it come on !!!! let us make big !!!!!!!!!!!!!! very long word enough greater than 64"
(integer) 1
127.0.0.1:6379> object encoding longkey
"hashtable"
127.0.0.1:6379>
可以看出，当field个数比较少且没有大的value时，内部编码为ziplist， 而当value大小大于64字节时，内部编码会由ziplist变为hashtable。（若field个数大于512内部编码也会由ziplist变为hashtable， 太长了，就不举例了）
哈希类型的使用场景
在关系型数据库中，我们通常使用一个记录来表示一条用户信息，每个字段代表用户的一个属性。
这其实可以通过哈希类型来缓存用户信息，而且表达的更加直观，操作也更快
由于哈希类型每个键可以有不同的field，一旦添加新的列，（比如，某些用户是vip，有些不同与普通用户的属性）不必像关系型数据库那样所有的记录都要添加新的列（没有该属性的也要设置为null）。而关系型数据库支持复杂关系查询，哈希类型去模拟这种复杂关系查询，维护成本较高。
提出一个问题
如果让你去缓存用户信息，有哪几种方式？
- 使用原生字符串类型， 每个属性作为一个键
127.0.0.1:6379> set user:1:name tracy
OK
127.0.0.1:6379> set user:1:age 25
OK
127.0.0.1:6379> set user:1:city hangzhou
OK
这种方式实现起来简单直观，每个属性都可以直接进行更新。但它占用了太多的键，内存消耗大，并且用户信息的内聚性差，因此，很少使用这种方法在生成环境。
- 使用序列化字符串类型，每条记录序列化后用一个键保存， set user:1 serialized(userInfo)。 合理使用序列化可以提高内存的使用率，但序列化和反序列化有一定的开销。
- 使用哈希类型，每个用户的属性使用field-value，一个用户对应一个键。
hmset user:1 name t-mac age 23 city hanzhoug
哈希类型实现简单直接，读写效率快，但需要控制哈希在ziplist和hashtable内部编码的转换。
总的来说，需要根据具体的业务场景来选择合适的方法！
Redis Rehash 内部实现
在Redis中，键值对（Key-Value Pair）存储方式是由字典（Dict）保存的，而字典底层是通过哈希表来实现的。通过哈希表中的节点保存字典中的键值对。类似Java中的HashMap，将Key通过哈希函数映射到哈希表节点位置。
接下来我们一步步来分析Redis Dict Reash的机制和过程。
(1) Redis 哈希表结构体：
/* hash表结构定义 */
typedef struct dictht {
dictEntry **table; // 哈希表数组
unsigned long size; // 哈希表的大小
unsigned long sizemask; // 哈希表大小掩码
unsigned long used; // 哈希表现有节点的数量
} dictht;
实体化一下，如下图所指一个大小为4的空哈希表（Redis默认初始化值为4）：
(2) Redis 哈希桶
Redis 哈希表中的table数组存放着哈希桶结构（dictEntry），里面就是Redis的键值对；类似Java实现的HashMap，Redis的dictEntry也是通过链表（next指针）方式来解决hash冲突：
/* 哈希桶 */
typedef struct dictEntry {
void *key; // 键定义
// 值定义
union {
void *val; // 自定义类型
uint64_t u64; // 无符号整形
int64_t s64; // 有符号整形
double d; // 浮点型
} v;
struct dictEntry *next; //指向下一个哈希表节点
} dictEntry;
(3) 字典
Redis Dict 中定义了两张哈希表，是为了后续字典的扩展作Rehash之用：
/* 字典结构定义 */
typedef struct dict {
dictType *type; // 字典类型
void *privdata; // 私有数据
dictht ht[2]; // 哈希表[两个]
long rehashidx; // 记录rehash 进度的标志，值为-1表示rehash未进行
int iterators; // 当前正在迭代的迭代器数
} dict;
总结一下：
- 在Cluster模式下，一个Redis实例对应一个RedisDB(db0);
- 一个RedisDB对应一个Dict;
- 一个Dict对应2个Dictht，正常情况只用到ht[0]；ht[1] 在Rehash时使用。
我们知道当HashMap中由于Hash冲突（负载因子）超过某个阈值时，出于链表性能的考虑，会进行Resize的操作。Redis也一样【Redis中通过dictExpand()实现】。我们看一下Redis中的实现方式：
/* 根据相关触发条件扩展字典 */
static int _dictExpandIfNeeded(dict *d)
{
if (dictIsRehashing(d)) return DICT_OK; // 如果正在进行Rehash，则直接返回
if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE); // 如果ht[0]字典为空，则创建并初始化ht[0]
/* (ht[0].used/ht[0].size)>=1前提下，
当满足dict_can_resize=1或ht[0].used/t[0].size>5时，便对字典进行扩展 */
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); // 扩展字典为原来的2倍
}
return DICT_OK;
}
...
/* 计算存储Key的bucket的位置 */
static int _dictKeyIndex(dict *d, const void *key)
{
unsigned int h, idx, table;
dictEntry *he;
/* 检查是否需要扩展哈希表，不足则扩展 */
if (_dictExpandIfNeeded(d) == DICT_ERR)
return -1;
/* 计算Key的哈希值 */
h = dictHashKey(d, key);
for (table = 0; table <= 1; table++) {
idx = h & d->ht[table].sizemask; //计算Key的bucket位置
/* 检查节点上是否存在新增的Key */
he = d->ht[table].table[idx];
/* 在节点链表检查 */
while(he) {
if (key==he->key || dictCompareKeys(d, key, he->key))
return -1;
he = he->next;
}
if (!dictIsRehashing(d)) break; // 扫完ht[0]后，如果哈希表不在rehashing，则无需再扫ht[1]
}
return idx;
}
...
/* 将Key插入哈希表 */
dictEntry *dictAddRaw(dict *d, void *key)
{
int index;
dictEntry *entry;
dictht *ht;
if (dictIsRehashing(d)) _dictRehashStep(d); // 如果哈希表在rehashing，则执行单步rehash
/* 调用_dictKeyIndex() 检查键是否存在，如果存在则返回NULL */
if ((index = _dictKeyIndex(d, key)) == -1)
return NULL;
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
entry = zmalloc(sizeof(*entry)); // 为新增的节点分配内存
entry->next = ht->table[index]; // 将节点插入链表表头
ht->table[index] = entry; // 更新节点和桶信息
ht->used++; // 更新ht
/* 设置新节点的键 */
dictSetKey(d, entry, key);
return entry;
}
...
/* 添加新键值对 */
int dictAdd(dict *d, void *key, void *val)
{
dictEntry *entry = dictAddRaw(d,key); // 添加新键
if (!entry) return DICT_ERR; // 如果键存在，则返回失败
dictSetVal(d, entry, val); // 键不存在，则设置节点值
return DICT_OK;
}
继续dictExpand的源码实现：
int dictExpand(dict *d, unsigned long size)
{
dictht n; // 新哈希表
unsigned long realsize = _dictNextPower(size); // 计算扩展或缩放新哈希表的大小(调用下面函数_dictNextPower())
/* 如果正在rehash或者新哈希表的大小小于现已使用，则返回error */
if (dictIsRehashing(d) || d->ht[0].used > size)
return DICT_ERR;
/* 如果计算出哈希表size与现哈希表大小一样，也返回error */
if (realsize == d->ht[0].size) return DICT_ERR;
/* 初始化新哈希表 */
n.size = realsize;
n.sizemask = realsize-1;
n.table = zcalloc(realsize*sizeof(dictEntry*)); // 为table指向dictEntry 分配内存
n.used = 0;
/* 如果ht[0] 为空，则初始化ht[0]为当前键值对的哈希表 */
if (d->ht[0].table == NULL) {
d->ht[0] = n;
return DICT_OK;
}
/* 如果ht[0]不为空，则初始化ht[1]为当前键值对的哈希表，并开启渐进式rehash模式 */
d->ht[1] = n;
d->rehashidx = 0;
return DICT_OK;
}
...
static unsigned long _dictNextPower(unsigned long size) {
unsigned long i = DICT_HT_INITIAL_SIZE; // 哈希表的初始值：4
if (size >= LONG_MAX) return LONG_MAX;
/* 计算新哈希表的大小：第一个大于等于size的2的N 次方的数值 */
while(1) {
if (i >= size)
return i;
i *= 2;
}
}
总结一下具体逻辑实现：
可以确认当Redis Hash冲突到达某个条件时就会触发dictExpand()函数来扩展HashTable。
DICT_HT_INITIAL_SIZE初始化值为4，通过上述表达式，取当42^n >= ht[0].used2的值作为字典扩展的size大小。即为：ht[1].size 的值等于第一个大于等于ht[0].used*2的2^n的数值。
Redis通过dictCreate()创建词典，在初始化中，table指针为Null，所以两个哈希表ht[0].table和ht[1].table都未真正分配内存空间。只有在dictExpand()字典扩展时才给table分配指向dictEntry的内存。
由上可知，当Redis触发Resize后，就会动态分配一块内存，最终由ht[1].table指向，动态分配的内存大小为：realsizesizeof(dictEntry)，table指向dictEntry的一个指针，大小为8bytes（64位OS），即ht[1].table需分配的内存大小为：82*2^n （n大于等于2）。
Redis哈希表的实现要点
哈希算法的选择
针对不同的key使用不同的hash算法，如对整型、字符串以及大小写敏感的字符串分别使用不同的hash算法；
整型的Hash算法使用的是Thomas Wang's 32 Bit / 64 Bit Mix Function ，这是一种基于位移运算的散列方法。基于移位的散列是使用Key值进行移位操作。通常是结合左移和右移。每个移位过程的结果进行累加，最后移位的结果作为最终结果。这种方法的好处是避免了乘法运算，从而提高Hash函数本身的性能。
unsigned int dictIntHashFunction(unsigned int key)
{
key += ~(key << 15);
key ^= (key >> 10);
key += (key << 3);
key ^= (key >> 6);
key += ~(key << 11);
key ^= (key >> 16);
return key;
}
一个好的hash算法需要满足两个条件：
- 性能高，运算足够快；
- 相邻的数据hash后分布广；即使输入的键是有规律的，算法仍然能给出一个很好的随机分布性；
比如：murmur计算"abc"是1118836419，"abd"是413429783。而使用Horner算法，"abc"是96354， "abd"就比它多1（96355）；
rehash
负载因子 = 当前结点数/桶的大小，超过1表示肯定有碰撞了；碰撞的结点，通过链表拉链起来；
所有哈希表的初始桶的大小为4，根据负载因子的变化进行rehash，重新分配空间（扩展或收缩）
当hash表的负载因子超过1后，进行扩展（小于0.01时，进行收缩）；
所谓扩展，就是新建一个hash表2，将桶的数量增大（具体增大为：第一个大于等于usedSize的2的n次冥）；然后将hash表1中结点都转移到hash表2中；
rehash的触发条件：
当做BGSAVE或BGREWRITEEOF时，负载因子超过5时触发rehash，
没有BGSAVE或BGREWRITEEOF时，负载因子超过1时触发rehash；
在BGSAVE或BGREWRITEEOF时，使用到Linux的写时复制，如果这时候做rehash，将会好用更多的内存空间（没有变化的结点用一份，变化的结点复制一份）
渐进式rehash
一个hash表中的数据可能有几百上千万，不可能一次rehash转移完，需要分批逐渐转移；
在rehash的过程中，对redis的查询、更新操作首先会在hash0中查找，没有找到，然后转到hash1中操作；
对于插入操作，直接插入到hash1中；最终目标是将hash表0变为空表，rehash完成；
value的存储
键值对的实现，value 是一个union，对整型和字符串使用不同的存储对象；
// 键
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
