Thread: data Structures / Hash functions

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