Time Complexity of Looping over an ArrayList and putting values in HashMap vs. just searching the ArrayList

Question

If you start with an ArrayList<Obj>, is there a time benefit to for-looping over the ArrayList and putting the values into a HashMap with a useful key for searching? Or does the looping of the ArrayList pretty much negate any benefit you would gain by putting it in the HashMap?

I assume you'd still get a benefit if you were going to perform many searches on the new HashMap, but what about just one search?

Answer 1

For just one search there's no point in creating a HashMap, since the time it takes to build the HashMap would be linear (O(n)), which is the same time it takes to directly search the ArrayList.

Since creating the HashMap has some overhead beyond the time it would take to iterate over the ArrayList, a single search by directly iterating over the ArrayList should be faster than building the HashMap and then searching for some key (though asymptotically both operations should take the same time).

A HashMap is justified if you are going to use it multiple times. For example, if you perform n searches on an ArrayList of size n, it would take O(n^2) time (since each search would require O(n) time).

On the other hand, if you put the elements of the ArrayList in a Map and perform n searches on the Map, the running time would be O(n) (since each search would take expected constant time).