HashMap or TreeMap or LinkedHashMap which one is fastest to iterate over?

HashMap will generally be fastest, since it has the best cache behavior (HashMap iterates directly over the backing array, whereas TreeMap and LinkedHashMap iterate over linked data structures).

You may want to use an ImmutableMap or UnmodifiableMap if the map isn't going to change once it's initialized

I wouldn't use the map. If all you want is to iterate through the entries make a new ArrayList of what you need and use that - you cannot get faster than an ArrayList for iteration.

// Which map you use only chooses the order of the list.
Map<Key,Value> map = new HashMap<>();
// The list to iterate for maximum speed.
List<Map.Entry<Key,Value>> list = new ArrayList<>(map.entrySet());

This way you iterate across the entry set just once to build the list. From then on you are iterating across the list again and again - which certainly should be close to optimal.

Note Changed from LinkedList to ArrayList on Marko's suggestion.

None of the other answers here take into consideration the effects of CPU cache, which can be huge when iteration is concerned.

One way to improve this is to use just a single array of interleaved keys and values (keys at even indices, values at odd ones). This will tightly group together these data items and maximally leverage the cache, at least for the references.

But the true, screaming improvement would be achieved if you could avoid creating objects which hold your data and use just arrays of primitive values. This is, naturally, highly dependent on your use case.