algorithm - 文件中单词出现的次数 - 复杂性？

Question

鉴于我有一个包含一组单词的文件:

1) 如果我选择一个哈希表来存储单词 -> 计数，查找特定单词出现的时间复杂度是多少？

2) 我怎样才能按字母顺序返回这些单词？

如果我选择哈希表，我知道 1) 的时间复杂度是 O(n) 来解析所有单词，O(1) 来获取特定单词的计数。

我看不出如何排序哈希表以及时间复杂度是多少。有帮助吗？

Answer 1

本质上，可排序的 HashMap 变成了二叉树。在 Java 中，您可以看到 TreeMap 在查找和插入时使用 O(log n) 实现 SortableMap 接口(interface)。

如果您想要最佳的理论性能，您可以使用 O(1) 查找和插入的 HashMap，然后使用 O(n) 的桶/基数排序进行显示/迭代。

实际上，对字符串使用基数排序的性能比 O(n log n) 的快速排序差。