鉴于我们有一个字符串列表我想知道能够验证给定字符串是否已经存在的最有效的数据结构是什么，如果不存在，则添加它。
我的第一个问题是HashSet<String>，当涉及到检查字符串的存在时，它具有O(n)(最佳情况)复杂性。然而，当它将被重载时，每个字符串将根据hashCode算法逐个字符地重新哈希：s[0]*31^(n - 1) + s[1]*31^(n - 2) + ... + s[n - 1]什么将导致CCD_ 4。
编辑：我想强调的是，我在这里最担心的是在重新哈希集的同时重新哈希每个非常长的字符串的时间复杂性，因为有大量非常长、唯一的条目。
有没有更好的方法将许多字符串存储在HashSet中，或者可能有更好的数据结构用于这种方法？
该构造函数不是选项吗？
public HashSet(int initialCapacity, float loadFactor)
您的第一个想法是错误的。答案是HashSet。时期
你对碰撞的担忧与此无关；尝试将已存在的字符串添加到集合中不会有任何作用。获得冲突的唯一方法是添加大量字符串，这些字符串完全巧合地具有相同的哈希代码，这是不会发生的除非有人故意惹你，以增加服务器费用或拒绝向合法用户提供服务。
如果是这样的话，你需要付出相当大的代价：你需要一个加密安全的哈希算法。你当然可以这样做，但这会使事情变得更加复杂。模型将是相同的(有一个hashmap，键基于custom_hash_algo("input")的结果，值为List<V>：每个值都使用custom_hash_algo散列到同一个键。然后你用这个重新实现Set的所有方法(字面意思是：创建一个extends AbstractSet<V>的类，其中大多数方法都是调用该内部映射上的方法的一行。
custom_hash_algo将是您所需要的任何东西。如果你想防止有人故意给你提供哈希冲突的字符串，那么要么有一个简单的阻塞机制(如果给定自定义哈希值的列表有太多条目，就崩溃并拒绝服务，因为在这一点上，客户干扰你或反过来被干扰的几率为99.9999%)，要么有一种加密安全的哈希。
如果你有任何其他理由相信哈希冲突会比预期的更频繁，"对于任何两个给定的字符串，它们冲突的几率约为40亿分之一"，那么同样的原理也可以用于其他一些非加密算法(因此对故意创建冲突字符串不具有鲁棒性)。
NB：如果我误解了你的问题，你唯一担心的是字符串的hashCode()impl会查看每个字符：不，你不能改进这一点；如果不这样做，就不可能对字符串进行哈希处理，从而在很大程度上避免冲突，除非你知道特定字符串的某些特定信息，而这些信息不适用于任意字符串("它们总是以唯一的8个字符的ID开头！"-好吧，也许你可以将其用于哈希)。
这也不使它成为O(n^2)。当谈到算法复杂性时，如果不定义n的实际含义，就无法做到这一点。从上下文来看，这通常是显而易见的，这就是为什么它通常不会被说出来，但它仍然是声明的关键部分，即使没有说出来。在您的情况下，"集合中的字符串数"是一个变量，"字符串的平均长度"是另一个变量。最多可以说它是O(n*m)(其中n和m定义为"n=集合的大小，m=其中字符串的平均长度")。哪一个是 啊这显然是最有效的方法
NB2：在编写Map<Integer, List<V>>支持的集合impl时，一个重要的优化机会是让值不是List<V>而是Object，这样你就可以制定一个规则，如果它是非列表对象，那么在你的集合中只有一个对象可以散列到这个值，只有当发生冲突时，你才会创建一个特殊的内部列表类型(这就是你区分的方式：除了你之外，没有人可以创建这种内部列表类型，因此如果是那种类型，你就知道这是冲突情况)。这节省了大量的开销。
这里更常见的情况是：如何实现数组的映射？
如果数组(或字符串)经常非常大，则哈希代码计算将成为负速度因子。因此，HashMap可能不是一个好主意。
然后TreeMap会更好，正如比较经常比较的那样：
- 相同长度
- 只要元素相等，就比较阵列元素
换句话说：
- 给定N数组的数量
- 给定L数组的平均长度
然后对于平均情况：
- 哈希映射：O(N*L)
- 树映射：大约O(N*log(N)*log(M))
这意味着您必须进行基准测试。
当字符串很大时，比如说包含文件时，这一切都变得相关。你也可以"；优化"；通过压缩和用哈希码(CRC？)存储字节来实现这些功能。
作为针对接口(Set<String> set)的一个程序，可以推迟实现的选择。