Sort Hashtable by (possibly non-unique) values

I have a Hashtable that maps strings to ints. Strings are unique, but several may be mapped to the same integer.

My naive approach was to simply invert the Hashtable to a SortedList that is indexed by the Hashtable's values, but the problem is that you get a clash as soon as two of the H开发者_运维百科ashtable's strings map to the same value.

What is the most efficient way to list my entire Hashtable (keys and values) ordered by the values? (Where two values are the same, I don't care about their ordering.)

Using Linq:

hashtable.Cast<DictionaryEntry>().OrderBy(entry => entry.Value).ToList()

You said you wanted the most efficient method. The following code is the best I could find.

Hashtable hashtable = GetYourHashtable();
var result = new List<DictionaryEntry>(hashtable.Count);
foreach (DictionaryEntry entry in hashtable)
{
    result.Add(entry);
}
result.Sort(
    (x, y) =>
    {
        IComparable comparable = x.Value as IComparable;
        if (comparable != null)
        {
            return comparable.CompareTo(y.Value);
        }
        return 0;
    });
foreach (DictionaryEntry entry in result)
{
  Console.WriteLine(entry.Key.ToString() + ":" + entry.Value.ToString());
}

I experimented with various different approaches using Linq, but the above method was about 25-50% faster.

Maybe this could work:

myhashtable.Keys.Select(k => new List<string, int>() {k, myhashtable[k]})
    .OrderBy(item => item[1]);

This should give you a list of lists, with the nested lists containing exactly two elements, the key and the value. Sorted by the value (second element).

I'm not quite sure if the Hashtable has a KeyValuePair<K, V> type... something like this could also work:

myhashtable.Items.OrderBy(kvp => kvp.Value);

The immediate way that springs to mind is along the lines of what you have except that you have a SortedList (or similar) that uses the original values (ie the integers) as keys and as values has a list of the original keys (ie the strings if I understand correctly). There is a bit more faff involved in adding values (since you need to check if they exist and add them to the list if so or create a new list otherwise). There may be better methods but this is the one that immediately springs to mind...