Има ли реализирана структура от данни, която съчетава свойствата на хеш таблица и подредбата на елементите?

Да, така структура от данни съществува. В 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, но той не е базиран на хеш таблица.