¿Existe una estructura de datos implementada que combine las propiedades de una tabla hash y el orden de los elementos?

Sí, existe tal estructura de datos. En Java y Android, esto es la clase LinkedHashSet, que combina las propiedades de una tabla hash y mantiene el orden de inserción de los elementos.

LinkedHashSet almacena los elementos de forma única (como HashSet) y mantiene el orden en que se añaden, lo que permite iterar sobre los elementos en ese mismo orden.

Ejemplo de uso de LinkedHashSet:

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

for (String s : linkedSet) {
    System.out.println(s); // Imprimirá: one, two, three
}

Si se necesita ordenar por orden natural, se puede usar TreeSet, pero no está basado en una tabla hash.