locked
Do HashTables contain Collision Resolution? RRS feed

  • Question

  • I have been trying to figure this out without any success, and msdn says that these functions are built in, but does the .NET 2.0 framework have collision resolution for a Hashtable or Dictionary?  Maybe I am missing the method for utilizing it but all I do is the .Add() function.  Here is an example below:

    private Hashtable HTable = new Hashtable();

    static void Main(string[] args)
    {
              HTable.Add("A", "Justin");
              HTable.Add("B", "Robert");
              HTable.Add("C", "Scott");
              HTable.Add("A", "Rich");

              return 0;
    }


    I get an error "ArgumentException", stating that an argument has already been added.  The key value of 'A' already exists, which I know and I want it to perform the collision resolution.  However nothing happens.  Is there a step that I am missing here?  Is the collision resoluiton process the same for a Hashtable as well as a Dictionary?

    Please help because I am truly confused on what to do without building in my own functions to fix this error.
    Monday, August 6, 2007 1:48 PM

Answers

  •  RichardSny wrote:
    So what you are saying is that the built in hashing function can return, in rare instances, the same key vaule for insertion when passed different values.  In that case the built in collision resolution works.

     

    Absolutely. The hash value is an int, so there are "only" 2^32 unique values to choose from.


     RichardSny wrote:
    What if I want to perform an insert and the key 'A' will have multiple values associate with it what do I do?

     

    You could keep them in an array or list and store that in the hashtable instead.

     

    Or you could use a more appropriate collection type, such as the MultiDictionary in the Power Collections library.

    Monday, August 6, 2007 2:59 PM
  • This is how Hashtables work: they assign a single value to a single key. "Collision resolution" is a term for the behind-the-scenes processing, which occurs when two different keys result in the Hashtable class computing identical hash values. This is not uncommon; only perfect hash functions can create unique hashes for each key, and building those usually requires knowing something about the character of the underlying (and usually limited) data set.

     

    You don't want "collision resolution"; you simply want to associate a key with a collection instead of a scalar. If you want to associate multiple values to a key, use a generic Dictionary class, and make the value some sort of collection object instead of a scalar value. E.g., this will allow you to associate a List<String> with a key:

     

    Dictionary<String, List<String>> dictListTable = new Dictionary<String, List<String>>();

    dictListTable.Add("A", new List<String>());

    dictListTable["A"].Add("Justin");

    dictListTable["A"].Add("Rich");

     

    You can do this with the old Hashtable class too, but you'll be forced to convert back and forth between object and the specific classes you use. The generic implementation is much cleaner.

     

    HTH,

     

    -J-

    Monday, August 6, 2007 3:01 PM

All replies

  • If you want to replace the existing value for the "A" key, use the indexer. HTable["A"] = "Rich".

     

    Collision resolution is used when multiple different keys result in the same index used for the hashtable's internal storage, which isn't the case here.

     

    Monday, August 6, 2007 2:19 PM
  • So what you are saying is that the built in hashing function can return, in rare instances, the same hash code vaule, for insertion into the talbe, when passed different key values.  For example:
    Key1 = Today,          HashValue = 1234
    Key2 =  Yesterday,   HashValue = 1234

    In that case the built in collision resolution works.  If I am on the same page with you let me try and fine tune my question.

    What if I want to perform an insert and the key 'A' and will have multiple values associate with it what do I do?  Is there a built in ability to allow for multple storing or do I have to create my own ability.
    For instance:

    static void Main(string[] args)
    {
              HTable.Add("A", "Justin");
              HTable.Add("A", "Robert");
              HTable.Add("A", "Scott");
              HTable.Add("A", "Rich");

              return 0;
    }



    Can I do this?
    Monday, August 6, 2007 2:25 PM
  •  RichardSny wrote:
    So what you are saying is that the built in hashing function can return, in rare instances, the same key vaule for insertion when passed different values.  In that case the built in collision resolution works.

     

    Absolutely. The hash value is an int, so there are "only" 2^32 unique values to choose from.


     RichardSny wrote:
    What if I want to perform an insert and the key 'A' will have multiple values associate with it what do I do?

     

    You could keep them in an array or list and store that in the hashtable instead.

     

    Or you could use a more appropriate collection type, such as the MultiDictionary in the Power Collections library.

    Monday, August 6, 2007 2:59 PM
  • This is how Hashtables work: they assign a single value to a single key. "Collision resolution" is a term for the behind-the-scenes processing, which occurs when two different keys result in the Hashtable class computing identical hash values. This is not uncommon; only perfect hash functions can create unique hashes for each key, and building those usually requires knowing something about the character of the underlying (and usually limited) data set.

     

    You don't want "collision resolution"; you simply want to associate a key with a collection instead of a scalar. If you want to associate multiple values to a key, use a generic Dictionary class, and make the value some sort of collection object instead of a scalar value. E.g., this will allow you to associate a List<String> with a key:

     

    Dictionary<String, List<String>> dictListTable = new Dictionary<String, List<String>>();

    dictListTable.Add("A", new List<String>());

    dictListTable["A"].Add("Justin");

    dictListTable["A"].Add("Rich");

     

    You can do this with the old Hashtable class too, but you'll be forced to convert back and forth between object and the specific classes you use. The generic implementation is much cleaner.

     

    HTH,

     

    -J-

    Monday, August 6, 2007 3:01 PM
  • Great, that is just what I was thinking.  I will look into the MultiDictionary since I have never heard of it before but thanks again for your help.
    Monday, August 6, 2007 3:02 PM
  • I was just reading my C# book and noticed that a NameValueCollection seems to do exactly what I want when it comes to this particular problem.  It allows for multiple values to be stored per a single key.
    Monday, August 6, 2007 4:42 PM