keys 是什么

简介

1. scan 复杂度为O（n）可带游标进行分步进行查询，不会阻塞线程
2. 可以进行模糊匹配和keys一样，只不过每一次都要带上一次返回的游标，可以使用limit限制最大条数，有可能少但是不会超过（http://doc.redisfans.com/key/scan.html#scan）
3. 每次根据游标返回的数据有可能为空也有可能为多个。只要返回的游标不为0，就不代表数据没有了。
4. 但是问题还是有的，就是有可能返回重复的key值这个得我们应用程序进行一次去重，可以使用set进行存储或者Map
   因为他两的数据结构本身就是不可以重复的。

SCAN 内部探究

1. redis 的全局就是使用的是key-value形式存储，使用的也就是他底层的数据结构dict字典。字典内部存储和java中的hashmap差不多，其底层都是通过数组和链表实现的。

2. 在dict中我们所存储的key就是底下的数组下标，数组下表是通过计算hash值出来的。正是因为有了hash冲突也就有了链表。

3. 在使用scan的时候我们其中scan的游标就是数组的下标，因为在存储的时候进行的是计算hash后进行存储，所以在数组上不是顺序存储，所以在一段数组上有可能有值也有可能没有值。也有可能一个slot上有多个值。所以这就是scan为什么会在增量式的过程中出现多个和0个的原因，如下图

    

   

4. 如果说按数组的下标顺序便利下去那要是扩容了怎么办，因为扩容之后需要进行进行重新hash，数组下标的位置就会改变，那么这个过程中我们我们在扩容之前scan返回的游标就不准确了吗？

5. redis处理扩容下表的方案是：它不是从第一维数组的第 0 位一直遍历到末尾，而是采用
   了高位进位加法来遍历。之所以使用这样特殊的方式进行遍历，是考虑到字典的扩容和缩容
   时避免槽位的遍历重复和遗漏。

6. 选择高位进位加法的主要原因还是他进行扩容的特点，和hashMap的差不多，采用的是：
   *Java 中的 HashMap 有扩容的概念，当 loadFactor 达到阈值时，需要重新分配一个新的
   2 倍大小的数组，然后将所有的元素全部 rehash 挂到新的数组下面。rehash 就是将元素的
   hash 值对数组长度进行取模运算，因为长度变了，所以每个元素挂接的槽位可能也发生了变
   化。又因为数组的长度是 2n（我们在进行扩容的时候其容量都为2n的原因） 次方，所以取模运算等价于位与操作。
    

   

抽象一点说，假设开始槽位的二进制数是 xxx，那么该槽位中的元素将被 rehash 到
0xxx 和 1xxx(xxx+8) 中。 如果字典长度由 16 位扩容到 32 位，那么对于二进制槽位
xxxx 中的元素将被 rehash 到 0xxxx 和 1xxxx(xxxx+16) 中。*

a mod 8 = a & (8-1) = a & 7
a mod 16 = a & (16-1) = a & 15
a mod 32 = a & (32-1) = a & 311

如下图就是缩容和扩容的一个对比

所以说redis采用了高位进位加法来遍历的。

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); Java 1.8计算hash的方法

7. 还有就是在进行扩容的时候，会进行copy和rehash，redis的数据量会很大，所以一次性进行rehash会出现卡顿问题。所以redis采用的是渐进式的rehash。也就是不一次性进行rehash 而是慢慢的继续进行，所以这也是scan乎过程中得注意的，也就新老dict 都进行扫描，最后合并返回。
8. 我们可以再想想keys 是不是就不用考虑以上问题呢？，因为他是每次都是全量扫，不担心扩容了等问题。