redis中一个db就是一个大dict，也就是实现的可伸缩hash表。其操作支持遍历scan类操作，按stl容器中场景的逻辑，如果一个迭代器在迭代过程中被修改(插入或删除)元素，迭代器可能失效。
redis中，由于在scan操作时，整个dict会有大量的增加和删除操作，如果失效迭代器重新遍历可能永远无法完成scan操作，所以其实现的scan遍历操作使用了Reverse Binary Iteration算法，意思是遍历的顺序递增操作是二进制反向的，也就是该数字递增是二进制高位加1，向低位进位。
因为dict的具体实现是通过索引找到bucket，bucket中可以容纳多个key，并且会进行rehash操作，要实现的目标是：
- 在迭代开始时刻起，没有被删除的key都能被遍历。
- 在迭代器rehash操作后，没有被删除的key尽可能少的被重复遍历。
dict的rehash长度是都是2倍增加或半数减少，在遍历过程中cursor的变化是采用反向二进制增加的，在hash长度为8和16时，cursor的增长如下：
8: 000 --> 100 --> 010 --> 110 --> 001 --> 101 --> 011 --> 111 --> 000
16: 0000 --> 1000 --> 0100 --> 1100 --> 0010 --> 1010 --> 0110 --> 1110 --> 0001 --> 1001 --> 0101 --> 1101 --> 0011 --> 1011 --> 0111 --> 1111 --> 0000
- rehash增长
如果cursor是2，在长度8的hash表中下标是010，在长度16的hash表中下标是0010和1010，这两个是相邻的，这个特性很重要，能够保证在rehash之后，0010之前的bucket都是已经遍历过的，不需要再重复遍历。在增长到16后，下次迭代的cursor为0110，所以不会漏掉也不会重复遍历。
- rehash缩小
在16缩小成8的情况下，当在长度16时，在迭代完成1010后，rehash成8大小，cursor变成010。在大小为16时已经完成0000，1000，0100，1100，0010和1010迭代，大小变为8后，为了防止漏掉bucket，下次迭代从010开始，0010和1010已经迭代过，所以会出现重复。
链接