| Assignment • FAQ • Development Guide • Code • Checklist • |
Question:
Do I have to worry about testing the hash table with sizes that are not prime?
Answer:
You do not have to check that the size of the HashTable is prime. If the number is not prime, then the table will still work, but you just may not be able to use all the spaces in the table. We will only be testing your program with a table size that is prime.
Question:
How should we handle the case of insertion into a full hash table?
Answer:
This depends on whether the insertion results in an error or not. If the user is performing a duplicate insertion, there should be no error.
However, for any non-duplicate insertion there will be an error. In this case you will need to print out an error message to the user.
Question:
Please explain how the hashing algorithm works.
Answer:
The initial hashing location in the table is accomplished by via a mod of a numeric attribute (sum of ASCII codes) by the size of the hash table:
initialLocation = numericAttribute % tableSize
The increment value is obtained by modding the numeric attribute by the size of the hash_table and then adding one:
increment = (numericAttribute % (tableSize - 1)) + 1
Each subsequent location is achieve by adding the increment value to the current index and then modding by the size of the hash table:
newIndex = (currentIndex + increment) % tableSize
The numeric attribute from the element will be attained by a statement like:
attribute = element.hashCode ();
where element is the Base Pointer parameter.
Question:
I am having trouble creating the UCSDStudent class. I am not really sure if I am including all the things you want in this class.
Answer:
You should modal your UCSDStudent class on the Variable class in the provided Calculator.java. It should be VERY similar to Variable. Of course, you will want to change the names of data fields (as students dont have a "value") and get rid of methods which don't make sense for a UCSDStudent.
Question:
I am a little bit confused about why we have to extend from the Base class. You said we have to because the HashTable uses the getName method. But doesn't the Hash Table have to use equals and hashCode also?
Answer:
Yes, it does. But these methods are already defined in Java's Object class. We are just overwriting them. The HashTable knows nothing about the data fields of the pointer to the item that is stored within it. The items being stored in the HashTable know nothing about the data fields of the HashTable. The interface of communication between the pointers to the items in the HashTable and the HashTable itself are via redefinition of the virtual functions of Base redefined within the derived classes of Base (ex: UCSDStudent, Variable). When redefining virtual functions in derived classes, the parameter types, the return type and the function name must all be identical to those of the virtual function as it was originally defined.
Question:
So I understand that we have to use the equals function, but I don't understand how I should call it on the table. Is it a hash table or a base function?
Answer:
You are comparing two objects in the Hash Table, so it should be a function of the objects in the table. Therefore, you will have a line of code like:
if (table[index].equals (element))...
where table[index] is an item in the table, and element is the Base pointer parameter. At run-time, the function that is called is the "equals" function redefined within the derived class of Base (ex: UCSDStudent, Variable).
| Assignment • FAQ • Development Guide • Code • Checklist |