Estas usando un HashMap
HashMap Esta clase no garantiza el orden del mapa; en particular, no garantiza que el pedido se mantenga constante en el tiempo.
Deberías usar un LinkedHashMap
LinkedHashMap Esta implementación se diferencia de HashMap en que mantiene una lista doblemente vinculada que se ejecuta en todas sus entradas. Esta lista enlazada define el orden de iteración, que normalmente es el orden en el que se insertaron las claves en el mapa (orden de inserción).
public Map<String, String> obtenerCeldaHora(Hora[][] matriz){
Map<String, String> horass = new LinkedHashMap<String, String>();
for(int i=0; i<matriz.length; i++) {
for(int j=0; j<matriz[0].length; j++) {
Hora hora = matriz[i][j];
horass.put("("+String.valueOf(i)+","+String.valueOf(j)+")", hora.toString());
}
}
imprimir(horass);
return horass;
}