java - 在给定字符串中搜索字符集的最快算法

Question

这是我和我的一个 friend 进行的一场辩论:什么是制作验证方法的最快方法来检查给定字符串是否包含不允许的字符之一

方法一:简单

char [] invalidChars = "!@#$%^...".toCharArray();
        for (int i = 0; i < myString.length(); i++) {
            char ch = myString.charAt(i);
            for (int j = 0; j < invalidChars.length; j++) {
                if (invalidChars[j] == ch) {
                    return false;
                }
            }
        }

方法二:利用 Map 的 O(1)

Map <String,String> map = new HashMap<String, String>();
        map.put("!", null);
        map.put("@", null);
        map.put("#", null);
        map.put("$", null);
        map.put("^", null);
        ...
        for (int i = 0; i < labels.length(); i++) {
            char ch = labels.charAt(i);
            if (map.containsKey(ch)) {
                return false;
            }
            return true;
        }

方法 I 实际上是 N2，但在 invalidChars 数量较少时与 N 一样好。当情况一:有很多无效字符，情况二:只有少数无效字符时，应该优先考虑什么？

注意:我不是在寻找任何内置的 Java 解决方案，而是在寻找过滤少数(不是全部)非文本字符的算法

Answer 1

如果您只对验证 ASCII 字符感兴趣，那么长度为 128 位的 boolean 查找表可能比上述任何一种方法都快。