algorithm - 具有字符串键的 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;
} 

因此，它被缓存(并且是线程安全的)。一旦计算出来，字符串的散列码就不需要重新计算了。这使您不必在哈希表(或哈希集、 HashMap )的情况下花费 O(k) 时间。

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