data Structures / Hash functions

This is a discussion on data Structures / Hash functions within the A Brief History of Cprogramming.com forums, part of the Community Boards category; ok, let me start out by first sying that I'm not looking for any help doing my homework, but instead ...

  1. #1
    Registered User
    Join Date
    Sep 2001
    Posts
    17

    Question 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.
    Thanks,

    -Rick

  2. #2
    Just one more wrong move. -KEN-'s Avatar
    Join Date
    Aug 2001
    Posts
    3,230
    >>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#?

  3. #3
    Registered User
    Join Date
    Sep 2001
    Posts
    17

    hashing

    you are correct ken....wrong board

    I should have posted this in the c board

    sorry
    Thanks,

    -Rick

  4. #4
    the hat of redundancy hat nvoigt's Avatar
    Join Date
    Aug 2001
    Location
    Hannover, Germany
    Posts
    3,138
    This is a general matter... it has nothing to do with the language
    hth
    -nv

    She was so Blonde, she spent 20 minutes looking at the orange juice can because it said "Concentrate."

    When in doubt, read the FAQ.
    Then ask a smart question.

  5. #5
    Former Member
    Join Date
    Oct 2001
    Posts
    955
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem with unaligned intrinsics
    By The Wazaa in forum C++ Programming
    Replies: 4
    Last Post: 02-18-2009, 11:36 AM
  2. Replies: 2
    Last Post: 02-28-2006, 01:01 PM
  3. Need some help regarding data structures
    By Afrinux in forum C Programming
    Replies: 15
    Last Post: 01-28-2006, 04:19 AM
  4. Data Structures C++ Book
    By Cprogrammer in forum C++ Programming
    Replies: 1
    Last Post: 09-16-2005, 12:50 AM
  5. Data Structures Debugging
    By 0rion in forum C Programming
    Replies: 15
    Last Post: 08-28-2004, 10:36 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21