Существует ли реализованная структура данных, которая сочетает в себе свойства хеш-таблицы и упорядоченности элементов?

Да, такая структура данных существует. В Java и Android это класс LinkedHashSet — он сочетает в себе свойства хеш-таблицы и поддерживает порядок вставки элементов.

LinkedHashSet хранит элементы уникальными (как HashSet) и при этом сохраняет порядок их добавления, что позволяет итерироваться по элементам в том же порядке.

Пример использования LinkedHashSet:

LinkedHashSet<String> linkedSet = new LinkedHashSet<>();
linkedSet.add("one");
linkedSet.add("two");
linkedSet.add("three");

for (String s : linkedSet) {
    System.out.println(s); // Выведет: one, two, three
}

Если нужна сортировка по естественному порядку, то можно использовать TreeSet, но он не основан на хеш-таблице.