[mattlyons]

Got a test tomorrow and this is on the study guide. The question is:

"Define a table size and a reasonable hash function for the following problem. We need to store and retrieve Human Resource objects for up to 1000 employees using the SSN (nine-digit integer) as the key."

I don't remember him going over stuff like this so I am kinda lost. Help is needed! Thanks in advance guys.

HashTable <Integer> hashtable = new HashTable <Integer>(1500);

I don't even know how to define a hash function. I know what a hash function is but not how to define one. Help please!

This post has been edited by mattlyons: 07 April 2010 - 08:18 PM

[macosxnerd101]

Don't forget that HashTables accept two generic types- Key and Value. So your HashTable declaration should look more like HashTable<K,V>, where you replace K and V with reference data types.

As for your hash function question, you are basically being asked to write an algorithm to map Keys to Integers, usually consecutive indices like in an array. The Wikipedia Page has a good graphic depicting this if you want to check it out.

[mattlyons]

Okay that makes sense. So lets say I do the last 3 digits of the SSN (since first three are similar to people in same areas) will be the Key. How would I actually write that down? Or do I just write it out in words like I just did?

[pbl]

And the class name is Hashtable not HashTable

[mattlyons]

Oh okay thanks. Simple mistake there.

Still have the above question if anyone can help.

[pbl]

mattlyons, on 07 April 2010 - 09:22 PM, said:

Okay that makes sense. So lets say I do the last 3 digits of the SSN (since first three are similar to people in same areas) will be the Key. How would I actually write that down? Or do I just write it out in words like I just did?

If you used the SSN as an int than

Hastable<Integer, Employe> hash = new Hashtable<Integer, Employe>(1000);

assumming you have a class Employe to store your employes' data

[mattlyons]

That means that line of code pbl just did would define the Hashtable. Now how would I actually "define" the hash function? I know the hash function would be the last 3 digits of the SSN. Do I "define" the hash function in code or simply as: "The last 3 digits of each SSN."

If it came up on the test tomorrow to tell what the hash function is, how would I mark it on the test. That is where I am having the problem.

[pbl]

mattlyons, on 07 April 2010 - 10:41 PM, said:

That means that line of code pbl just did would define the Hashtable. Now how would I actually "define" the hash function? I know the hash function would be the last 3 digits of the SSN. Do I "define" the hash function in code or simply as: "The last 3 digits of each SSN."

If it came up on the test tomorrow to tell what the hash function is, how would I mark it on the test. That is where I am having the problem.

You let the Java Hashtable class do it for you
If you want to rewrite your own this is a completly different other story
and then you can actually name your own class HashTable with a capital T and look at macosxnerd101 links if you want to do the hashing yourself

[macosxnerd101]

What is the scope of your course? What exactly did you cover in regards to hashing in class? If you covered specific hash algorithms, I would use those. However, if you only covered the basic principle of hashing, I would store the keys into an array and sort them, so that you have an easy perfect hash function as you can use Arrays.sort() or Collections.sort() to do the sorting for you.

[mattlyons]

I think I might have figured it out after reading both of your posts. Would this be a hash function:

Hash(key) = 1000 % key

?

[macosxnerd101]

That would be a hash function, though it would not create a perfect hash, as the keys 996 and 6 would return the same results- 4.