Add items to a Set<String> in proper order Java

Question

I am creating a song playback app. I have a Set that I keep in SharedPreferences. I want to add and remove file names from it, and keep them in the same order as I added them in for example:

recentsp = getSharedPreferences("recentkey", Context.MODE_PRIVATE);

    recent = recentsp.getStringSet("recent", recent);
    recentedited = recent;

    if (recentedited.contains(string) {
        recentedited.remove(string);
        Log.i(TAG, "Recent exists, removing song");
        SharedPreferences.Editor editor = recentsp.edit();
        editor.clear();
        editor.putStringSet("recent", recentedited);
        editor.commit();
    }

        recentedited.add(string);
    Log.i(TAG, "adding song to recent");
        SharedPreferences.Editor editor = recentsp.edit();
        editor.clear();
        editor.putStringSet("recent", recentedited);
        editor.commit();

But the problem arises when I view these in a ListView. I want them in the order that I add them so that I can have a recently played section, but sometimes they don't move at all, or maybe they end up in the beginning. It seems random. Am I missing something?

Edit:

I check to make sure the SharedPreferences is not null by doing this in an initialization step...

Edit:

Even with using a LinkedHashSet I still don't get proper ordering. I only call this if the SharedPreferences is null, so I'm not exactly sure how to make sure I am using a LinkedHashSet.

        recentsp = getSharedPreferences("recentkey", Context.MODE_PRIVATE);
    recent = recentsp.getStringSet("recent", null);
    if (recent == null) {

        recent = new LinkedHashSet<String>();
        SharedPreferences.Editor editor = recentsp.edit();
        editor.clear();
        editor.putStringSet("recent", recent);
        editor.commit();
    }

Answer 1

If you are looking for an implementation of the Set interface that preserves insertion order, switch from HashSet to: LinkedHashSet. All of the standard Set behavior remains intact, with the addition of insertion-order iteration.

From the associated JavaDoc:

Hash table and linked list implementation of the Set interface, with predictable iteration order. This implementation differs from HashSet in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is the order in which elements were inserted into the set (insertion-order). Note that insertion order is not affected if an element is re-inserted into the set. (An element e is reinserted into a set s if s.add(e) is invoked when s.contains(e) would return true immediately prior to the invocation.)

This implementation spares its clients from the unspecified, generally chaotic ordering provided by HashSet, without incurring the increased cost associated with TreeSet. It can be used to produce a copy of a set that has the same order as the original, regardless of the original set's implementation