Existe um quase tipo que pareça com Hashtable, mas

Preciso de uma collection que tenha estrutura semelhante a um Hashtable no que diz respeito a definição de Chave/Valor só que não reordene seus elementos como o Hashtable faz.

[color=darkblue] O HashMap não serviria ? [/color]

  HashMap map = new HashMap();
  map.put(key, value);

Você quer que a coleção fique ordenada como ??? Se for na ordem de inserção dos objetos você pode usar o java.util.LinkedHashMap !!!

Use um LinkedHashMap.

Exemplo:

Map<String, String> mapa = new LinkedHashMap<String, String>();
mapa.put ("AM", "Amazonas");
mapa.put ("BA", "Bahia");
mapa.put ("CE", "Ceará");
for (Map.Entry<String, String> entry : mapa.entrySet()) {
    System.out.println (entry.getKey() + "->" + entry.getValue());
}

Acho que o LinkedHashMap vai funcionar legal se ele mantém a ordem da inserção, pois o Hashtable estava trazendo uma lista ordenada de modo diferente a cada vez que a pagina era acessada!

Se você precisar de uma lista ordenada MESMO (ou seja, ordenada alfabeticamente ou numericamente), use TreeMap:

SortedMap <String, String> estados = new TreeMap <String, String>();
estados.put ("SP", "São Paulo");
estados.put ("RJ", "Rio de Janeiro");
estados.put ("DF", "Distrito Federal");
 for (Map.Entry<String, String> entry : mapa.entrySet()) {
     System.out.println (entry.getKey() + "->" + entry.getValue());
 }

imprime:

DF -> Distrito Federal
RJ -> Rio de Janeiro
SP -> São Paulo

Valeu!