Thread: data Structures / Hash functions

  1. #1
    Registered User
    Join Date
    Sep 2001

    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.


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


    you are correct ken....wrong board

    I should have posted this in the c board



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

    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
    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++):

    #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()
    	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++)
    	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
    	//We're going to do a little trick in here: open the chain at the beggining and place
    	//our object in the middle
    	//OK!, now our object is on the right place.
    	g++; //Update our counters
    	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 <=
    			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!


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, 12:36 PM
  2. Replies: 2
    Last Post: 02-28-2006, 02:01 PM
  3. Need some help regarding data structures
    By Afrinux in forum C Programming
    Replies: 15
    Last Post: 01-28-2006, 05: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