Почему, когда пересобию Map в нужном порядке, он выводит все равно в другом? TreeMap тоже не проходит, хоть и выводит верно.

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.Map;
import java.util.ArrayList;
import java.util.Collections;

class Scratch {
    public static void main(String[] args) throws IOException {

        Map<String, Double> database = new HashMap<>();
        BufferedReader bfreader = new BufferedReader(new FileReader("e:\\input.txt"));

        while (bfreader.ready()) {
            String[] split = bfreader.readLine().split("\\s");
            if (database.containsKey(split[0])) {
                database.put(split[0], ((database.get(split[0]) + Double.parseDouble(split[1]))));
            }
            else {
                database.put(split[0], Double.parseDouble(split[1]));
            }
        }

        bfreader.close();

        ArrayList<String> key = new ArrayList<>();
        for (Map.Entry<String, Double> outmap : database.entrySet()) {
            key.add(outmap.getKey());
        }

        Collections.sort(key);

        Map<String, Double> sorteddata = new HashMap<>();
        for (String array : key) {
//            System.out.println(array);  выводит:
//                                        Иванов
//                                        Петров
//                                        Сидоров
            sorteddata.put(array, database.get(array));
        }

        for (Map.Entry<String, Double> outmap : sorteddata.entrySet()) {
            System.out.print(outmap.getKey() + " " + outmap.getValue() + "\n");
//            выводит:
//            Иванов 1.35
//            Сидоров 6.0
//            Петров 5.1

        }
    }
}