最快的算法，用于搜索给定字符串中的字符集
这是我和我的一个朋友之间的争论：制作一个valiation方法的最快方法是检查给定的字符串是否有一个不允许的字符
方法一：简单
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; } } } 方法二：利用地图的O（1）
Map map = new HashMap(); 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解决方案，而只是用于过滤少数（非全部）非文本字符的算法
如果您只对validationASCII字符感兴趣，那么长度为128的布尔查找表可能比上述任何一种方法都快。
有一种简单的方法可以给你O(n log(m))时间复杂度，其中n是输入的长度， m是不允许的字符数。
一次扫描输入的一个字符，并使用二进制搜索在不允许的字符的（已排序）数组中查找当前字符。
如果您使用HashSet，它为您添加O（1）并包含您：
- O（n）用于插入每个禁用的字符
- 每次比较操作的O（m）
这导致O（m + n），其中m是禁止字符的数量，n是字符串的长度。 但我已经看到了表现更好的答案。
但请记住，大多数事情都有开销（比如HashSet / HashMap中的“哈希”）。 因此，即使渐近性能可能更好，但对于小输入， 天真的实现可能会更快 。 我不是说你应该使用具有O（n²）的东西，但是对于一组通用数据，将O（n log n）解决方案与O（m）解决方案进行比较可能是值得的！
最快的！ HashMap是最快的解决方案，理论上它只是O（1）。
在java中： java.util.BitSet是为您的需求而设计的。 或者使用self unwrapped long [] / int []数组（取决于目标体系结构32/64）
为什么HashMap不好？ 来自访问和创建桶的额外行李高于其右侧的查找。
构造一个hashmap并将项目放在那里相对昂贵。 但是，正如您所说，在哈希映射中查找项目是O（1）。
所以我们有hashmap填充：O（n log n）和查找O（1）。
或标准方式（填写O（1）查找O（n））。
然而，由于O（n）查找发生在每个字符串中，所以第一个方法总共是O（numberOfInvalidChars + strings * NumberofInValidChars），第二个方法是O（numInv log numInv + strings）。 哪个更便宜，所以几乎总是更便宜。