Hashlist - Hashtable meets ArrayList

• Download source files - 1 Kb

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
        {
        //array list that contains all the keys 

        //as they are inserted, the index is associated with

        //a key so when pulling out values by index

        //we can get the key for the index, pull from the 

        //hashtable the proper value with the corresponding 

        //key

        //This is basically the same as a sorted list but

        //does not sort the items, rather it leaves them in the

        //order they were inserted - like a list

        
            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
        //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
        //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
        //specialized indexer routines

        
        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

• 5/23/2003 - Written