用Java实现密码强度检查器(Bitmap高性能版本)

问题描述

编写一个函数，该函数接受一个字符串作为参数，检查该字符串是否符合密码强度要求，返回True或False。之前的版本使用正则表达式来实现密码强度检查，但是正则表达式的性能不够好，我们可以使用Bitmap来实现密码强度检查，提高性能。

要求

密码强度要求如下：

不能小于6个字符
必须出现大写、小写、数字、特殊字符（!@#$%^&*_-） 的组合
不能出现4个连续的字符，比如1234， dcba这样的规则

测试代码

assert is_password_strong('A1b@131') == True  # 符合所有条件
assert is_password_strong('abc123') == False # 缺少大写字母和特殊字符
assert is_password_strong('ABC!123') == False # 缺少小写字母
assert is_password_strong('aBc!123') == True  # 符合所有条件
assert is_password_strong('') == False        # 空字符串
assert is_password_strong('A') == False     # 长度不足
assert is_password_strong('Ab@1234') == False  # 不能顺序字符
assert is_password_strong('Ab@6543X') == False  # 不能顺序字符
assert is_password_strong('Ab@abcdf') == False  # 不能顺序字符
assert is_password_strong('Ab1@1212') == True  # 避免Abs出现1212都是连续1的情况

解决思路

用Bitmap来实现：Bitmap是一种位图数据结构，可以用来表示一个集合，每个元素用一个位来表示，可以用来快速判断一个元素是否在集合中。我们可以用Bitmap来表示密码中的字符，然后用位运算来判断是否符合要求。

我们知道所有的ascii都是0-128的数字，我们可以用一个128位的Bitmap来表示所有的ascii字符，每个字符对应一个位，如果该位为1，表示该字符在密码中出现过，否则为0。

为了识别是否都出现了对应的规则：大小写字母、数字、特殊字符，我们可以在Bitmap中存储"1<< 1", "1 << 2", "1 << 3", "1 << 4"，分别表示大小写字母、数字、特殊字符，然后用位运算来判断是否符合要求。

Bitmap的构建

    private static final int[] bitmaps = createBitmap();
    public static final int UPPER_CASE = 1 << 1;
    public static final int LOWER_CASE = 1 << 2;
    public static final int DIGIT = 1 << 3;
    public static final int SPECIAL_CHAR = 1 << 4;
    public static final int ALL = UPPER_CASE | LOWER_CASE | DIGIT | SPECIAL_CHAR;

    static int[] createBitmap() {
        int[] maps = new int[128];
        for (int i = 0; i < 128; i++) {
            if (i >= 65 && i <= 90) { // A-Z
                maps[i] = UPPER_CASE;
            } else if (i >= 97 && i <= 122) { // a-z
                maps[i] = LOWER_CASE;
            } else if (i >= 48 && i <= 57) { // 0-9
                maps[i] = DIGIT;
            } else if (i == 33 || i == 64 || i == 35 || i == 36 || i == 37 || i == 94 || i == 38 || i == 42 || i == 95
                    || i == 45) { // !@#$%^&*_
                maps[i] = SPECIAL_CHAR;
            }
        }
        return maps;
    }

这样就可以用Bitmap来表示密码中的字符，然后用位运算来判断是否符合要求。

判断是否符合要求

int hints = 0;
for (int i = 0; i < password.length(); i++) {
   char c = password.charAt(i);
   if (bitmaps[c] == 0) {
       return false;
   }
   int currentBit = bitmaps[c];
   hints |= currentBit;

   // 继续做连续字符的判断
   if (i < password.length() - 1) {
       int nextBit = bitmaps[password.charAt(i + 1)];
       int diff = c - password.charAt(i + 1);

       if (Math.abs(diff) == 1 && (prevDiff == 0 || prevDiff == diff)
               && ((currentBit & ALL) != 0) && currentBit == nextBit) {
           count++;
           prevDiff = diff;
           if (count >= 4) {
               return false;
           }
       } else {
           count = 1;
           prevDiff = 0;
       }
   }
}

if (hints != ALL) {
   return false;
}
return true;

通过一个循环遍历密码中的字符，如果出现bitmap == 0, 就表示不符合要求，否则就用hints |= currentBit来记录出现的字符

最后要求hints == ALL，表示所有的字符都出现了

这里有完整的代码: bitmap

性能对比测试

我们测试一下性能对比，使用1个密码，对比正则表达式和Bitmap的性能

        String password = "A1b@131";
        long start = System.currentTimeMillis();
        for (int i = 0; i < 10000000; i++) {
            checkPasswordStrengthWithBitmap(password);
        }
        long end = System.currentTimeMillis();
        System.out.println("checkPasswordStrengthWithBitmap Time: " + (end - start) + "ms for 10M iterations");
        long bitmapCost = end - start;

        start = System.currentTimeMillis();
        for (int i = 0; i < 10000000; i++) {
            PasswordChecker.checkPasswordStrength(password);
        }
        end = System.currentTimeMillis();
        System.out.println("checkPasswordStrengthWithRegex Time: " + (end - start) + "ms for 10M iterations");
        long regexCost = end - start;

        System.out.println("Regex cost: " + regexCost + "ms, Bitmap cost: " + bitmapCost + "ms");
        System.out.println("Bitmap is " + (regexCost / bitmapCost * 1.0) + " faster than Regex");

测试了一下输出的结果如下：

checkPasswordStrengthWithBitmap Time: 89ms for 10M iterations
checkPasswordStrengthWithRegex Time: 1200ms for 10M iterations
Regex cost: 1200ms, Bitmap cost: 89ms
Bitmap is 13.0 faster than Regex

发现竟然Bitmap的性能比正则表达式快了13倍，这是因为整个算法用了O(n)的时间复杂度，而正则表达式的时间复杂度是 4 * O(n)

总结

正则表达式的方案比较好维护，但是如果你需要考虑性能的时候，就可以用最简单的算法来实现，代码没有增加复杂度的情况下，可以提升一个数量级的性能。

所有的后端面试常见的问题，我们每天都会在我们的编程群里面讨论和Code review, 欢迎大家加入我们的编程群，一起学习和进步。

编程交流群

欢迎大家关注入职啦 (公众号: ruzhila) ，获取更多有趣的编程挑战题和技术干货！