Redis随机取数到底咋实现的，算法原理和细节深扒讲解

关于Redis随机取数是怎么实现的，我们得分开看，因为它针对不同的数据结构，用的方法不一样，这里主要讲两个最常用的场景：一个是随机取一个键（key），另一个是从一个集合（Set）或者哈希（Hash）里随机取一个或多个元素。

第一部分：随机取一个键（key），也就是 RANDOMKEY 命令

这个功能的实现，说白了，蒙着眼睛在数据库里瞎摸一个”，但Redis不能真的瞎摸，不然效率太低了，它的核心算法是一种叫做 “采样” 的方法，这个方法的原理在源码的 dict.c 文件中的 dictGetRandomKey 函数有体现。

想象一下，Redis的数据库就是一个大大的、有很多个抽屉的柜子（这些抽屉在技术上叫做“哈希桶”），每个抽屉里都放了若干把钥匙（也就是key），RANDOMKEY 的目标就是随机从任何一个抽屉里,随机拿一把钥匙出来。

它具体是这么“蒙眼摸”的：

1. 先随机选一个抽屉（哈希桶）： Redis首先会看看这个柜子总共有多少个非空的抽屉，然后它会产生一个随机数，这个随机数就像扔骰子一样，决定去开第几个非空抽屉，比如有5个非空抽屉，随机数如果是3,就去找第三个非空抽屉。
2. 再从选中的抽屉里随机拿一把钥匙： 打开这个抽屉后，发现里面可能挂着一串钥匙（因为可能有哈希冲突，多个key会被放到同一个桶里，用链表连起来），这时，Redis会再产生一个随机数，决定拿这串钥匙里的第几把，比如链表有4个key，随机数选到2,就拿第二个。
3. 处理空抽屉和扩容的特殊情况： 这里有个细节，如果Redis在第一步随机选中的那个抽屉碰巧是空的（可能在随机选择的那一刻，这个桶里的数据刚好被删光了），或者这个柜子正在扩容（数据正在从一个旧柜子往一个新柜子里搬），那上面的简单方法就可能出问题，比如一直选到空抽屉，或者漏掉一些数据。
   • 为了解决这个问题，Redis用了一个很聪明的办法：它不会轻易放弃。 如果第一次没摸到，它会设定一个尝试次数的上限（比如100次），在限定的次数内，不断地重复“随机选桶 -> 随机选链表节点”这个过程，直到成功摸到一个key为止，如果尝试了很多次都失败，它才会放弃，返回空值，这种方法在数学上能保证随机性是均匀的，而且效率很高,因为大多数情况下一两次就能成功。

RANDOMKEY 并不是遍历整个数据库（那样在数据量大的时候会慢死），而是通过这种有限次数的随机采样，既保证了随机性,又保证了速度。

第二部分：从集合（Set）或哈希（Hash）里随机取元素，也就是 SRANDMEMBER 或 HRANDFIELD

这个的实现和上面的 RANDOMKEY 有点像，但更直接，因为数据就在当前这个数据结构里,范围更小。

• 对于集合（Set）： Redis的Set底层有两种实现方式：一种是基于整数数组（intset），另一种是基于字典（hashtable）。
  • 如果Set用的是整数数组，那实现起来超级简单：直接生成一个随机数作为数组的索引下标，然后去这个下标的位置把元素取出来就行了，就像你有一个排好队的队伍，直接报“第5个出列”一样。
  • 如果Set用的是字典（哈希表），那它的做法就和前面讲的 RANDOMKEY 几乎一模一样了：在Set内部的这个哈希表上，进行“随机选桶 -> 随机选链表节点”的采样过程。
• 对于哈希（Hash）： 哈希结构本身底层就是哈希表，所以它的随机取字段名（field）的命令 HRANDFIELD，实现方式完全就是字典的随机采样，也就是和Set的第二种情况、以及 RANDOMKEY 的核心逻辑一致。

第三部分：随机取多个元素（带不重复和可重复选项）

当使用 SRANDMEMBER key [count] 命令，并且指定一个大于1的count值时，情况就更有趣了，Redis会根据你要的数量,选择不同的算法来优化性能：

• 当数量不大（你要的数量远小于集合总大小），且要求元素不重复时： Redis会用一个叫 “Knuth洗牌算法” 的变种，简单说，它并不是把整个集合都洗牌（那太浪费了），而是模拟洗牌的过程，从一个“牌堆”（集合）里，一张一张地、无放回地随机抽牌，直到抽够你需要的数量,这种方法能高效地保证抽出来的元素不重复。
• 当数量很大（接近或等于集合总大小），或者允许元素重复时： Redis会切换策略，如果数量等于集合大小，直接返回整个集合就行了，如果允许重复（count为负数时），那实现就更简单了：就是把你要求的次数（count的绝对值）重复执行“随机取一个元素”的操作，然后组合起来，因为允许重复,所以不需要做去重判断。

Redis随机取数的核心智慧在于 “随机采样” 而不是“全局遍历”，它充分利用了数据结构的特点（比如数组的索引、哈希表的桶），通过产生随机索引或进行哈希桶采样，在常数级或对数级的时间复杂度内就能完成任务，它还会根据数据量的大小、是否允许重复等条件，智能地选择最合适的底层算法（如洗牌算法或简单重复采样），在随机性、速度和内存开销之间取得最佳平衡,这些细节都体现了Redis作为高性能数据库在算法设计上的精巧之处。

（主要原理和细节参考自Redis源码中的 dict.c、t_set.c 等文件的相关函数实现，以及《Redis设计与实现》一书对数据结构的讲解。）