Trie数据结构的实现的疑惑 Array vs HashMap

最近做DFS做到一题Trie(LC 211) 就复习了下Princeton的网课 网课老头教的时候 在实现每个TrieNode的子节点列表的时候 用的是Array E.g. 储存英语字典的话 每个TrieNode的子节点需要新建一个TrieNode[26]

但是这样的话，执行一次insert的最坏空间复杂度是O(L * R), where L is String 长度, R = 26. 因为假设insert的String的每一个char在字典里都是新的，我们需要新建L个TrieNode[26]

我看到LC 211官方题解里这里用的是HashMap<Character, TrieNode>, 感觉这样的好处是执行一次insert的最坏空间复杂度是O(L) instead of O(L * R). 当然如果我们把所有长度的单词都放进字典的话总空间复杂度应该是一样的，也就是O(R^L)，但是好像字典比较sparse的时候用HashMap更节省空间一点？

希望大佬聊一下想法 感谢！

可是有时候string并不是只由26个字母组成

xav-zjf 发表于 2022-7-14 21:40
可是有时候string并不是只由26个字母组成

I see 这样感觉还是用HashMap好一点

楼上说的对啊，还见过有大佬用TrieNode[128]呢，包含了大写，小写，数字，再加上一点点浪费，但和HashMap的loadfactor相比也不分伯仲

有没有考虑过其他字符，比如说中文字符，那就只能hashmap了

如果是字母的话，开array写更加省事，尤其打比赛的时候，java选手写个map真不如开个array快。

工业代码的话，还是别这样了。用HashMap。