Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!usc!julius.cs.uiuc.edu!ux1.cso.uiuc.edu!osiris.cso.uiuc.edu!gordon
From: gordon@osiris.cso.uiuc.edu (John Gordon)
Newsgroups: comp.lang.c
Subject: Re: Hash??? Not quite clear on what this is...
Message-ID: <1990Nov22.235522.26487@ux1.cso.uiuc.edu>
Date: 22 Nov 90 23:55:22 GMT
References: <17291@netcom.UUCP>
Sender: news@ux1.cso.uiuc.edu (News)
Organization: University of Illinois at Urbana
Lines: 43

avery@netcom.UUCP (Avery Colter) writes:

>I'm seeing all this talk of "Hash Functions".

>Are you talking about parsing? What is being defined as "hashing"?

	Oh, goody.  We talked about hashing the last 2 weeks in class, so I
get to explain it.

	Hashing is: a method of storing items in an array such that they can
be quickly recalled when needed.  This is possible because hashing performs a
transmogrification (:-)) on the item and comes up with an array address, so
you can go get it directly without having to search for it.  

	Example:
	
	Let's say that your whole data set consists of the words: "I", "am", 
"the", "best", "programmer".  You want a function to store these words in an
array, and to be able to pick any one out without searching.  Well, a good
function for this would be to put the word in the [strlen()]'th position.  Do
you see how this would result in each word being in its own location?  "I" 
would be in slot #1, "am" would be in #2, etc.  So, if you are looking for
the word "I", you would apply the hash function and come up with 1, and you
would look in array element 1, and there it is!
	So, to reiterate: A hash function's puprpose is to be able to take 
data items and perform some operation on them, resulting in an array address to
store that item in.  This is good because you do not have to search for the
desired item, you can find out exactly where it is and get it.

	NOTE: The above example is not realistic, for several reasons:
	1) The data set is ridiculously small.
	2) Many times you do not know the data set beforehand.
	3) hash functions never use something so simple as strlen().  They
	   break the item down into bits and twiddle them to produce the
	   array address.


---
John Gordon
Internet: gordon@osiris.cso.uiuc.edu        #include <disclaimer.h>
          gordon@cerl.cecer.army.mil       #include <clever_saying.h>

"Gee, ralph, how many flames do ya think THIS post will get??"