Click here to Skip to main content
15,868,141 members
Articles / Desktop Programming / MFC
Article

Hashlist - Hashtable meets ArrayList

Rate me:
Please Sign up or sign in to vote.
4.44/5 (39 votes)
22 May 20035 min read 381.2K   1.7K   77   59
This article describes how to build a data structure that supports storage of objects with key/value pairs as well as integer indexors

Introduction

Have you ever needed the capabilities provided by the

C#
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

C#
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

C#
ICollection 
you must implement ICollection members as well.

Here is the declaration of the class:

<PRE id=PRE2>        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):

C#
#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)

C#
#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):

C#
#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:

C#
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:

C#
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:

C#
IEnumerator IEnumerable.GetEnumerator()


The above interface implementation returns an

C#
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:

C#
#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:

C#
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

C#
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

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


Written By
Web Developer
United States United States
Software developer for 9 years. Likes .NET and C#.

Comments and Discussions

 
GeneralWorks perfect!! Pin
Jorge Mendez16-Mar-11 11:44
Jorge Mendez16-Mar-11 11:44 
Questionhow do I implement hashtable by declaring own structure or class Pin
Member 37378035-Jul-10 14:09
Member 37378035-Jul-10 14:09 
Questionis there any way to create property files in c#? Pin
merryjoy0006-Feb-09 22:18
merryjoy0006-Feb-09 22:18 
Questionlike properties file's in java...what is the term for properti file's in c#? Pin
merryjoy0006-Feb-09 22:17
merryjoy0006-Feb-09 22:17 
Generalneed help [modified] Pin
neoandrew3-May-08 3:17
neoandrew3-May-08 3:17 
QuestionIts Not Returing Value [modified] Pin
ramseenu5-Feb-07 22:32
ramseenu5-Feb-07 22:32 
GeneralSortedList + a custom comparer does the trick! Pin
gunnarD30-Nov-06 12:01
gunnarD30-Nov-06 12:01 
QuestionAny reason why you did not use OrderedDictionary? Pin
mosaic211-Jul-06 9:44
mosaic211-Jul-06 9:44 
AnswerRe: Any reason why you did not use OrderedDictionary? Pin
s0mat0se11-Jul-06 22:46
s0mat0se11-Jul-06 22:46 
GeneralRe: Any reason why you did not use OrderedDictionary? Pin
mosaic215-Jul-06 4:33
mosaic215-Jul-06 4:33 
GeneralIDictionaryEntry should be DictionaryEntry Pin
Michael Freidgeim30-May-06 14:58
Michael Freidgeim30-May-06 14:58 
QuestionCould I use Ilist in place of arraylist. Pin
KamranShahid28-Apr-06 3:15
KamranShahid28-Apr-06 3:15 
GeneralMany Thanks Pin
ANIL KUMAR SHARMA (INDIA)31-Mar-06 17:43
ANIL KUMAR SHARMA (INDIA)31-Mar-06 17:43 
GeneralPerformance Hit Pin
ANIL KUMAR SHARMA (INDIA)27-Mar-06 3:58
ANIL KUMAR SHARMA (INDIA)27-Mar-06 3:58 
AnswerRe: Performance Hit Pin
Mike McPhail31-Mar-06 8:00
Mike McPhail31-Mar-06 8:00 
GeneralThanks, super useful Pin
Henry Rosales Parra1-Dec-05 11:15
Henry Rosales Parra1-Dec-05 11:15 
GeneralWintellect.PowerCollections Pin
CarlMeis5-Oct-05 5:37
CarlMeis5-Oct-05 5:37 
GeneralCool article Pin
Anonymous13-Jul-05 4:36
Anonymous13-Jul-05 4:36 
Generalproblem add key to SortedList Pin
Anonymous3-Apr-05 0:48
Anonymous3-Apr-05 0:48 
GeneralRe: problem add key to SortedList Pin
Mike McPhail4-Apr-05 2:45
Mike McPhail4-Apr-05 2:45 
Generalalternative possibility - smart class Pin
Sanjay M30-Mar-05 17:58
Sanjay M30-Mar-05 17:58 
GeneralNoo Pin
Anonymous14-Feb-05 7:25
Anonymous14-Feb-05 7:25 
Generalthanks, quite usefull for me Pin
raghavendra .K6-Feb-05 23:09
raghavendra .K6-Feb-05 23:09 
GeneralActually the article is useful... Pin
Timothy Paul Narron24-Jan-05 20:54
Timothy Paul Narron24-Jan-05 20:54 
GeneralForeach still returns an IDictionary Pin
staceyw27-May-04 18:54
staceyw27-May-04 18:54 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.