声明：本博客内容来自《Redis深度历险》本书，http://www.Sina.com/http://www.Sina.com/redis上的所有key都保存在一个大词典里。 本词典的结构与Java的HashMap一样，是一维数组的二维链表结构，本词典的结构为一维数组的大小总是2^n(n=0)，一次扩展大小的组大小空间加倍。 即，n scan命令返回的光标是第1维数组的位置索引，将该位置索引称为槽(slot )。 如果不考虑词典的扩展缩小的话，直接按照数组的下标顺序扫描就可以了。 limit参数表示需要遍历的插槽数。 返回的结果可能很多，也可能不多，这是因为并非所有插槽都安装了链表，有些插槽可能为空，而有些插槽中可能有多个链表元素。 对于每个遍历，对挂接在limit数量的插槽中的所有链表元素进行模式匹配过滤，然后一次返回给客户端http://www.Sina.com/http://www.Sina.com/http://Sina.com/com 不是从一维排列的第0位扫描到末尾，而是使用上位位数的进位加法进行扫描。 使用这种特殊的方式进行扫描是为了在考虑到词典的扩展和缩小的情况下，避免槽位的扫描重复和缺失。字典的上位进位法从左开始加法，进位向右移动，但与通常的加法正好相反。 但是，最终遍历所有时隙位，在http://www.Sina.com/http://www.Sina.com/Java的HashMap中有扩展概念。 loadFactor达到阈值后，必须重新分配两倍大的新数组，并将所有元素乘以rehash。rehash是指根据数组长度对元素的hash值进行模运算。 由于长度发生了变化，挂在各要素上的插槽的位也有可能发生了变化。 另外，由于数组的长度为2^n次幂，所以模运算是将位操作amod8=a(8-1) a7amod16=a ) 16-1 ) a15amod32=a ) 32-1 ) a31这里的7、15、31作为辞典的mmm 接下来，我们来看看rehash前后的要素时隙比特的变化。 当当前词典的数组长度从8位扩展到16位时，第三个时隙位011从rehash扩展到第三个时隙位和第十一个时隙位。 这意味着，该时隙位链表中约一半的元素仍然是第三个时隙位，其他元素位于第11个时隙位。 11这个数字的二进制数是1011，是在3的二进制数011上加上了前1。 如下图所示进行抽象时，假设开始时隙位二进制数为xxx，则该时隙位的要素为从rehash到0XX和1XXX (在辞典的长度从16位扩展到32位的情况下，二进制时隙的位xxxx内的要素为rehash 在1xxxx(xxxx16 )的结构 中查看此图，可以看到，无论是扩展还是缩小，rehash之后的插槽的位扫描顺序都采用高位进位加法的扫描顺序
10 这个位置 ( 橙色 ) 扩容后，当前槽位上所有的元素对应的新槽位是 0110 和 1110( 深绿色 ) ，也就是在槽位的二进制数增加一个高位 0 或 1 。这时我们可以直接从 0110 这个槽位开始往后继续遍历，而 0110 槽位之前的所有槽位都是已经遍历过的，这样就可以避免扩容后对已经遍历过的槽位进行重复遍历 假设当前要即将遍历 110 这个位置 ( 橙色 ) 缩容后，当前槽位所有的元素对应的新槽位是 10( 深绿色 ) ，也就是去掉槽位二进制最高位。这时我们可以直接从 10 这个槽位继续往后遍历，10 槽位之前的所有槽位都是已经遍历过的，这样就可以避免缩容的重复遍历。不过缩容还是不太一样，它会对图中 010 这个槽位上的元素进行重复遍历，因为缩融后 10 槽位的元素是 010 和 110 上挂接的元素的融合， 注意：这也是为什么scan命令可能会返回重复key的根本原因！ 渐进式 rehash Java 的 HashMap 在扩容时会一次性将旧数组下挂接的元素全部转移到新数组下面。如果 HashMap 中元素特别多，线程就会出现卡顿现象 Redis 为了解决这个问题，它采用渐进式 rehash 。它会同时保留旧数组和新数组，然后在定时任务中以及后续对 hash 的指令操作中渐渐地将旧数组中挂接的元素迁移到新数组上。这意味着要操作处于 rehash 中的字典，需要同时访问新旧两个数组结构。如果在旧数组下面找不到元素，还需要去新数组下面去寻找。scan也需要考虑这个问题，对与 rehash 中的字典，它需要同时扫描新旧槽位，然后将结果融合后返回给客户端。