Cook Computing

More Collection Trivia

June 11, 2002 Written by Charles Cook

While glancing through the decompiled SortedList code I noticed there is a serious bug waiting to happen. When a key/value pair is added, a reference to the key object, not a copy or clone of it, is stored in the key array. This means that if a reference to the key object is also held outside the SortedList (or obtained via the GetKey method), the object can be modified, thereby corrupting the index. This code illustrates the problem:


class Str : IComparable
{
  public Str(string s)
  {
    str = s;
  }
  public int CompareTo(object x)
  {
    Str sx = (Str)x;
  int ret =  String.Compare(str, sx.str);
  return ret;
  }
  public string str;
}

class _
{
  static void Main(string[] args)
  {
    Str s1 = new Str("aaa");
    Str s2 = new Str("bbb");
    SortedList srtdlst = new SortedList();
    srtdlst.Add(s1, "111");
    srtdlst.Add(s2, "222");
    s1 = new Str("ccc"); // corrupt the index
    string ss = (string)srtdlst[s1]; // Item method fails
  }
}

HashTable suffers from the same problem. In this case the documentation states: Key objects must be immutable as long as they are used as keys in the Hashtable.

An example of an immutable object would be an instance of String. Alternatively if a value type is passed in as the first parameter of Add, an implicitly boxed value is created which cannot be modified outside the SortedList instance.