This week's giveaway is in the Android forum.
We're giving away four copies of Android Security Essentials Live Lessons and have Godfrey Nolan on-line!
See this thread for details.
The moose likes Beginning Java and the fly likes hashing problem Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "hashing problem" Watch "hashing problem" New topic
Author

hashing problem

Iain Palmer
Ranch Hand

Joined: Jul 28, 2004
Posts: 56
I've been given an assignment
A program is required that uses a list of student objects. The student object needs to store the student�s name and the course they are enrolled upon at a college. The hash index needs to be calculated within the student object. The hash index is calculated using the student name as a key.

The Hashing Assignment files, centre around the Student class which represents a single student who has a name and a course. This public class should be in a source code file with the following name.....

Student.java

Multiple instances of the Student class are added to a single instance of the Storage class. This public class should be in a source code file with the following name.....

Storage.java

Both of the above classes should only be instantiated by the MainProgram class. This public class should be in a source code file with the following name.....

MainProgram.java

It makes sense to begin designing the whole program beginning with the Student class, as neither of the other two classes would function correctly if the Student class didn't produce the output which was expected. Once the Student class is fully tested using a separate test class, the Storage class should be designed, and then finally tested.
Ive been looking at this program for a coouple of weeks and couldn't get seem to get it right. I finally wrote one class and got it to work but am unsure if this is what is required if it is great, if not what is needed?
here is the single class

Jimmy Die
Ranch Hand

Joined: Nov 20, 2003
Posts: 97
Hi,


You can readily define some algorithm in student class to make some unique key for your hash table.



Now maybe my algorithm makes all unique keys and then again maybe a collision will occur (duplicated keys)...

In you hashTable class you will need to handle this.

Your hash class should

-determine the size and table.
~I'll assume you will use open addressing to simplfy.
-create a insert method
-hash your key out so the number is smaller. int hashValue getKey() % size of the array.
-formulate a solution for collisions if one hashValue == second hashValue insert the second hash value some other array index. (perhaps next array element, or quadradic probing if you are up to it.)
-create a find() method to unhash what you just did when you inserted the key.

I think what you have done is great, however I read that you need seperate classes. Make your classes and if you're stuck just write back.


Jimmy Die
Iain Palmer
Ranch Hand

Joined: Jul 28, 2004
Posts: 56
I've got the student class

I am testing it with a class called Test.java here is this class
Iain Palmer
Ranch Hand

Joined: Jul 28, 2004
Posts: 56
I'm having a problem with the Storage class. I've set up the array for the student's name,course & hash code, but when i try to print out the array. I get
Student :1 null [I@1df354 [Ljava.lang.String@5225a7
obviously the arrays are not getting passed to the storage class but why?
Here is the storage class
David Harkness
Ranch Hand

Joined: Aug 07, 2003
Posts: 1646
I didn't see anything in your writeup that specified that you must implement your own hash table. If not, Java has one ready made for you (HashSet) and another that maps values to hashed keys (HashMap).

Assuming, however, that you must write your own, it should store Student instances -- not the names and courses of Students. The Student class's job is to store a single student's name and course and provide a hashing algorithm for Storage to use. In Java, the Object class defines the "int hashCode()" method which you should override instead of defining your own method name. This way it can be used with the Java Collections framework, and others will expect to see it named hashCode().

[ Side note: getter methods that return a property of an object are typically named "get<Property>": getName and getCourse. Again, this is a standard that you might want to get used to before you develop the wrong habits. ]

In your Storage class there are a few issues. The constructor says it takes a size parameter, but it doesn't. It assigns its initial size (0) to itself which has no effect.

It also declares fields like those in Student (studentName and course) and uses them in addStudent. Instead, addStudent should take a Student parameter. You'll need to alter the algorithm as currently it loops through the arrays, setting each slot's value to the same value, wiping out any previous values.

Finally, the printArray() prints "[I@1df354" and "[Ljava.lang.String@5225a7" because you are telling it to print an array -- not an array slot. You need to reference a specific slot index on all of the arrays.

Again, verify that you must write your own hash table before continuing. If you can use the Java Collections this assignment becomes vastly simplified. Your Storage class would have a few one-line methods.
Iain Palmer
Ranch Hand

Joined: Jul 28, 2004
Posts: 56
I've created a Hash Set but i can't seen to add the Hash Value to the Hash Set.
Jimmy Die
Ranch Hand

Joined: Nov 20, 2003
Posts: 97
Hi,


The documentation shows that the add() needs to take a object, however you have passes an int primitive so that will not work.

If you use the approach that david suggest then also you must override the hashCode() method in your student class (he mentioned this also). hashCode() is inherited from from the class 'Object'. Read in your documentation about the hashCode() and also equals(). There are some general rules to make sure that everything will work. It is not so complicated so check it out. I think your almost there so good luck!
David Harkness
Ranch Hand

Joined: Aug 07, 2003
Posts: 1646
Iain, I highly recommend you check out Sun's Collection tutorial and/or the Collections trail here at JavaRanch. No time to track down the links this time, but they're always in the top few at Google. They will explain exactly how a HashSet operates and what it requires of your objects.
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
Although there is nothing in the original post that specifically says you need to implement a hash table yourself, I'd be willing to bet that you still do. At least, that's the way I read it. Partly because it doesn't sound like you need to override the hashCode() method, which is exaclty what you would need to use HashTable in the first place. However, It might help to use HashTable as an outline for the methods (and the arguments they take) that you might want to use in your Storage class.

With that said, I'd like to back up to your Student class. I see that the calculateHash() takes a String argument for the name. However, the Student class also has a name member field. This seems like a bad idea to me because when another method calls calculateHash() it is possible to pass a different name than the Student object has. This is a possible source of a very big headache. Instead, the calculateHash() should take NO parameters and use the member field called name to calculate the hash value.

You should check to see if you need to implement the hash table code yourself, rather than using HashSet. Either way, there is a slight problem with the addStudent() method in your Storage class. As the name of this method implies, it should add a Student object to the internal storage, correct? How does it know which Student to add? At the moment this method only takes an int as an argument. Would it make more sense to take a Student object as an argument instead? Notice that if it does, then you can call Student.calculateHash() to get the hash code for the object passed in.

Also, I see that the Storage class contains several fields like studentName, course, and hashValue that are applicable to a SINGLE student. However, from what I understand, the Storage class is supposed to store MANY students. At the moment, that is what the HashSet is for, right? I think you can just get rid of studentName, course, and hashValue since those fields don't have anything to do with the Storage class.

Next, I see a problem with the Storage constructor:

The problem here is that "this.size=size;" doesn't accomplish anything. Both "this.size" and "size" refer to the same member variable. This line of code just assigns a value to itself. From the comment, it looks like you need to accept the size of the array as a parameter. If you make this change, then it will probably do what you are thinking of.

However, the comment also indicates that you need an array. I think this is the crux of the problem. You should use an array to implement your own hash table instead of the built-in HashSet class. In doing so, you will use the value returned from Student.calculateHash() in order to figure out which index in the array to use. Then you also have to deal with collisions and other complications. However, we should probably wait a little before we get into those details. Take a look at my other suggestions above before moving on with this.

Keep Coding!

Layne


Java API Documentation
The Java Tutorial
Maureen Charlton
Ranch Hand

Joined: Oct 04, 2004
Posts: 218
This looks similiar to a program I had to write.

When I first attempted it I went off in the wrong direction of using HashMap/Hashset. It is my understanding this is not needed. Nor is overriding or overloading of any methods.

The Student class has a constructor
Student (String studentName, String studentCourse)

The Student class also has a method that calculates the hashCode from the Upper case Student name, accepting the size of the Students array
public int hashCode (int numStudents)

As mentioned above you need to be aware that it is possible to generate the same hash index for two different names i.e. JOHN DOE and JOE DOHN. However I didn't address this in the Student class. I addressed this in the Storage class.

The MainProgram class uses JOptionPane (equivalent of your Test class above)
The size of the array i.e. the number of students is declared here (it can be 3 or 4; whatever).

Please do not think about dynamic arrays i.e. where the size of the array is NOT declared. If this is a similiar assignment then they are happy with the array size being declared.

The studentName and studentCourse is entered in the MainProgram using JOption pane, and passed to the Storage class. The Storage class uses the hash index calculated within the student object to store object within array. Collisions i.e. names with the same hashCode need to be addressed here.

Hopefully the above helps without me giving too much away as I think you learn a great deal with doing this assignment (especially from people who respond in this forum); but most people find it difficult so early on in the course. If this is the same assignment the requirement is not clear and assumptions have to be made i.e. arraySize = 6; (these I usually put as a comment at the top of my program and mention again in my test program).
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
The Student class also has a method that calculates the hashCode from the Upper case Student name, accepting the size of the Students array
public int hashCode (int numStudents)

Personally, I think it would be better to change this method to not take any parameters. Then the Storage class would be responsible for manipulating the returned value based on the size of its internal array. In my opinion, this makes the Student class too dependent on external information that really isn't necessary.

Layne
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: hashing problem
 
Similar Threads
Hashing Index
Calling a method
Hashing Problem
calling a method
Hashing Storage