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

Question

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

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

我的看法是，这里的 Trie 比查找字符串的 HashMap 具有更低的时间复杂度，因为 HashMap - 除了计算哈希值 - 可能会发生冲突。我错过了什么吗？

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

Answer 1

除了特里树实现的复杂性之外，在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)在哈希表（或哈希集、哈希图）的情况下花费时间。

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