如果您以 ArrayList<Obj> 开头, 在 ArrayList 上循环是否有时间优势并将值放入 HashMap有一个有用的搜索键？或者循环 ArrayList几乎抵消了将其放入 HashMap 中可以获得的任何好处？
我假设如果您要在新的 HashMap 上执行多次搜索，您仍然会受益。 ，但是只搜索一次呢？
最佳答案
对于一次搜索，创建 HashMap 没有意义，因为构建 HashMap 所花费的时间将是线性的 ( O(n) )，这与直接搜索 ArrayList 所需的时间相同.
自从创建 HashMap有一些开销超出了迭代 ArrayList 所需的时间，通过直接遍历 ArrayList 来进行一次搜索应该比构建 HashMap 更快然后搜索一些 key (尽管渐进地这两个操作应该花费相同的时间)。
A HashMap如果你要多次使用它是合理的。例如，如果您执行 n在 ArrayList 上搜索尺寸n ，需要 O(n^2)时间(因为每次搜索都需要 O(n) 时间)。
另一方面，如果您将 ArrayList 的元素放入在Map并执行 n在 Map 上搜索，运行时间将为 O(n) (因为每次搜索都需要预期的常数时间)。
关于java - 遍历 ArrayList 并将值放入 HashMap 与仅搜索 ArrayList 的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/54090789/