这种选择随机对象键的算法是如何工作的？(Math.random() < 1/++c)

Question

function randomKey(obj) {
    var ret;
    var c = 0;
    for (var key in obj)
        if (Math.random() < 1/++c)
           ret = key;
    return ret;
}

有人可以说明该代码如何公平从对象中选择一个随机键？

Answer 1

说您在obj中有三个键。在循环的第一次迭代中，1/++c将是1，因此ret将始终设置为第一个密钥。在第二次迭代中，1/++c等于0.5，因此生成的随机数将小于此的1/2概率，因此您将将ret更改为第二个键的50％的机会。在第三次迭代中，1/++c将为0.333 ...，因此ret将更改为第三个密钥的1/3概率。

对于obj中的任何尺寸集合，您应该最终获得均匀分布。