Подойдёт ли HashMap, если нужно обходить элементы в порядке их вставки?

Нет, Java HashMap не гарантирует порядок обхода по вставке. Для такого требования обычно используют LinkedHashMap с порядком вставки; TreeMap сортирует по ключам, что является другой задачей.

Пример:

Map<String, Integer> values = new LinkedHashMap<>();
values.put("b", 2);
values.put("a", 1);
// При обходе: b, затем a.

У LinkedHashMap также существует режим порядка доступа, поэтому настройку нужно выбирать осознанно. Случайно устойчивый порядок HashMap на конкретных данных не является контрактом. Повторная запись существующего ключа в обычном режиме вставки не равна добавлению нового элемента.