验证用户 ID 的线性全余生成器唯一性

Question

Id 要求：

• 短(供用户键入的字符 # 个(
• 允许尽可能多的 ID
• 看似随机(因此没有人可以通过id轻松猜测用户计数(
• 没有混合大小写字符(用户更容易键入(
• 不生成脏话

因此，我选择使用 6 个字符的大写字符串，而不使用根据用户计数排序的线性同余生成器生成的元音。我从维基上了解了 LCG，我想验证我的代码是否正确，因为我自己在 LCG 中编造了系数，并且讨厌 id 发生冲突。我尝试自己测试碰撞，但是在 200 万次之后将 id 存储在地图中时，我的堆空间用完了。我认为数学检查出来，但真的很感激第二双(或一千(双眼睛。(对JS也不是那么有经验，所以如果有更有效的方法来交换元音，很想知道(。

// UserId generated from stored userCount key in redis, sequenced by a Linear
// Congruental generator, and stringified with a radix of 31 (all numbers and
// letters besides vowels = 10 + 26 - 5 = 31).
//
// The equation we will use to generate the sequence is:
// userVal = (a * userCount + c) % m + minVal
// To guarantee each userId is at least 6 characters, we need:
// minVal = 31^5 = 28629151
//
// To guarantee that our userId is at most 6 characters, we need:
// log31(minVal + maxVal + 1) = 6
// => 31^6 = minVal + maxVal + 1
// => maxVal = 31^6 - minVal - 1 = 858874529
//
// So our LCG needs to have:
// 1) m < maxVal
// 2) m and c relatively prime
// 3) a-1 is divisible by 4 if m is
// 4) a-1 is divisible by all prime factors of m
//
// m = 858062848 = 2^16 * 13093
// c = 1
// a = 3351809 = 2^8 * 13093 + 1
//
// This means we can support 858062848 unique userIds (>850 million).
// If we ever cross that amount, it will be a good problem to solve :)
this.getUserId = function(){
    var userCount = Spark.getRedis().incr("unique-id:user");
    var a = 3351809;
    var c = 1;
    var m = 858062848;
    var minVal = 28629151;
    var userVal = (a * userCount + c) % m + minVal;
    return userVal.toString(31)
        .toUpperCase()
        .replace(/A/g, 'V')
        .replace(/E/g, 'W')
        .replace(/I/g, 'X')
        .replace(/O/g, 'Y')
        .replace(/U/g, 'Z');
};

Answer 1

我怀疑您在线性同余生成器的代码中引用的条件足以确保序列具有最大长度。但是，我相信这并不能保证生成的随机数具有良好的统计特性。LCG参数有一些"首选"选择，它们具有良好的统计特性(例如，连续数组之间的低相关性(，这些参数在数值配方(Press等(中列出。更详细的理论讨论在高德纳的计算机编程艺术中。