data Structures / Hash functions

ok, let me start out by first sying that I'm not looking for any help doing my homework, but instead I need to understand the hashing function of data structures.

With the help of other members on this site, I have been supplied with links to good references, but for some reason I cannot grasp the concept of hashing.

For example I need to understand how to determine a hash address, and how to determine if a collision has occurred, and of course how to handle the collision.

My books are really not helping me, so i'm hoping that someone can either point me in a good direction of reading material, or explain to me what is going on.

Any help would be greatly appreciated.

>>I'm not looking for any help doing my homework

homework in C#? that'd be amazing. And this shouldn't be in this board, I don't think...are you sure you want to learn how to do it in C#?

you are correct ken....wrong board

I should have posted this in the c board

sorry

This is a general matter... it has nothing to do with the language :)

well, I'm not sure about what you know, but hashing (as far as I know) is a method for extremely-fast searching, and it consists of giving each input value a unique number, based on the contents of the object you want to store, when you get this number, you associate it with a list, and store it in the index that corresponds to the number you got, the best idea for doing this is using pointers. Each time the user enters a new value, the program must:

-find the number associated with the object
-append the object (or a description of it, anything which can help you to determine whether the value the user searched matches or not the value stored in the table) at the end (or at the beggining) of the hash queue
-Do any other cleanups you must do (such as upgrading the number-of-values counter.

So, when the user searches for a precise value, you must find the number which is associated with your object, look up the index in your hash table, and start searching linearilly (one by one) in that index, and checking if the object which was searched matches the one you're checking.

it would be something like this (in C++):

Code:

---


#include <string.h>

int amount[100]; //In this array, we're going to store the amount of objects appended to
                //any index of our hash table

struct objects
{
        char text[100];        //We're going to do strings
        objects* next;        //The pointer to the next structure
};

objects hash[100];
objects object[100000]; //this is the maximum amount of objects
int g;                        //The amount of objects stored

int ClearHash()
{
        memset(hash,0,sizeof(hash));
        memset(anount,0,sizeof(amount));
        g=0;
        return 0;        //We want to do ANSI, don't we? :)
}

int GetNumber(char* s)
{
        int l=strlen(s);
        int n=0;
        /*
        This is just a suggestion of what kind of encoding
        you could use, but you're free to use any kind of encoding
        you want.
        */
        for(int i=0;i<l;i++)
        {
                n+=(int)(s[i]);
        }
        return n%100;        //The maximum index possible is 99, so, if the value is greater
                        //than 99, we should cut it to fit our hash table.
}

int AddObject(char* s)        //The new string
{
        int n;
        strcpy(object[g]->text,s);        //We suppose that is is up to 99 characters long
        n=GetNumber(s);
        //We're going to do a little trick in here: open the chain at the beggining and place
        //our object in the middle
        object[g].next=hash[n].next;
        hash[n].next=&object[g];
        //OK!, now our object is on the right place.
        g++; //Update our counters
        amount[n]++;
        return 0;        //For an ANSI compliant program
}

int LookupObject(char* s)        //The string we're searching for
{
        int n=GetNumber(s);
        object* o;
        o=hash[n].next;        //We're only going to check the objects whose value corresponds to the value of our search
        for(int i=0;i<amount[n];i++) //I'm not sure if it's < or <=
        {
                if(strcmp(o->text,s)==0)
                {
                        return 1;        //FOUND!!!
                }
                o=o->next;        //Go to the next value in our hash table
        }
        return 0;        //Search string not found!
}

---

the problem with doing hash tables is that modifying or erasing values is a little boring, but it can also be done.

I hope that you understand this, if you don't, please, don't hesitate to tell me!

whoof, this is a new record for me!!! 3272 characters long!

Oskilian