1 公司代码出现的问题

请注意：本文出现的所有代码只模拟表单验证情况。

公司代码具有保密性以及其他授权鉴权、加密等内容，不方便贴出来，这里我就自己写一个demo复原一下源代码。

public static boolean register(User user) {
    if (user == null) {
        return false;
    }
    String match = "+- */!@#$%";
    for (int i = 0; i < user.getUserName().length(); i++) {
        for (int j = 0; j < match.length(); j++) {
            if (match.charAt(j) == user.getUserName().charAt(i)) {
                return false;
            }
        }
    }
    for (int i = 0; i < user.getPassword().length(); i++) {
        for (int j = 0; j < match.length(); j++) {
            if (match.charAt(j) == user.getPassword().charAt(i)) {
                return false;
            }
        }
    }
    return true;
}

该方法的时间复杂度为外层循环O(n)*内层循环O(m) = O(n * m)，其中 n 为 ‘user.getUserName()/user.getPassword()’ 字符串的长度，m 为违规字符匹配的长度。
该方法没有使用额外的数据结构来存储临时变量，所以空间复杂度是O(1)，即常量空间复杂度。

结论：时间复杂度为O(n * m)，空间复杂度为O(1)

问题：在账号密码登录场景中，通常n代表用户名或密码的长度，而m代表违规字符匹配的长度。双重嵌套循环的时间复杂度O(n * m)，可能会导致性能问题，特别是当用户名和违规字符串很长时，验证可能会变得非常缓慢。

我们可以尝试使用正则表达式去优化他

2 使用正则表达式实现

public boolean register(User user) {
    if (user == null) {
        return false;
    }
    String pattern = "[+\\- */!@#$%]";
    return !user.getUserName().matches(".*" + pattern + ".*")
            && !user.getPassword().matches(".*" + pattern + ".*");
}

我们可以看到的是，正则表达式相比原方法更加简洁，减少了循环遍历的复杂性。虽然在初学者看来，该方法在一定程度上会让代码看起来复杂，但对于熟悉正则表达式的人来说，代码的意图和功能会很清晰。
该方法的时间复杂度可以近似看作 O(n + m)，其中 n 是用户名长度，m 是密码长度，相比原方法的双重循环，存在优化。
该方法也没有使用额外的数据结构来存储临时变量，所以空间复杂度是O(1)，即常量空间复杂度。

结论：时间复杂度为O(n + m)，空间复杂度为O(1)

Java的正则表达式引擎使用的是NFA（Non-deterministic Finite Automaton）和DFA（Deterministic Finite Automaton）的混合匹配算法。这使得正则表达式能够支持一些复杂的特性，比如回溯和捕获组，但请注意，一些复杂的正则表达式，也会导致引擎需要进行更多的判断和分支来处理这些特性，性能则会出现下降，甚至可能达到恐怖的O( 2^n )。那么除了正则表达式，在面对简单的表单验证需求，还有没有其他的方法呢？自然是有的。

3 使用 String 类的 contains() 方法实现

public boolean register(User user) {
    if (user == null) {
        return false;
    }
    List<String> list = new ArrayList<>(Arrays.asList("+", "-", " ", "*", "/", "!", "@", "#", "$", "%"));
    for (String match : list) {
        if (user.getUserName().contains(match)) {
            return false;
        }
        if (user.getPassword().contains(match)) {
            return false;
        }
    }
    return true;
}   

方法中包含一个循环，循环的次数是list中元素的有限个数m，在每次循环中，使用Java String contains方法来检查用户名和密码中是否包含list中的元素，contains方法的时间复杂度是O(n)，其中m是字符串的长度。因此，循环的总时间复杂度是O(m + n)。
空间复杂度主要来自于创建的ArrayList对象，其大小与list中元素的个数相同，也就是10。所以，空间复杂度为O(10) = O(1)，因为它是一个固定大小的数据结构。

结论：时间复杂度为O(m + n)，空间复杂度为O(1)

该方法的代码逻辑相对简单，容易理解和维护，后续有新的违规字符仅需添加进list即可。

4 使用 HashSet 哈希表实现

/**
  * 使用HashSet存储输入字符串中出现的字符，以便后续匹配验证。
  */
 private final HashSet<Character> charSet;

 /**
  * 构造函数，在对象创建时初始化charSet为一个新的空HashSet。
  */
 public RegisterFormValidator() {
     charSet = new HashSet<>();
 }

 /**
  * 将输入的字符串中的字符逐个添加到charSet中。
  * @param inputString 输入的字符串
  */
 public void addCharsToSet(String inputString) {
     for (char c : inputString.toCharArray()) {
         charSet.add(c);
     }
 }

 /**
  * 验证给定的匹配字符串是否与用户的用户名和密码匹不匹配。
  * 如果匹配字符串中的任何字符在charSet中出现，返回false，表示不匹配；否则返回true，表示匹配。
  * @param match 违禁字符
  * @param user 用户信息
  * @return 结果集
  */
 public boolean isMatch(String match, User user) {
     addCharsToSet(user.getUserName());
     addCharsToSet(user.getPassword());
     for (char c : match.toCharArray()) {
         if (charSet.contains(c)) {
             return false;
         }
     }
     return true;
 }

该方法需要遍历用户名和密码中的字符，将其添加到 HashSet 中。假设用户名的长度为 n，密码的长度为 m，则该方法的时间复杂度近似为 O(n + m)，相比于其他方法，该方法在字符查找方面更高效。
该方法使用了一个 HashSet 来保存用户名中的字符。由于特定字符集是固定的，并且字符集长度为常数，添加到 HashSet 中的不同字符个数最多为常数。因此，该方法的空间复杂度为 O(1)，即常量级别。

结论：时间复杂度为O(m + n)，空间复杂度为O(1)。综合来看，哈希表是一个相对高效且简洁的解决方案，与其余方法相比，在时间复杂度和性能方面有一定优势，稳定性也相对较高。

综上，是本人目前所能想到的较为实用的表单验证方法，如果读者有更好的办法，也希望能互相分享新的知识。当然，还需要指出的是，对于方法的稳定性评估并不仅仅取决于时间复杂度和空间复杂度，还受到实际应用场景的影响。不同的输入数据规模、特殊字符集的大小、硬件环境等因素都可能对方法的性能产生影响。因此，为了选择最合适的方法，最好是根据具体的需求和实际情况，通过实际测试来进行评估。在实际应用中，可能需要考虑更多因素，如安全性、可维护性、易用性等，综合权衡后做出最优选择。

最后附上本文所写源代码：表单验证的实现与优化

YouFeng

优化 Java 表单验证