redis源码5--字典Dict：初始化api 及 rehash 相关api

本文先介绍字典的初始化相关api，以及rehash相关的函数，并以向字典添加key，value为例，介绍rehash如何在其中运行

和 rehash 相关的定义

// 指示字典是否启用 rehash 的标识
static int dict_can_resize = 1;
// 强制 rehash 的比率
static unsigned int dict_force_resize_ratio = 5;
dictEnableResize

手动开启自动 rehash

void dictEnableResize(void) {
   dict_can_resize = 1;
}
dictDisableResize

手动关闭自动 rehash

void dictDisableResize(void) {
  dict_can_resize = 0;
}

需要注意的是，并非所有 rehash 都会被 dictDisableResize 阻止：
如果已使用节点的数量和字典大小之间的比率，大于字典强制 rehash 比率 dict_force_resize_ratio ，那么 rehash 仍然会（强制）进行。

静态函数

//传入一个字典的指针，根据需要，初始化字典的哈希表，或者对字典现有的哈希表进行扩展
static int _dictExpandIfNeeded(dict *ht)
//计算第一个大于等于 size 的 2 的 N 次方，用作哈希表的大小
static unsigned long _dictNextPower(unsigned long size);
//传入字典的指针和键，返回可以将 key 插入到哈希表的索引位置，如果 key 已经存在于哈希表，那么返回 -1
//如果字典正在进行 rehash ，那么总是返回 1 号哈希表的索引。因为在字典进行 rehash 时，新节点总是插入到 1 号哈希表。
static int _dictKeyIndex(dict *ht, const void *key);
//初始化字典
static int _dictInit(dict *ht, dictType *type, void *privDataPtr);
//在字典不存在安全迭代器的情况下，对字典进行单步 rehash 
static void _dictRehashStep(dict *d)

主要函数

//传入一个哈希表指针，重置（或初始化）给定哈希表的各项属性值
static void _dictReset(dictht *ht)
//创建一个新的字典
dict *dictCreate(dictType *type,void *privDataPtr)
//缩小给定字典，让它的已用节点数和字典大小之间的比率接近 1:1
int dictResize(dict *d)
//创建一个新的哈希表，并根据字典的情况，选择以下其中一个动作来进行：
//(1),如果字典的 0 号哈希表为空，那么将新哈希表设置为 0 号哈希表
//(2),如果字典的 0 号哈希表非空，那么将新哈希表设置为 1 号哈希表，并打开字典的 rehash 标识，使得程序可以开始对字典进行 rehash
int dictExpand(dict *d, unsigned long size)
//执行 N 步渐进式 rehash。N是处理n个索引
int dictRehash(dict *d, int n)
//返回以毫秒为单位的 UNIX 时间戳
long long timeInMilliseconds(void)
//在给定毫秒数内，以 100 步为单位，对字典进行 rehash 。
int dictRehashMilliseconds(dict *d, int ms)
//尝试将给定键值对添加到字典中
int dictAdd(dict *d, void *key, void *val)
//尝试将键插入到字典中，不处理值，只将key插入字典中。并且条件允许会调用单步rehash
dictEntry *dictAddRaw(dict *d, void *key)

_dictReset

传入一个哈希表指针，重置（或初始化）给定哈希表的各项属性值

static void _dictReset(dictht *ht)
{
  ht->table = NULL;
  ht->size = 0;
  ht->sizemask = 0;
  ht->used = 0;
}

dictCreate

创建一个新的字典

dict *dictCreate(dictType *type,void *privDataPtr)
{
  dict *d = zmalloc(sizeof(*d));

  //初始化字典，是一个静态函数
  _dictInit(d,type,privDataPtr);

  return d;
}

_dictInit

初始化字典，是一个静态函数

 int _dictInit(dict *d, dictType *type, void *privDataPtr)
{
  // 初始化两个哈希表的各项属性值
  // 但暂时还不分配内存给哈希表数组
  _dictReset(&d->ht[0]);
  _dictReset(&d->ht[1]);

  // 设置类型特定函数
  d->type = type;

  // 设置私有数据
  d->privdata = privDataPtr;

  // 设置哈希表 rehash 状态
  d->rehashidx = -1;

  // 设置字典的安全迭代器数量
  d->iterators = 0;

  return DICT_OK;
}

dictResize

缩小给定字典，让它的已用节点数和字典大小之间的比率接近 1:1。
并不是将ht[0]的size减小就完事了，因为ht[0].table是一个连续的数组，而数据是散列的排布在上面，直接将ht[0]的size减小，可能会丢失数据。比如ht[0]的size为10，used为2，数据放在ht[0].table[0]和 ht[0].table[9]上，这时候进行dictResize，如果只是减小ht[0]的size值，那么ht[0].table[9]的数据就丢失了，所以正确的做法是进行 rehash，将数据移到到size变小的ht[1]上面
返回 DICT_ERR 表示字典已经在 rehash ，或者 dict_can_resize 为假
成功创建体积更小的 ht[1] ，可以开始 resize 时，返回 DICT_OK。

int dictResize(dict *d)
{
  int minimal;

  // 不能在关闭 rehash 或者正在 rehash 的时候调用
  if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;

  // 计算让比率接近 1：1 所需要的最少节点数量
  minimal = d->ht[0].used;
  if (minimal < DICT_HT_INITIAL_SIZE)
      minimal = DICT_HT_INITIAL_SIZE;

  // 调整字典的大小
  // T = O(N)
  return dictExpand(d, minimal);
}

_dictExpandIfNeeded

根据需要，初始化字典（的哈希表），或者对字典（的现有哈希表）进行扩展
此函数，在查找给定的key在字典中下标位置的时候被调用
T = O(N)

static int _dictExpandIfNeeded(dict *d)
{
  // 渐进式 rehash 已经在进行了，直接返回
  //在 dictExpand() 函数中也进行了判断，但是在dictExpand()中，如果 rehash 已经在进行，返回 DICT_ERR，和本函数返回值不同
  if (dictIsRehashing(d)) return DICT_OK;

  // 如果字典（的 0 号哈希表）为空，那么创建并返回初始化大小的 0 号哈希表
  // T = O(1)
  if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

  // 一下两个条件之一为真时，对字典进行扩展
  // 1）字典已使用节点数和字典大小之间的比率接近 1：1
  //    并且 dict_can_resize 为真
  // 2）已使用节点数和字典大小之间的比率超过 dict_force_resize_ratio
  if (d->ht[0].used >= d->ht[0].size &&
      (dict_can_resize || d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
  {
      // 新哈希表的大小至少是目前已使用节点数的两倍
      // T = O(N)
      return dictExpand(d, d->ht[0].used*2);
  }

  return DICT_OK;
}

dictExpand

创建一个新的哈希表，并根据字典的情况，选择以下其中一个动作来进行：
(1),如果字典的 0 号哈希表为空，那么将新哈希表设置为 0 号哈希表
(2),如果字典的 0 号哈希表非空，那么将新哈希表设置为 1 号哈希表，并打开字典的 rehash 标识，使得程序可以开始对字典进行 rehash。因为0号哈希表非空，并且哈希表的size变了，不管是变大还是变小，都需要进行rehash，将ht[0]的数据移到ht[1]中

size 参数不够大，或者 rehash 已经在进行时，返回 DICT_ERR 。成功创建 0 号哈希表，或者 1 号哈希表时，返回 DICT_OK 。

int dictExpand(dict *d, unsigned long size)
{
  // 新哈希表
  dictht n; /* the new hash table */

  // 根据 size 参数，计算新建哈希表的大小
  // T = O(1)
  unsigned long realsize = _dictNextPower(size);

  // 不能在字典正在 rehash 时进行。
  // size 的值也不能小于 0 号哈希表的当前已使用节点
  if (dictIsRehashing(d) || d->ht[0].used > size)
     return DICT_ERR;

  // 为哈希表分配空间，并将所有指针指向 NULL
  n.size = realsize;
  n.sizemask = realsize-1;
  // T = O(N)
  //table[i] 是一个指针，是dictEntry* 类型，所以为table数组分配内存的时候，大小是 realsize*sizeof(dictEntry*)
  n.table = zcalloc(realsize*sizeof(dictEntry*));
  n.used = 0;

  // 如果 0 号哈希表为空，那么这是一次初始化：
  // 程序将新哈希表赋给 0 号哈希表的指针，然后字典就可以开始处理键值对了。
  if (d->ht[0].table == NULL) {
      d->ht[0] = n;
      return DICT_OK;
  }

  // 如果 0 号哈希表非空，那么这是一次 rehash ：
  // 程序将新哈希表设置为 1 号哈希表，
  // 并将字典的 rehash 标识打开，让程序可以开始对字典进行 rehash
  d->ht[1] = n;
  d->rehashidx = 0;
  return DICT_OK;

  /* 顺带一提，上面的代码可以重构成以下形式：

  if (d->ht[0].table == NULL) {
      // 初始化
      d->ht[0] = n;
  } else {
      // rehash 
      d->ht[1] = n;
      d->rehashidx = 0;
  }
  return DICT_OK;
  */
}

_dictNextPower

计算第一个大于等于 size 的 2 的 N 次方，用作哈希表的值

static unsigned long _dictNextPower(unsigned long size)
{
  unsigned long i = DICT_HT_INITIAL_SIZE;

  if (size >= LONG_MAX) return LONG_MAX;
  while(1) {
    if (i >= size)
        return i;
    i *= 2;
  }
}

dictRehash

执行 N 步渐进式 rehash。N是处理n个索引
返回 1 表示仍有键需要从 0 号哈希表移动到 1 号哈希表，返回 0 则表示所有键都已经迁移完毕。
注意，每步 rehash 都是以一个哈希表索引（桶）作为单位的，一个桶里可能会有多个节点，被 rehash 的桶里的所有节点都会被移动到新哈希表。
rehash完成的标志是 ht[0].used = 0

int dictRehash(dict *d, int n) {

  // 只可以在 rehash 进行中时执行
  if (!dictIsRehashing(d)) return 0;

  // 进行 N 步迁移
  // T = O(N)
  while(n--) {
    dictEntry *de, *nextde;

    // 如果 0 号哈希表为空，那么表示 rehash 执行完毕
    // T = O(1)
    if (d->ht[0].used == 0) {
        // 释放 0 号哈希表
        zfree(d->ht[0].table);
        // 将原来的 1 号哈希表设置为新的 0 号哈希表
        d->ht[0] = d->ht[1];
        // 重置旧的 1 号哈希表
        //此函数只是让哈希表的table指向Null，并没有释放内存
        _dictReset(&d->ht[1]);
        // 关闭 rehash 标识
        d->rehashidx = -1;
        // 返回 0 ，向调用者表示 rehash 已经完成
        return 0;
    }

    // 确保 rehashidx 没有越界
    //当前要处理的是 ht[0].table[rehashidx]，ht[0].size是table数组的大小，所以rehashidx应始终小于 ht[0].size
    assert(d->ht[0].size > (unsigned)d->rehashidx);

    // 略过数组中为空的索引，找到下一个非空索引
    //不可能全都为空，因为ht[0].used 大于0
    while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;

    // 指向该索引的链表表头节点
    de = d->ht[0].table[d->rehashidx];

    // 将链表中的所有节点迁移到新哈希表
    // T = O(1)
    while(de) {
        unsigned int h;

        // 保存下个节点的指针
        nextde = de->next;

        // 计算新哈希表的哈希值，以及节点插入的索引位置
        //dictHashKey 是 宏定义函数，调用字典中的hash函数
        h = dictHashKey(d, de->key) & d->ht[1].sizemask;

        // 插入节点到新哈希表
        //d->ht[1].table[h] 是 dictEntry * 类型，指向头结点
        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;
    // 更新 rehash 索引
    d->rehashidx++;
  }

  return 1;
}

timeInMilliseconds

返回以毫秒为单位的 UNIX 时间戳

long long timeInMilliseconds(void) {
  struct timeval tv;

  gettimeofday(&tv,NULL);
  return (((long long)tv.tv_sec)*1000)+(tv.tv_usec/1000);
}

dictRehashMilliseconds

在给定毫秒数内，以 100 步为单位，对字典进行 rehash 。

int dictRehashMilliseconds(dict *d, int ms) {
  // 记录开始时间
  long long start = timeInMilliseconds();
  int rehashes = 0;

  //执行100 步 rehash
  while(dictRehash(d,100)) {
    rehashes += 100;
    // 如果时间已过，跳出
    if (timeInMilliseconds()-start > ms) break;
  }

  return rehashes;
}

_dictRehashStep

在字典不存在安全迭代器的情况下，对字典进行单步 rehash 。字典有安全迭代器的情况下不能进行 rehash ，因为两种不同的迭代和修改操作可能会弄乱字典。
这个函数被多个通用的查找、更新操作调用，它可以让字典在被使用的同时进行单步rehash ，将rehash的时间分散，减轻redis压力

static void _dictRehashStep(dict *d) {
  if (d->iterators == 0) dictRehash(d,1);
}

dictAdd

尝试将给定键值对添加到字典中，只有给定键 key 不存在于字典时，添加操作才会成功
最坏 T = O(N) ，平摊 O(1) 。时间消耗在内部调用dictAddRaw时，会再调用_dictKeyIndex()，查找key可以插入的索引位置，_dictKeyIndex()会再调用_dictExpandIfNeeded()，如果发现字典空间不够了，会再调用dictExpand()进行扩展的话，时间复杂度会加大。但平摊下来时间复杂度还是O(1)
接受的参数为一个字典类型的指针，一个key和一个val

int dictAdd(dict *d, void *key, void *val)
{
  // 尝试添加键到字典，并返回包含了这个键的新哈希节点
  // T = O(N)
  dictEntry *entry = dictAddRaw(d,key);

  // 键已存在，添加失败
  if (!entry) return DICT_ERR;

  // 键不存在，设置节点的值
  //这是宏定义函数，调用了字典的dictType 类型函数 
  // T = O(1)
  dictSetVal(d, entry, val);

  // 添加成功
  return DICT_OK;
}

dictAddRaw

尝试将键插入到字典中，接受的参数为一个字典类型的指针，一个key。只是将key插入字典中，并不处理值
如果键已经在字典存在，那么返回 NULL
如果键不存在，那么程序创建新的哈希节点，将节点和键关联，并插入到字典，然后返回节点本身。让接收返回值的函数处理该节点值

dictEntry *dictAddRaw(dict *d, void *key)
{
  int index;
  dictEntry *entry;
  dictht *ht;

  // 如果条件允许的话，进行单步 rehash
  // T = O(1)
  if (dictIsRehashing(d)) _dictRehashStep(d);

  // 计算键在哈希表中的索引值
  // 如果值为 -1 ，那么表示键已经存在
  // T = O(N)
  if ((index = _dictKeyIndex(d, key)) == -1)
    return NULL;

  // T = O(1)
  // 如果字典正在 rehash ，那么将新键添加到 1 号哈希表
  // 否则，将新键添加到 0 号哈希表
  ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
  // 为新节点分配空间
  entry = zmalloc(sizeof(*entry));
  // 将新节点插入到链表表头
  entry->next = ht->table[index];
  ht->table[index] = entry;
  // 更新哈希表已使用节点数量
  ht->used++;

  // 设置新节点的键
  // T = O(1)
  dictSetKey(d, entry, key);

  return entry;
}

_dictKeyIndex

静态函数。返回可以将 key 插入到哈希表的索引位置
如果 key 已经存在于哈希表，那么返回 -1
注意，如果字典正在进行 rehash ，那么总是返回 1 号哈希表的索引。 因为在字典进行 rehash 时，新节点总是插入到 1 号哈希表。
T = O(N)

static int _dictKeyIndex(dict *d, const void *key)
{
  unsigned int h, idx, table;
  dictEntry *he;
  
  //如果有需要，对字典进行扩展
  // T = O(N)
  if (_dictExpandIfNeeded(d) == DICT_ERR)
    return -1;

  // 计算 key 的哈希值
  h = dictHashKey(d, key);
  // T = O(1)
  for (table = 0; table <= 1; table++) {

    // 计算索引值
    idx = h & d->ht[table].sizemask;

    // 查找 key 是否存在
    // T = O(1)
    he = d->ht[table].table[idx];
    while(he) {
        if (dictCompareKeys(d, key, he->key))
            return -1;
        he = he->next;
    }

    // 如果运行到这里时，说明 0 号哈希表中所有节点都不包含 key
    // 如果这时 rehahs 正在进行，那么继续对 1 号哈希表进行 rehash
    if (!dictIsRehashing(d)) break;
  }

  // 返回索引值
  return idx;
}

总结

在调用dictCreate() 创建一个字典时，并没有立刻给字典中两个哈希表中的table数组分配内存，而是让size为0，而当调用dictAdd()向字典中添加元素时，如果发现ht[0].size为0，此时为ht[0].table分配内存，并将数据插入
在调用dictAdd()时，会调用 _dictKeyIndex() 来查找给定的key插入到哈希表时索引的位置，在_dictKeyIndex中，会调用 _dictExpandIfNeeded()，发现空间不够时，会对字典进行扩展，调用rehash，将数据从ht[0]移动到ht[1]
当rehash进行时，当对字典进行插入、删除、查找时，会进行安全的单步rehash，分散压力。并且，当rehash进行过程中，插入数据只会插入到ht[1]中

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 205,033评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 87,725评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,473评论 0赞 338
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,846评论 1赞 277
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,848评论 5赞 368
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,691评论 1赞 282
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,053评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,700评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 42,856评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,676评论 2赞 323
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,787评论 1赞 333
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,430评论 4赞 321
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,034评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,990评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,218评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,174评论 2赞 352
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,526评论 2赞 343