java - Java 中不使用数组的排列

Question

下面的代码循环遍历所有提交的字符，将它们放入字符串数组中，然后对它们进行哈希处理后，检查最初输入的哈希密码。此逻辑适用于最多 5 个字符的密码，但是当我达到 6 个字符时，排列数量 (36^6) 太大，以至于由于数组的大小太大而引发内存异常。

因此，我也尝试修改它，仅使用字符串而不是数组来阻止此内存问题，但无法完全使其正常工作，有什么明显的建议吗？

Answer 1

您可以通过从 0 数到无穷大并转换数字 toString 来枚举所有可能包含字母和数字的密码。以 36 为基数。

long k = 0;
while (true) {
    String pwd = Long.toString(k++, 36);
    if (SHA1(pwd).equals(hashedPassword)) {
        System.out.println(pwd);
    }
}

这里，toString 适用于最大 36 的基数，使用 [0-9a-z]，即它适用于您的情况，但如果您想包括特殊字符，您将必须创建自己的数字到密码函数(考虑除法和模数)，但其余部分保持不变。

这样，内存要求是 O(1)，但是对于最多 n 个字符的密码，复杂度当然仍然是 O(36ⁿ)。

<小时/>

这种方法的一个问题是——与所有数字表示一样——前导零将被省略，因此 Long.toString 永远不会生成以 0 开头的密码 code> (0 本身除外)。为了解决这个问题，您可以使用两个嵌套循环 - 外部循环迭代密码中的位数，内部循环迭代最多 36^d 的数字并用前导零填充字符串，或者从 36^d 循环到 2*36^d 并删除第一个(非零)数字。这看起来可能比以前多了很多工作，但实际上它只产生了两倍的密码。

for (int d = 1; d < 3; d++) {
    long p = pow(36, d);
    for (long n = p; n < 2 * p; n++) {
        String pwd = Long.toString(n, 36).substring(1);
        System.out.println(n + " " + pwd);
    }
}

输出:

0
1
...
z
00
01
...
zz