Sort Hashtable by (possibly non-unique) values

Question

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 Hashtable'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.)

Answer 1

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);

Answer 2

Using Linq:

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

Answer 3

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...

Answer 4

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.