Нужна структура с быстрым поиском по ключу, которая при обходе отдаёт элементы в порядке их добавления. Что выбрать?

HashMap даёт нужную скорость, но порядок обхода у него не определён и меняется при перехешировании. TreeMap упорядочивает по ключу, а не по времени добавления, и стоит O(log n). Список пар потребует линейного поиска. LinkedHashMap решает задачу точно: та же хеш-таблица плюс двусвязный список, прошивающий записи в порядке вставки. Общий подход к таким вопросам — сначала сформулировать паттерн доступа (поиск, обход, диапазоны, порядок), и структура выбирается почти однозначно.