Existe uma estrutura de dados implementada que combina as propriedades de uma tabela de hash e de uma ordenação de elementos?

Sim, existe essa estrutura de dados. Em Java e Android, ela é a classe LinkedHashSet, que combina as propriedades de uma tabela hash e mantém a ordem de inserção dos elementos.

O LinkedHashSet armazena elementos de forma única (como o HashSet) e mantém a ordem em que foram adicionados, permitindo iterar sobre os elementos na mesma ordem.

Exemplo de uso do LinkedHashSet:

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

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

Se for necessária ordenação pela ordem natural, pode-se usar o TreeSet, mas ele não é baseado em uma tabela hash.