The fastest way to collapse a hash map to disk in a sorted set

I have one Map<byte[], Element>, and I want to sort it and write it to disk so that I have a file with all the elements sorted by key via Guava UnsignedBytes.lexicographicalComparator.

Now I am doing the following:

HashMap<byte[], Element> memory;

// ... code creating and populating memory ...

TreeMap<byte[], Element> sortedMap = new TreeMap<byte[], Element>(UnsignedBytes.lexicographicalComparator());
sortedMap.putAll(memory.getMap());

MyWriter writer = new MyWriter("myfile.dat");
for (Element element: sortedMap.values())
    writer.write(element);
writer.close();

It's probably harder to make sorting faster (O (nlogn)), the question is, can I improve the navigation of the sorted list. Ideally, I would choose ArrayListinstead TreeMap, so iterating through it would be very fast.

I thought about putting the HashMap in ArrayListand Collections.sort(), but this will require more copying than the actual solution.

Any ideas?

Edit:

ArrayList, 2 , , . , ?

// ArrayList-based implementation 2x faster
ArrayList<Element> sorted = new ArrayList<Element>(memory.size());
sorted.addAll(memory.values());

final Comparator<byte[]> lexic = UnsignedBytes.lexicographicalComparator();

Collections.sort(sorted, new Comparator<Element>(){
    public int compare(Element arg0, Element arg1) {
        return lexic.compare(arg0.getKey(), arg1.getKey());
    }
});
MyWriter writer = new MyWriter(filename);

for (Element element: sorted)
    writer.write(element);
writer.close();