1回答

liuyubobobo

2021-04-25

严格来讲，HashMap 或者 HashSet 对字符串的操作不是 O(1) 的而是 O(w) 的，其中 w 是字符串的长度。这是因为为了处理一个字符串，需要计算一个字符串的哈希值，为了计算这个字符串的哈希值，必须遍历整个字符串，所以是 O(w) 的。这一点，在理论时间复杂度上，是和 Trie 一样的。（Trie 的各项操作也是 O(w) 的。）

但是，在实际使用上，哈希表很多时候不如专门设计的链式存储结构，这是因为：

1）哈希表的实际性能可能并不高，因为计算哈希值，处理哈希冲突，包括可能的扩容操作，这些都是性能开销。这些都是 trie 没有的。这里有个类似的问题，可以参考我的回答的后半部分：https://class.imooc.com/course/qadetail/283599

2）哈希表对空间的消耗可能很大。为了减少哈希冲突，就需要增大空间消耗。这在嵌入式系统中，尤其是早期嵌入式系统设计中，是个很重要的考量因素。

dp 的专门课程是有计划的，还在思考中。敬请关注，继续加油！：）

继续加油！：）

0

hew_chapter

hp>多谢老师的回答，非常感谢！期待dp课早日出炉。

h021-04-25

共1条回复