Does entrySet() in a LinkedHashMap also guarantee order?

According to the Javadocs, yes.

This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).

As for the edit, no, it should work just fine. But the entry set is somewhat faster since it avoids the overhead of looking up every key in the map during iteration.