Redis哈希表的迭代与遍历
Redis中对于哈希表的迭代与遍历，是整个哈希表实现中最为巧妙，同时也是最复杂难以理解的一个部分， 相当一部分写法，很难揣测作者的意图。只能暂且根据Redis的整体功能来进行推测，当然笔者的推测无法保证完全的准确， 如果随着对代码理解的深入，笔者会随时更新对这部分内容的理解。
Redis哈希表的随机采样
在Redis中，给出了两个接口函数用于对哈希表进行随机采样，不过作者自己也认为，这两个接口在采样数据分布的随机性上并不是特别的完善。
dictEntry* dictGetRandomKey(dict *d);unsigned int dictGetSomeKeys(dict *d, dictEntry **des, unsigned int count);
dictGetRandomKey
这个接口从名字上理解起来很简单，就是从哈希表中，随机的返回一个key-value元素， 其具体的算法为：
从所有的桶中，随机选择一个非空的桶。
从这个选定的桶中的链表里，随机返回一个元素。
可以看出，每个元素并不是等概率地被采样出来的，如果某个桶中的链表长度比较短的话，那么该桶中的元素，相比较与其他链表较长的桶的元素， 有更高的概率被dictGetRandomKey
这个接口所返回。
dictGetSomeKeys
这个接口用于从哈希表中，随机地获取给定count
数量的元素，当然作者也给出注释：
该接口无法保证，一定会获取到
count
个采样结果，最终的采样数量通过函数进行返回，这一点很好理解，当哈希表中的元素个数小于count
时， 该接口返回足够的采样数据。该接口无法保证，所返回的采样结果一定是没有重复的。
while(stored < count && maxsteps--) { for (j = 0; j < tables; j++) { if (tables == 2 && j == 0 && i < (unsigned long) d->rehashidx) { if (i >= d->ht[1].size) i = d->rehashidx; else continue; } if (i >= d->ht[j].size) continue; /* Out of range for this table. */ dictEntry *he = d->ht[j].table[i]; if (he == NULL) { emptylen++; if (emptylen >= 5 && emptylen > count) { i = random() & maxsizemask; emptylen = 0; } } else { emptylen = 0; while (he) { *des = he; des++; he = he->next; stored++; if (stored == count) return stored; } } } i = (i+1) & maxsizemask; }
其基本逻辑为：
从两个哈希表中选取最大的
maxsizemask
，以此为依据生成随机索引。根据该随机索引，选择对应的桶，将该桶中的元素尽可能的加入到返回结果中，如果达到
count
的数量，那么直接结束调用。如果没有达到所需的
count
，那么选择下一个桶进行采样，i = (i+1) & maxsizemask;
。如果对应的桶为空，则选择下一个桶进行采样；如果连续五个桶都为空，则重新生成随机索引，这一步有可能会导致数据被重复采样。
如果生成的随机索引大于当前哈希表的
size
，则用该索引查看另外一个哈希表， 而第一步的maxsizemask
则可以保证随机索引在两个哈希表中至少有一个是有效的。如果对桶的采样超过
10 * count
的次数，则停止采样，防止Redis长时间的阻塞在这个调用中， 这也是导致该接口无法保证返回count
个采样结果的原因之一。
Redis中用于处理哈希表迭代器的操作接口
对于哈希表的迭代器，Redis给出了两种迭代器类型，
安全迭代器，运行迭代器在迭代的过程中进行数据插入，查找，以及其他操作。
非安全迭代器，在迭代过程中只能调用
dictNext()
操作，也就是在迭代过程中禁止对哈希表进行改变。
dictIterator *dictGetIterator(dict *d);dictIterator *dictGetSafeIterator(dict *d);dictEntry *dictNext(dictIterator *iter);void dictReleaseIterator(dictIterator *iter);
上面的四个函数便是Redis哈希表迭代器的接口，dictGetIterator
会获取一个哈希表的非安全迭代器， 而dictGetSafeIterator
通过调用dictGetIterator
函数，同时dictIterator.safe
设置为1，来获取一个哈希表的安全迭代器。
dictNext
接口是哈希表迭代器的迭代接口，其具体的使用方式为：
dictEntry* de = NULL; while((de = dictNext(iterator)) != NULL) { //handle dictEntry }
对于迭代器的第一次迭代：
非安全迭代器会从关联哈希表当前的状态计算出一个指纹值，将之复制给
dictIterator.fingerprint
，用于防止在迭代中对哈希表的错误使用，会在迭代器释放时，对哈希表的指纹值进行校验。安全迭代器则会对
dict.iterators
字段执行加1的操作，如果dict.iterators
大于零，那么原本在添加、查找操作中进行的单步重哈希就不会进行。
dictReleaseIterator
用来释放一个迭代器，如果释放的是非安全迭代器，那么在释放时，会重新计算哈希表的指纹，将其与之前存储的指纹进行比较，如果不一致，则会触发断言机制；如果是安全迭代器，怎么将关联的哈希表的dict.iterators
字段减1，当这个字段减到0的话，那么就可以继续在添加，查找，删除的操作中继续执行单步重哈希操作_dictRehashStep
。
为什么单步重哈希_dictRehashStep
需要判断关联安全迭代器的数量，而心跳中的dictRehashMilliseconds
则不需要？
这里作者没有给出解释，我个人的猜测是由于Redis对于核心数据的操作都是单线程模式进行的， 心跳中的dictRehashMilliseconds
，在执行时，会阻塞Redis的核心主线程，此时不会对于哈希表有其他的操作，因此不需要判断关联安全迭代器的数量。而对于哈希表的迭代器，在迭代的过程中有可能基于逻辑的需求而对哈希表进行增加，查找等操作，故此需要判断关联安全迭代器的数量。当然上述解释，是笔者的个人见解，如果后续发现和此处有矛盾的地方，会做特别说明和补充。
Redis中用于扫描哈希表的操作接口
unsigned long dictScan(dict *d, unsigned long v, dictScanFunction *fn, dictScanBucketFunction *bucketfn, void *privdata);
这段代码，作者自己的评价是：
somewhat hard to understand at first
也就是第一次看，很令人费解。
想要理解这段代码，必须要先了解Redis的SCAN命令：
SCAN命令以及相关SSCAN，HSCAN和ZSCAN命令都用于增量迭代一个集合元素
该组命令每次调用都会以O(1)的时间复杂度来返回若干结果，以O(N)的时间复杂度完成整个迭代。
SCAN命令是一个基于游标的迭代器。这意味着命令每次被调用都需要使用上一次这个调用返回的游标作为该次调用的游标参数，以此来延续之前的迭代过程 当SCAN命令的游标参数被设置为0时， 服务器将开始一次新的迭代， 而当服务器向用户返回值为0的游标时， 表示迭代已结束。
这个SCAN系列命令可以保证：
如果某个key从扫描开始到扫描结束时，都存在于哈希表中，那么它一定会在某一次或几次迭代调用SCAN命令时被返回。
如果某个key，在还未被SCAN命令返回前就被删除，那么它将不会出现在后续的SCAN命令返回结果里。
如果某个key，在扫描过程中被添加到哈希表中，那么Redis不保证在后续的SCAN命令结果中一定会返回这个key。
按照正常的理解，遍历应该按照0->1->2->3->...这样的顺序来进行的，但是Redis对哈希表的扫描却不是按照这个顺序进行的， 以拥有8个桶且没有在重哈希过程中的哈希表来说，其扫描的顺序为0->4->2->6-1->5->3->7->0，如果对于这个扫描顺序没有头绪的话， 那么将其转化为二进制来看一下，000->100->010->110->001->101->011->111->000，我们其扫描顺序的规律：
从0开始，高位加1
向地位进位，到0结束
那么为什么Redis要使用如此抽搐的扫描方式呢？
其原因在于，对于哈希表的扫描，不是一次性完成的，而是客户端通过调用SCAN命令增量地进行的，而在这个过程中，有可能会发生哈希表的重哈希操作， 如果采用*0->1->2->3->...*这样的扫描顺序，则有可能漏掉某些元素，或者对某些元素进行了重复扫描。重复扫描可以通过客户端自己维护一个数据集合， 来对重复数据进行过滤，但是如果某些元素被漏掉，那么则有可能会产生一些错误。
为什么这种跳跃的扫描方式可以避免元素被遗漏呢？
对于没有处于重哈希过程中的哈希表，这种方法可以被理解为是递增操作在二进制上的反方向操作，虽然采用跳跃的方式进行， 但是可以明确的是，这种方法也可以覆盖对所有桶的遍历。
如果对于处于重哈希过程中的哈希表，首先便是底层会有两个哈希表用于增量的重哈希，而SCAN扫描需要覆盖到这两个底层的哈希表。同时在增量重哈希的过程中，哈希表中的元素也存在从多个桶向一个桶汇集（缩容）或者从一个桶向多个桶扩散（扩容）的过程。这也就要求，不能因为数据的迁移，而导致某些数据在扫描过程中被遗漏。
首先，我们需要明确的一点是，Redis中桶的个数一定是2的n次方个：
如果从4个桶扩容到16个桶，那么0号桶中的元素，也就是二进制
00
中的元素一定会被分散到0000
、1000
、0100
和1100
这四个桶中， 也就是0号桶、8号桶、4号桶以及12号桶中。如果从16个缩容到4个桶，那么0号桶、8号桶、4号桶以及12号桶中的元素，也就是
0000
、1000
、0100
和1100
中的元素会被 集中到新的00
这个桶中，也就是新的0号桶中。
从上面的图示，我们可以发现，给定一个桶，在扩容过程中，桶中元素分散的目标桶一定是固定的；同时在缩容的过程中，这个桶也一定会从若干个固定的桶中收集元素。而这其中数量较多那组桶， 其编号恰巧满足高位加1，同时向低位进位这一规律。这似乎隐约可以体会出，Redis作者使用这个跳跃的扫描方式的目的了。
t0 = &d->ht[0]; t1 = &d->ht[1]; if (t0->size > t1->size) { t0 = &d->ht[1]; t1 = &d->ht[0]; } m0 = t0->sizemask; m1 = t1->sizemask; if (bucketfn) bucketfn(privdata, &t0->table[v & m0]); de = t0->table[v & m0]; while (de) { next = de->next; fn(privdata, de); de = next; } do { if (bucketfn) bucketfn(privdata, &t1->table[v & m1]); de = t1->table[v & m1]; while (de) { next = de->next; fn(privdata, de); de = next; } v |= ~m1; v = rev(v); v++; v = rev(v); } while (v & (m0 ^ m1));
通过上述代码片段，我们可以发现，每次给定一个游标对正在重哈希的哈希表进行扫描的时，总是会先访问小哈希表中对应索引的桶， 然后在访问较大哈希表中对应的若干个桶，这样也就保证了，无论是扩容还是缩容，我们总能扫描到所有的元素，当然这也是为什么会出现元素被重复扫描的原因。
