hash实现
redis的hash数据结构和java的HashMap虽然不同，但是有异曲同工之妙，value是键值对，相当于HashMap，对于hash碰撞也是采用的类似于HashMap的处理方式，数组+链表，更适合存储对象，将一个对象存储在hash类型中会占用更少的内存，且可以更方便的存取整个对象
编码格式
| 编码 | 对象 |
|---|---|
| OBJ_ENCODING_ZIPLIST | 使用ziplist |
| OBJ_ENCODING_HT | 使用的hash table |
set有两种编码格式
ziplist 一开始存储使用的ziplist，但是当满足一定条件时会转换为hash table hash table
#根据该配置项来进行编码转换的
# ziplist的节点数量限制
hash-max-ziplist-entries 512
# 键或者值的长度限制
hash-max-ziplist-value 64
源码结构
// 哈希表数据结构
typedef struct dict {
// 类型
dictType *type;
// 私有数据，存储一些额外的数据
void *privdata;
// 哈希表
// ht[0]:用来存放真是的数据
// ht[1]:用于扩容/缩容
dictht ht[2];
// 哈希表重置下标，指定的是哈希数组的数组下标
//rehash 如果为-1表示没有进行rehash，用来记录迁移的索引位置
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
// 如果大于0，则暂停rehash
int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;
typedef struct dictht {
// 哈希表数组，保存的是dictEntry结构的数据，就像HashMap中的Entry一样，存储的KV键值对
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码，用于计算索引值
unsigned long sizemask;
// 哈希表已有节点数量
unsigned long used;
} dictht;
typedef struct dictEntry {
// 键
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
// 下一个哈希节点，链表，为了解决哈希冲突问题，形成链表
struct dictEntry *next;
} dictEntry;
redis哈希冲突将新节点添加在链表的表头
过程分析
添加元素
向字典中添加元素，将会为字典中的ht[0]分配空间，默认情况下table数组为4(DICT_HT_INITIAL_SIZE)，新添加元素的键值会经过哈希算法确定哈希表数组的位置，进行添加，如果两个不同的键经过哈希算法产生相同的哈希值，就会发生哈希冲突，采用链表的方式，新元素会放到链表头节点(与java7类似，因为新增加的节点，大概率会被再次访问)
扩容
扩容的时候会将ht[0]的所有键值都迁移到h[1]中，当节点全部迁移完毕后，释放ht[0]的占用空间，并将ht[1]设置为ht[0]，由于redis中可能存的数据量比较大，所以进行rehash的时间可能会很长，而rehash又是一个阻塞的操作，所以redis采用的是渐进式的迁移方式，rehashidx就是为这个操作而设置的属性，用来记录索引位置的，默认为-1，当进行迁移的时候设置为0，每次接收到增加，删除，查找，更新命令时，除了执行该命令外，还需要将rehashidx索引上的节点迁移到ht[1]，迁移之后，rehashidx+1，当所有的数据都迁移到ht[1]中时，rehashidx会被重新设置为-1
本文由 mdnice 多平台发布
