If you ever need to do that in the future in Java for whatever reason, Java actually has it already in the standard library--it's called LinkedHashMap.
Yeah, I think I knew that even at the time, but I suspect if my answer was just "import java.util.LinkedHashMap", they might have been a bit disappointed.
