带有字符串键的 HashMap 是否真的比 Trie 具有更低的时间复杂度

Question

假设我想存储一个字符串字典，我想知道某个字符串是否存在。我可以使用Trie或HashMap。HashMap 的时间复杂度为 O（1），概率很高，而在这种情况下的 Trie 的时间复杂度为 O（k），其中 k 是字符串的长度。

现在我的问题是：计算字符串的哈希值不是具有 O（k） 的时间复杂度，从而使 HashMap 的复杂性相同吗？如果没有，为什么？

我的看法是，这里的Trie在查找字符串时的时间复杂度低于HashMap，因为HashMap除了计算哈希值外，还可能遇到冲突。我错过了什么吗？

更新：在构建字典时，您将使用哪种数据结构来优化速度？

Answer 1

除了实现 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)时间。

在

实现字典时，我认为尝试在你对可能的部分匹配而不是完全匹配更感兴趣的地方大放异彩。一般来说，基于哈希的解决方案在完全匹配的情况下效果最好。

Answer 2

对哈希表执行操作的时间复杂度通常以必须执行的哈希和比较数来衡量。在期望值上，以这种方式衡量时，成本是O（1），因为在期望值上，只需要使用恒定数量的散列和比较。

要确定对字符串使用哈希表的成本，您确实需要考虑这些操作的成本，对于长度为 k 的字符串，每个操作的成本为 O（k）。因此，对字符串进行哈希表操作的开销为 O（1） · O（k） = O（k），与 trie 成本相匹配，尽管仅在预期上并且具有不同的常量因子。