Introduction
Have you ever needed the capabilities provided by the SortedList
but didn't want the data to be sorted? Have you ever needed the
capabilities of the Hashtable, but wanted to be able to loop
through the items using a foreach construct or a for loop? I needed this
capability in an application I was writing, and figured that someone else might
benefit from my time spent solving this problem.
Background
The whole thing started when I was writing a custom configuration
component. I originally stored the configuration information in a
SortedList because it provided me with a key/value pair feature
(which was needed since each configuration item was "unique" based on the key),
as well as a nice GetByIndex method so I could use a foreach to get the data or
I could use a for loop to get the data.
The problem I ran into was that the SortedList did what it was
supposed to and sorted the data according to the key that I passed in when
adding items.
Unfortunately, portions of my application expected the configuration
information to be sequential, I quickly learned the SortedList was not the tool
for the job I was trying to do.
After spending several hours looking for a data structure to fit my
needs in System.Collections and
System.Collections.Specialized, I found a close match to what I
wanted:
- Get items by index
- Index items in the order in which they are added
- Provide key/value pair capability as well
The System.Collections.Specialized.NamedValueCollection seemed
to be exactly what I needed. But alas.... the NamedValueCollection
only stored strings. AAAHHHHH... so close... but I need the thing
to store objects.
I finally bit the bullet and wrote the Hashlist. I think
that I got all the features I needed... perhaps this can solve a similar problem
for you.
Design/Implementation
The Hashlist design is pretty simple.
I just took an ArrayList (because it stores objects in the order
in which they were inserted), and a Hashtable (which gives the
key/value pair capability) and smushed them together into a class that
implements both IEnumerable (so foreach can be used) and
IDictionary (so key/value can be used). And because
IDictionary is a specialized implementation of ICollection
you must implement ICollection members as well.
Here is the declaration of the class:
public abstract class Hashlist : IDictionary, IEnumerable
{
protected ArrayList m_oKeys = new ArrayList();
protected Hashtable m_oValues = new Hashtable();
Now here is the ICollection implementation (basically wrapped up
the hashtable ICollection members):
#region ICollection implementation
public int Count
{
get{return m_oValues.Count;}
}
public bool IsSynchronized
{
get{return m_oValues.IsSynchronized;}
}
public object SyncRoot
{
get{return m_oValues.SyncRoot;}
}
public void CopyTo(System.Array oArray, int iArrayIndex)
{
m_oValues.CopyTo(oArray, iArrayIndex);
}
#endregion
Next is the IDictionary implementation (again using underlying
ArrayList and Hashtable data structure):
One important note here is that if you notice the Add method, I
am only adding the Key to the ArrayList, not the object
itself. This is because when you add an item to the
ArrayList, it gives them an index in the order in which they were
inserted.
Therefore, when you want an item by index, just get the key from the
ArrayList and then get the value with the appropriate key from the
Hashtable (this is done in the Hashlist specialized
implementation code section - with overloaded indexors)
#region IDictionary implementation
public void Add(object oKey, object oValue)
{
m_oKeys.Add(oKey);
m_oValues.Add(oKey, oValue);
}
public bool IsFixedSize
{
get{return m_oKeys.IsFixedSize;}
}
public bool IsReadOnly
{
get{return m_oKeys.IsReadOnly;}
}
public ICollection Keys
{
get{return m_oValues.Keys;}
}
public void Clear()
{
m_oValues.Clear();
m_oKeys.Clear();
}
public bool Contains(object oKey)
{
return m_oValues.Contains(oKey);
}
public bool ContainsKey(object oKey)
{
return m_oValues.ContainsKey(oKey);
}
public IDictionaryEnumerator GetEnumerator()
{
return m_oValues.GetEnumerator();
}
public void Remove(object oKey)
{
m_oValues.Remove(oKey);
m_oKeys.Remove(oKey);
}
public object this[object oKey]
{
get{return m_oValues[oKey];}
set{m_oValues[oKey] = value;}
}
public ICollection Values
{
get{return m_oValues.Values;}
}
#endregion
Now for the trick of getting this IEnumerable interface to work
(implement the IEnumerable interface):
#region IEnumerable implementation
IEnumerator IEnumerable.GetEnumerator()
{
return m_oValues.GetEnumerator();
}
#endregion
But wait... didn't I just implement a GetEnumerator in the
IDictionary implementation?
Yes I did. This one is different.
It must be implemented because IDictionary is
IEnumerable, but unless your class explicitly implements
IEnumerable, you cannot use foreach constructs with
the object type so for instance:
foreach(MyObject o in MyHashlist)
{
.... blah blah ....
}
can only be used if you implement the IEnumerable interface, and
of course provide overloaded indexor properties. If you only implement
IDictionary you have to use a foreach construct like
this:
foreach(IDictionaryEntry o in MyHashlist)
{
.... blah blah ....
}
In my opinion the latter just plain sucks... So, you have to fully
qualify the interface for which you are implementing in the declaration, which
explains the:
IEnumerator IEnumerable.GetEnumerator()
The above interface implementation returns an IEnumerator
which if you notice in the IDictionary implementation, is
not what is returned from IDictionary.GetEnumerator(). Crazy way MS
implemented this but they are Microsoft so... who am I to say.
The last
thing that we must do is implement some specialized indexors so that we can get
the objects out the way we want:
#region Hashlist specialized implementation
public object this[string Key]
{
get{return m_oValues[Key];}
}
public object this[int Index]
{
get{return m_oValues[m_oKeys[Index]];}
}
#endregion
Notice that the indexors are overloaded to take an index or a key string.
This makes this data structure really handy. Also you may ask about the
IDictionary implementation of the indexor which takes an object. A
colleague of mine mentioned that perhaps the this[string Key] implementation was
equivelant to the this[object key] implementation defined in
IDictionary. While this is true, explicitly defining the type
passed in is more efficient so .NET doesn't have to convert the string you pass
in as the key to an object. That is also a point of debate which I encourage,
because I couldn't find a clear "best" way to handle that (but it is a minor
issue so I left it as it was).
Using the Hashlist
So you may ask yourself... what good is all this code if I can't use it?
Right you are, so here are some examples of what you could do:
The first
thing to consider is the fact that the Hashlist class is abstract. This
means that sorry - no instances. You have to inherit from this list but it
is pretty easy... take this SectionList for example:
public class SectionList : Hashlist
{
public new Section this[string Key]
{
get{return (Section)base[Key];}
}
public new Section this[int Index]
{
get
{
object oTemp = base[Index];
return (Section)oTemp;
}
}
public SectionList()
{
}
}
In the above code I created a specialized list that returns a Section class
from the indexors. As you can see, implmenting your own specialized lists that
have all the functionality of both Hashtables and
ArrayLists, takes little effort. The new keyword before the
indexors are required because they overload the Hashlist indexors.
Points of Interest
One interesting tid bit of information that I did learn is that:
Using an enumeration with a foreach construct to loop through
say a Hashtable for instance, or any other IEnumerable
data structure for that matter, does not loop through the items in
the order in which they were inserted.
This is because:
The key/value pair capability of IEnumerable derived collections
typically use some sort of hashing algorithm to make retrieval fast, the data is
stored in an order that is most efficient for retrieval, not necessarily the
order in which it was inserted (not FIFO). This is probably common
knowledge to most folks but was a rude awakening to me.
Thanks to Guy Swartwout for pointing out strange behavior in my config
component that forced this issue to the surface. I sure did learn alot
about .NET collections.
History
