Embora não esteja documentado, values é uma coleção que na verdade encapsula o iterador retornado por entrySet().iterator().
Então se entrySet().iterator() retorna as entradas do map na ordem em que foram inseridas, values() irá também fazer a mesma coisa (retornar os valores do map na ordem em que foram inseridos).
Eu tive de olhar os fontes de AbstractMap, HashMap e LinkedHashMap para chegar a essa conclusão.
B
Bruno_Laturner
Tem o mesmo comportamento.
Na implementação do GNU classpath, values retorna uma AbstractCollection, com o mesmo iterador do [Linked]HashMap, mas que retorna somente os valores da coleção.