11 Replies - 9928 Views - Last Post: 24 June 2012 - 01:02 AM Rate Topic: -----

#1 megglz  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 11
  • View blog
  • Posts: 414
  • Joined: 22-August 08

implementing a hashtable using arrays

Posted 04 September 2010 - 06:11 AM

I've been searching for ages for a code example of implementing a hashtable in C# from scratch using only arrays but can only seem to find examples that make use of the Hashtable class. If anyone could point me to a good example I'd really appreciate it and thank you :)
Is This A Good Question/Topic? 0
  • +

Replies To: implementing a hashtable using arrays

#2 eclipsed4utoo  Icon User is offline

  • Not Your Ordinary Programmer
  • member icon

Reputation: 1524
  • View blog
  • Posts: 5,960
  • Joined: 21-March 08

Re: implementing a hashtable using arrays

Posted 04 September 2010 - 07:31 AM

so you are wanting to use arrays to simulate a HashTable?
Was This Post Helpful? 0
  • +
  • -

#3 megglz  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 11
  • View blog
  • Posts: 414
  • Joined: 22-August 08

Re: implementing a hashtable using arrays

Posted 04 September 2010 - 07:44 AM

yes
Was This Post Helpful? 0
  • +
  • -

#4 Imdsm  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 103
  • View blog
  • Posts: 362
  • Joined: 21-March 09

Re: implementing a hashtable using arrays

Posted 04 September 2010 - 02:25 PM

Well you'd have you have a list of objects for keys, and a list of objects for values:

List<object> keys = new List<object>();
List<object> values = new List<object>();


then you would have to add the key to one and value to the other when requested:

keys.Add(key);
values.Add(value);


then you would have to get the index of the key when requested:

int index = keys.IndexOf(key);
object value = values[index];


Does this make sense?
Was This Post Helpful? 1
  • +
  • -

#5 Imdsm  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 103
  • View blog
  • Posts: 362
  • Joined: 21-March 09

Re: implementing a hashtable using arrays

Posted 04 September 2010 - 02:35 PM

Further to this:

class HashtableEx
{
    private List<object> keys = new List<object>();
    private List<object> values = new List<object>();

    public object Get(object key)
    {
        int index = keys.IndexOf(key);
        return values[index];
    }

    public void Add(object key, object value)
    {
        keys.Add(key);
        values.Add(value);
    }

    public void Remove(object key)
    {
        int index = keys.IndexOf(key);
        keys.RemoveAt(index);
        values.RemoveAt(index);
    }

    public void Clear()
    {
        keys = new List<object>();
        values = new List<object>();
    }
}


and

HashtableEx ht = new HashtableEx();

ht.Add("hello", "world");

object obj = ht.Get("hello");

Console.WriteLine("Value of \"hello\": {0}", obj);
Console.WriteLine("Type of \"hello\": {0}", obj.GetType());
Console.ReadKey();


Outputs:

Value of "hello": world
Type of "hello": System.String

Was This Post Helpful? 1
  • +
  • -

#6 Imdsm  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 103
  • View blog
  • Posts: 362
  • Joined: 21-March 09

Re: implementing a hashtable using arrays

Posted 04 September 2010 - 02:43 PM

You can actually upgrade this using indexers like so:

class HashtableEx
{
    private List<object> keys = new List<object>();
    private List<object> values = new List<object>();
        
    public object this[object key]
    {
        get
        {
            int index = keys.IndexOf(key);
            if (index == -1) return null;
            else return values[index];
        }
        set
        {
            if (keys.Contains(key))
            {
                int index = keys.IndexOf(key);
                values[index] = value;
            }
            else
            {
                keys.Add(key);
                values.Add(value);
            }
        }
    }

    public object Get(object key)
    {
        int index = keys.IndexOf(key);
        return values[index];
    }

    public void Add(object key, object value)
    {
        keys.Add(key);
        values.Add(value);
    }

    public void Remove(object key)
    {
        int index = keys.IndexOf(key);
        keys.RemoveAt(index);
        values.RemoveAt(index);
    }

    public void Clear()
    {
        keys = new List<object>();
        values = new List<object>();
    }
}


With this usage code:

HashtableEx ht = new HashtableEx();

ht["hello"] = "world";

Console.WriteLine("Value of \"hello\": {0}", ht["hello"]);
Console.WriteLine("Type of \"hello\": {0}", ht["hello"].GetType());

Console.ReadKey();


Which outputs:

Value of "hello": world
Type of "hello": System.String

Was This Post Helpful? 3
  • +
  • -

#7 megglz  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 11
  • View blog
  • Posts: 414
  • Joined: 22-August 08

Re: implementing a hashtable using arrays

Posted 04 September 2010 - 03:02 PM

thank you very much :)
Was This Post Helpful? 1
  • +
  • -

#8 Imdsm  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 103
  • View blog
  • Posts: 362
  • Joined: 21-March 09

Re: implementing a hashtable using arrays

Posted 04 September 2010 - 03:03 PM

Most welcome :)
Was This Post Helpful? 0
  • +
  • -

#9 tymek  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 1
  • Joined: 22-June 12

Re: implementing a hashtable using arrays

Posted 22 June 2012 - 09:22 PM

This is a good solution except it is not a hash table and it doe not use arrays :))

It is a dictionary and not a very good good one. For example, handling duplicates is pretty much random.
Was This Post Helpful? 1
  • +
  • -

#10 eclipsed4utoo  Icon User is offline

  • Not Your Ordinary Programmer
  • member icon

Reputation: 1524
  • View blog
  • Posts: 5,960
  • Joined: 21-March 08

Re: implementing a hashtable using arrays

Posted 23 June 2012 - 04:07 PM

View Posttymek, on 23 June 2012 - 12:22 AM, said:

This is a good solution except it is not a hash table and it doe not use arrays :))

It is a dictionary and not a very good good one. For example, handling duplicates is pretty much random.


1. You can't really use arrays for what the OP wanted. Arrays aren't dynamically sized like Lists and dictionarys. Just because he asked for it, doesn't mean he knows what he wants.

2. Dictionaries and HashTables are essentially the same. Dictionaries use a HashTable internally.

Yes, the code posted does not handle duplicates, but we aren't here to post full code samples. We like for the members to do a little on their own.
Was This Post Helpful? 0
  • +
  • -

#11 Momerath  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1012
  • View blog
  • Posts: 2,444
  • Joined: 04-October 09

Re: implementing a hashtable using arrays

Posted 23 June 2012 - 11:26 PM

View Posteclipsed4utoo, on 23 June 2012 - 04:07 PM, said:

1. You can't really use arrays for what the OP wanted. Arrays aren't dynamically sized like Lists and dictionarys. Just because he asked for it, doesn't mean he knows what he wants.

Actually, almost all implimentations of a Hashtable are done with arrays. In .NET they use an array of System.Collection.Hashtable.bucket to hold the items and resize the array as more items are added (and don't handle collisions).

eclipsed4utoo said:

2. Dictionaries and HashTables are essentially the same. Dictionaries use a HashTable internally.

Dictionary<TKey,TValue> uses a complicated set of arrays of type bucket, entry and dictionary (lower case d) to hold the data. Again, no handling of duplicates.
Was This Post Helpful? 0
  • +
  • -

#12 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2118
  • View blog
  • Posts: 3,244
  • Joined: 21-June 11

Re: implementing a hashtable using arrays

Posted 24 June 2012 - 01:02 AM

View Posteclipsed4utoo, on 24 June 2012 - 01:07 AM, said:

2. Dictionaries and HashTables are essentially the same. Dictionaries use a HashTable internally.


The Dictionary class is a hash table, yes. But not everything that implements IDictionary is a hash table and in my mind everything that implements IDictionary can reasonably be referred to as a dictionary.

The class written by Imdsm most certainly isn't a hash table (though it might very well be extended to implement the IDictionary interface).
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1