scan会导致数据重复原因分析

一、分三种情况考虑

1、从迭代开始到结束,哈希表没有进行rehash

第一种情况 比较简单， hscan 扫描时，没有进行rehash ，正常返回游标结果。

2、从迭代开始到结束,哈希表进行了rehash,但是每次迭代时,哈希表要么没开始rehash,要么已经结束了rehash

第二种情况比较复杂。假设redis的哈希表大小为4,如果rehash完后size变成了8

按照公式  hash(key) & (size - 1) 的话，即如果size是4时,hash(key)&00000011
如果size是8时,hash(key)&00000111
因此当从4扩容到8时,原先在0bucket的数据会分散到0(000)与4(100)两个bucket。
原先1bucket 会分散到 1 和 5， 依次类推，当还是按照 原先的hash方法取数据的话，从bucket4 开始取到的都是重复数据。

3、从迭代开始到结束,某次或某几次迭代时哈希表正在进行rehash

第三种情况，如果返回游标1时正在进行rehash,ht[0]中的bucket 1中的部分数据可能已经rehash到 ht[1]中的bucket[1]或者bucket[5]，
此时必须将ht[0]和ht[1]中的相应bucket全部遍历,否则可能会有遗漏数据

二、分析完三种情况，如果想统一解决，必须要采取特别的措施了

    // 将游标v 的unmasked比特位都置为1
    // ~ 按位取反
    // & 按位与
    // | 按位或
    v |= ~m0;

    v = rev(v); // 反转v
    v++;        // v+1
    v = rev(v); // 再次反转v，即得到下一个游标值

备注，上面的公式是计算下一个游标的方法。比如第一个游标0，下一个计算后是2，2再计算下一个是 1，1再计算下一个是3，3再计算下一个是0

遍历size为4时的游标状态转移为0-2-1-3.

同理,size为8时的游标状态转移为0-4-2-6-1-5-3-7.

size为16时的游标状态转义为0-8-4-12-2-10-6-14-1-9-5-13-3-11-7-15

可以看出，当size由小变大时,所有原来的游标都能在大的hashTable中找到相应的位置,并且顺序一致,不会重复读取并且不会遗漏

但是当size由16变为了4 的时候，但如果游标返回的不是这四（0，2，1，3）,例如返回了10,10&11之后变为了2,所以会从2开始继续遍历.但由于size为16时的bucket2已经读取过,并且2,10,6,14都会rehash到size为4的bucket2,所以会造成重复读取

三、总结

redis里边rehash从小到大时，scan系列命令不会重复也不会遗漏.而从大到小时,有可能会造成重复但不会遗漏