循环遍历ArrayList并将值放入HashMap与仅搜索ArrayList的时间复杂度

如果你从ArrayLista 开始,是否有时间好处来循环ArrayList并将值放入HashMap一个有用的搜索键中？或者,ArrayList通过将它放入其中而几乎否定了你将获得的任何好处HashMap？

我假设如果你要对新的搜索执行许多搜索,你仍然可以获得一个好处HashMap,但是只有一次搜索呢？

对于一次搜索,创建一个没有意义HashMap,因为构建它所需的时间HashMap将是linear(O(n)),这与直接搜索它所需的时间相同ArrayList.

由于创建HashMap具有一些开销超越时间,将采取迭代ArrayList,通过在直接迭代一个单一的搜索ArrayList应该比建设速度HashMap,然后寻找一些主要的(尽管渐进两种操作应采取相同的时间).

一HashMap,如果你要多次使用它是有道理的.例如,如果您对大小进行n搜索,则需要一些时间(因为每次搜索都需要时间).ArrayListnO(n^2)O(n)

另一方面,如果你将a的元素ArrayList放在a上Map并对其执行n搜索Map,则运行时间将是O(n)(因为每次搜索都需要预期的恒定时间).