问题描述

要求

测试代码

解决思路

Bitmap的构建

判断是否符合要求

性能对比测试

总结

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

小葵

2024-06-04

🏷

java面试题

问题描述

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

要求

密码强度要求如下:

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

测试代码

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) ,获取更多有趣的编程挑战题和技术干货!

友情链接:

Copyright© 2024 杭州园中葵科技有限公司 版权所有