我有一个执行以下操作的程序：
遍历字符串，将单词放入 aHashMap<String, Integer>中，其中键表示唯一单词，值表示运行的总出现次数（每次找到单词时递增）。
我相信到目前为止我们是O(n)因为每个插入都是恒定的时间。
然后，我遍历 hashmap 并将值插入到一个新的HashMap<Integer, List<String>>. 进入计数匹配的值中String。List我认为我们仍在，O(n)因为在HashMaps 和Lists 上使用的操作是常数时间。
然后，我遍历HashMap并打印String每个中的 s List。
该程序中的任何内容是否会导致我超越O(n)复杂性？
也就是说O(n)，除非您的单词解析算法不是线性的（但它应该是）。
你是对的，有一个警告。在哈希表中，插入和查找每次都需要O(1) 的预期时间，因此算法的预期运行时间是 O(n)。如果你有一个糟糕的哈希函数，那么它可能会花费更长的时间，通常（对于最合理的哈希表实现）在最坏的情况下O(n 2 )。
此外，正如@Paul Draper 指出的那样，这假设计算每个字符串的哈希码需要时间 O(1)，并且比较表中的字符串需要时间 O(1)。如果您的字符串的长度不受某个常数的限制，则计算哈希码可能需要更长的时间。实际上，更准确的分析是运行时间为 O(n + L)，其中 L 是所有字符串的总长度。
希望这可以帮助！
除了 Paul Draper 和 templatetypedef 指出的两个问题之外，还有另一个潜在的问题。您写道，您的第二张地图是hashmap < int,list < string > >. 仅当您为列表选择的实现允许（摊销）常数时间附加时，这才允许总体线性复杂性。如果您使用 anArrayList并在末尾添加条目，或者您选择 aLinkedList并在任一端添加条目，则会出现这种情况。
我认为这涵盖了大多数开发人员的默认选择，因此它并不是真正的障碍。