假设我要存储字符串字典，并且想知道某个字符串是否存在。我可以使用Trie或HashMap。HashMap的时间复杂度为O（1）的可能性很高，而在这种情况下，Trie的时间复杂度为O（k），其中k是字符串的长度。
现在我的问题是：计算字符串的哈希值是否不具有O（k）的时间复杂度，从而使HashMap的复杂度相同？如果没有，为什么？
我看到的方式是，在Trie中查找字符串的时间复杂度要比HashMap低，因为HashMap（除了计算哈希值之外）还可能会发生冲突。我想念什么吗？
更新：构建字典时，您将使用哪种数据结构来优化速度？
除了实现Trie的复杂性之外，在hashCode确定哈希表中存储桶的方法的实现中还进行了某些优化。对于java.lang.String，一个不可变的类，这是JDK-8的作用：
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
因此，它被缓存了（并且是线程安全的）。一旦计算完，字符串的哈希码就不需要重新计算了。这使您不必花O(k)时间在哈希表（或哈希集，哈希图）上。
在实施字典时，我认为尝试会发光，使您对可能的部分匹配而不是精确匹配更感兴趣。一般来说，在完全匹配的情况下，基于哈希的解决方案效果最佳。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句