A LinkedHashMap gives you the speed of a HashMap with one addition: it remembers the order you inserted entries. When you iterate, keys come out in insertion order:
import java.util.LinkedHashMap;
LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
map.put("Carol", 88);
map.put("Alice", 95);
map.put("Bob", 72);
for (String name : map.keySet()) {
System.out.println(name);
}
// Carol, Alice, Bob
All operations still run in average time and space, just like HashMap. The cost is a small amount of extra memory to maintain the internal linked list that tracks insertion order.
There is also LinkedHashSet for the same behavior with unique elements. Use either one when you need fast lookups and predictable iteration order.