能否使用存储字符的HashMap替代String实现重复输入字符检测功能？

核心结论 #

使用HashMap.containsKey()（注意：HashMap没有contains()方法，你需要将字符作为Key存入Map，调用containsKey()做存在性校验）的实现方案，绝大多数场景下比String.contains()速度更快。

差异原因 #

• String.contains()底层是逐字符匹配的子串校验逻辑，单次检查的时间复杂度为O(n)，n是当前已拼接字符串的长度，随着拼接内容变长，每次检查的耗时会线性增长。
• HashMap.containsKey()的理想时间复杂度为O(1)，无论已存储多少字符，单次检查的耗时基本稳定，不会随拼接长度增加而明显上升。
• 如果你的业务场景中最多只会拼接不超过10个字符，两种方案的性能差异几乎可以忽略，String.contains()代码更简洁，更适合这种短字符串场景。

优化建议 #

如果只是做字符的存在性校验，不需要存储额外关联值的话，用HashSet更合适，它底层基于HashMap实现，HashSet.contains()的性能和HashMap完全一致，代码更精简，不需要存储无意义的占位Value。

示例实现（HashSet版本） #

public String buildStringUntilDuplicate(char[] inputChars) {
    Set<Character> existChars = new HashSet<>();
    StringBuilder result = new StringBuilder();
    for (char c : inputChars) {
        if (existChars.contains(c)) {
            break;
        }
        existChars.add(c);
        result.append(c);
    }
    return result.toString();
}

• 如果你有更极致的性能需求，且待处理的字符范围仅为ASCII字符，可以用长度为128的布尔数组代替HashMap/HashSet，查询速度更快，且完全没有哈希冲突的开销，内存占用也更低。

内容的提问来源于stack exchange，提问作者David Tejuosho