Hashtable hash-function implementation in C#

Question

I have array of random numbers from 100-1001 , which i transfer to hash table. Hash function is mod from n ( which is size of array ). The problem is, when im trying to check what is inside hashtable, it shows me different indexes from i have calculated on paper, so im confused if it works correct or not. Also as i was told, size of hash table must be at least 5% bigger than size of array, but i cannot find how to set hashtable size. Where do i have a mistake? Ill have to search value by address using same hash-function after that.

    static void Main()
    {

        int n;

        Console.WriteLine("Please enter array size");
        n = Convert.ToInt32(Console.ReadLine());

        Random rnd = new Random();
        int[] a = new int[n + 4];

        for (int i = 0; i < n; i++)
            Console.Write("{0,4}", a[i] = rnd.Next(100, 1001));    
        // I have deleted code in the middle as there is certain type of search in array which works fine

        // Now putting values to hash table       

        Hashtable Hashtable = new Hashtable();
        int hashcode = n + ((n / 100) * 5);
        int value; 
        int key;
        for (int i = 0; i < n; i++)
        {
            value = a[i];
            key = value % hashcode;

            if (Hashtable[key] == null)
                Hashtable.Add(key, value);
            else
            {
                while (Hashtable[key] != null)
                {
                    if (key == (hashcode - 1))
                        key = 0;
                    else
                        key++;
                }
                Hashtable.Add(key, value);
            }
        }

              Console.WriteLine();
    }

Answer 1

There seems to be a bit on confusion on how a hashtable works in .NET. A hashtable is an associative list. That means you can retrieve values by their keys, which is useful when an array or a list doesn't work, because you don't access values by their index (e.g. in a caching scenario). In order to quickly access the stored key/value pair, the hashtable internally calculates the hash code of the key to beable to store the data in buckets.

What you are doing is to calculate a "hash code" externally and then use it as a key to a hashtable. What the hashtable will do is to calculatate the hash code of that key to store the key/value pair. I'm pretty sure that's not what you want to do.

I would normally advise you to use a Dictionary<int, int>, but your case is different. Your key derives directly from the value you want to store, so your case is not a case for an assiciative list. I don't know exactly what you want to achieve, but your case looks most suited for a HashSet (that is a set that uses hash codes for storage of the values). You can override the GetHashCode method of your keys to change your hashing method, even though there is no necessity for that. In your case it will even degrade the efectiveness of the hash set, since your hash method is not only very poor, because it ranges for far less than the range of Int32, it will also cause a lot of collisions your hash set will have to work around.

Since you can not change the GetHashCodemethod of int, you have to create a wraper for that:

private struct HashCodeWrapper {
    private readonly int value;
    private readonly int n;

    public int Value {
        get {
            return value;
        }
    }

    public HashCodeWrapper(int value, int n) {
        this.value = value;
        this.n = n;
    }

    public override int GetHashCode() {
        return value % (n + ((n / 100) * 5));
    }

    public override bool Equals(object obj) {
        return (obj is HashCodeWrapper) && ((HashCodeWrapper)obj).value.Equals(value);
    }
}

You can then create a HashSet<HashCodeWrapper> and add your wrappers to the set. If that doesn't work for you you have to implement your own version of a "hashtable".

But for all practical purposes, just use a HashSet<int> and save yourself a lot of work.