Solved

# Hash Table

Posted on 2004-04-23
2,824 Views
Hello again,

Sorry it's been so long!  Okay, happiness with Hash Tables... I don't really know where to begin.  I think what I want to do with this one is start off with an easy hash table, and see if I understand it.  Let's start with an array... with linear hashing.  Linear hashing is when after the hash function has been computed, the object is placed in the next available position??

I was thinking... maybe the hash function will look something like:

hashKey = int % tableSize...

I need to go now, but I'll put up my codes when I get back.

-luna621 =^^=
0
Question by:luna621
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 54
• 21
• 4
• +3

Author Comment

ID: 10906523
Yay!  I'm back!  Here are my partial codes:

1. http://www2.hawaii.edu/~flam/Car.java <----------------- constructor class
2. http://www2.hawaii.edu/~flam/CarAgency.java <--------- main method
3. http://www2.hawaii.edu/~flam/CarInventory.java <------ hash table
0

Author Comment

ID: 10906530
Sorry, #3 should be:

3. http://www2.hawaii.edu/~flam/CarInventor.java <------ hash table

0

LVL 1

Assisted Solution

seanrowen earned 50 total points
ID: 10906580
First, Java itself provides hash table implementations for you -- if you want to implement a set of Cars (inventory), and want to use a hashtable so that you can efficiently see if a Car exists in the set, then just do three things:

1) Implement the methods "public boolean equals(Object o)" and "public int hashCode()" in Car. You can return the serial number, if that is what you want as a hash value.
2) Create a HashSet, and add Cars to it
3) Later, see if the HashSet contains a certain car

HashSet has a hash table inside it.

When you install the JDK you can install the source code. You may like looking at the HashSet / HashMap implementations and finding where the actual hash table is used.

You should be overriding Object's equals() method, whose signature is "public boolean equals(Object o)", rather than overloading it with "public boolean equals(Car otherCar)". That way you are implementing the standard Java equals() method.

Then, since you implement equals() in Car, you must implement hashCode() or else many Java classes, like HashSet, won't work properly with Car. It must be that when two Cars are equal (according to your equals() method), that they return the same value from hashCode(). The default implementation of hashCode(), which you haven't overridden, will return different values for different Car objects -- even those that are considered equal by equals(). So right now this doesn't follow the equals/hashCode contract.

Regarding linear probing -- yes this is one way to deal with collisions in a hash table. If a value hashes to a bucket that is already filled, you could simply iterate along the hash table until you find an empty bucket. This is a good idea when you know the hash table will be large relative to the number of items hashed into it... imagine what happens to inserts and lookups when it is nearly full.

The other option is chaining, whereby you simply put a chain of multiple elements into each bucket. This is good even when the hash table is full, but lookups can slow down if many elements hash to the same bucket. That's why a good hash function is important.
0

Author Comment

ID: 10906586
>I was thinking... maybe the hash function will look something like:
>
>hashKey = int % tableSize...

I guess I'm going to make the 'int' the car's serial number :)
0

Author Comment

ID: 10906600
seanrowen,

Thank you for your comment.  I understand that JAVA already has a built in HashTable function, but I want to write one myself -- that way I understand what it is doing.  I'm going with linear probing first, since I think it's easier to start there.  I will try chaining after I get linear probing down  :)

So, basically my question is how should I add the cars into the hash table?  I have an array, but how do I implement my has function...  I think the hash function is suppose to tell the program where to store the item, correct?

Something like this?:
-------------------------------------------------------
Car[hashKey] = new Car(12345, Toyota, 2004);

where hashKey = serialNumber % TABLE_SIZE;
0

Author Comment

ID: 10906629
You know with linear probing... if after the hash function is applied and the position is already filled, it will place the item in the next available spot - right?  Is there a way to tell what position that item is in?

|A| B|   |D|   |F|   |   |   |   |   |
0   1  2  3  4   5  6   7   8   9  10   <----- 11 positions total

Let's say I want to added element 'C' which has the serial number: 33

If I follow my hash function, hashKey = 33 % 11 = 0.  Position 0 is already taken by 'A', and position 1 is taken by 'B'.  So, 'C' will have to be placed in position 2.  Is there a way to know, if I view 'C' 's information, that it is stored in position 2?
0

Author Comment

ID: 10906675
Okay, I'm confusing myself.  In my CarInventory.java, I have:

addCar(int serialNumber, String makeModel, int year) {
...

Is this where I apply my hash function?
----------------------------------------------------------------------
private static final int TABLE_SIZE = 10; // size of hash table
private static int count = 0;  // keeps track of how many cars added

addCar(int serialNumber, String makeModel, int year) {
hashKey = serialNumber % TABLE_SIZE;
Car[hashKey] = new Car(serialNumber, makeModel, year);
count++;
0

Author Comment

ID: 10906677
hmm...
-------------------------------------------------------------------------
cannot resolve symbol
symbol  : variable Car
location: class CarInventor
Car[hashKey] = new Car(serialNumber, makeModel, year);
^
1 error
0

Author Comment

ID: 10906684
This is my constructor in Car.java:

/**
* constructor --- creates an object of Car.
*/
public Car(int serialNumber, String makeModel, int year) {
this.makeModel = makeModel;
this.year = year;
this.serialNumber = serialNumber;
} // end constructor
0

Author Comment

ID: 10906795
Okay, it's getting late.  I will continue working on this tomorrow.  See you then!!

-luna621 =^^=
0

LVL 23

Expert Comment

ID: 10906904
try here u wull get help...

http://www.braithwaite-lee.com/source/#Java

best of luck..

R.,K
0

Author Comment

ID: 10906907
Hehe... I lied.  Not asleep yet.  I updated my CarInventor.java.  Still not too sure how to add a particular Car to the array.  I made a 'key' though... thought that might help.
--------------------------------------------------------
http://www2.hawaii.edu/~flam/CarInventor.java
--------------------------------------------------------

Okay, going to sleep for real this time.  Good night, and see you tomorrow!!

-luna621 =^^=
0

Author Comment

ID: 10906918
rama_krishna580,

Thank you for the link.  I will take a look at it tomorrow.  Good night!!  =^^=
0

LVL 86

Expert Comment

ID: 10906964
The easiest way is to look at the source for the API Hashtable ;-)
0

LVL 1

Expert Comment

ID: 10907207
In your linear probing example, yes, say that car C hashes to bucket 0, but ends up in bucket 2 because 0 and 1 are taken. Later, when you see if car with serial number 33 exists in inventory, you again compute 33 % 11 and get 0. You look at bucket 0 and find that it does *not* have the car with serial number 33. So you follow the path it must have taken: look at 1, then 2, and then you find it.

This is what I mean when I say that linear probing performs badly when the hash table gets full. Also what happens if you delete items from the hash table? Things to think about...

Not sure what you are going for with:
Car[hashKey] = new Car(serialNumber, makeModel, year);

Do you mean to declare an array of Cars somewhere, and update that array?
Car[] theCars = new Car[11];
...
theCars[hashKey] = ...;
0

LVL 13

Expert Comment

ID: 10907377
Hi luna621,

Classic implementation of HashTable use an array of list.
Each list contains objects whose hashcode is the same and equals to the array index :

To add a car you can do :
And to remove it :
theCars[ hashKey(car) ].remove(car);
Testing if a car is in the hashtable :
theCars[ hashKey(car) ].contains(car);
For each list you can use java.util.Vector, or implement it yourself.

It's important to have a good hash function in order to avoid long lists. You can use the hashCode returned by all Objects instances:
int hashKey(Car car)
{
return car.hashCode() % theCars.length;
}

0

Author Comment

ID: 10910218
seanrowen,

>Not sure what you are going for with:
>Car[hashKey] = new Car(serialNumber, makeModel, year);
>
>Do you mean to declare an array of Cars somewhere, and update that array?
>Car[] theCars = new Car[11];
>...
>theCars[hashKey] = ...;
-------------------------------------------------------------------------------------------

Sorry for not explaining that better.  I was tired :)

What I want to do is add a Car to the array hash table using linear probing with the hash function:

hashKey = serialNumberOfCar % tableSize;
***************************************************************************

The Car object will contain the following information:

1. int serialNumber
2. String makeModel
3. int year

***************************************************************************
To remove, I'm just going to find the Car and set the position to null or -1 (something along those lines).

Question:  How do I add the object into the array?  Am I suppose to create the array in the addCar method, or do I do that in the main method?
--------------------------------------------------------
http://www2.hawaii.edu/~flam/CarInventor.java
0

LVL 23

Expert Comment

ID: 10910238
see here..all you can get u r answer..

http://www.cs.rit.edu/~ats/java-2000-1/html/skript-23.html

R.K
0

Author Comment

ID: 10910309
rama_krishna580,

Thank you.  I'll take a look at that as well :)

-luna621 =^^=
0

Author Comment

ID: 10910318
Okay, I updated my CarInventor.java again.  This time, I also created a removeKey method.  I was thinking, maybe if I knew which "bucket" the Car object was placed in, I could just remove it by setting that "bucket" to null or -1.

Question:  When I insertKey, I'm inserting into the hash function first, but if that "bucket" is filled, it will go to the next available position.  Is there a way to find out that "bucket" number?
0

Author Comment

ID: 10910324

http://www2.hawaii.edu/~flam/CarInventor.java
0

Author Comment

ID: 10910330
public int insertKey(int key) {
...
array[probe] = key; // everything A.OK!!  Insert!!
return probe;
} // end insertKey

Here, I'm returning the probe... which I think is the "bucket" number??
0

LVL 1

Expert Comment

ID: 10910745
probe would be the hash value of the object that you are inserting. Wouldn't you be inserting a Car instead of an int? You could return an int from this method, but there is no particular need to do so.

Regarding finding where an object ended up in the hash table -- no, there is no automatic way of knowing where it ended up later. You will have to likewise linearly search from the hash value bucket onwards to see if the object exists.

In the case of linear probing, think of the hash value as just a suggested starting point for finding an empty bucket, which is hopefully close to its actual location. This is how hash tables derive performance gains over a simple list.

Question for you -- when would you stop linearly searching for your object and decide it's not there? when you hit an empty bucket? sounds reasonable, but think about whether that works if you can remove objects from the hash table also. Linear probing gets complex if you can remove from the hash table.
0

Author Comment

ID: 10910835
seanrowen

>Question for you -- when would you stop linearly searching for your object and decide it's not there? when you hit an >empty bucket? sounds reasonable, but think about whether that works if you can remove objects from the hash table also. >Linear probing gets complex if you can remove from the hash table.

Hmm... I guess I can look at each object one-by-one until I reach TABLE_SIZE.  If I can't find the object, then the object's not in the array??  When I remove, I do the same thing - search one-by-one.  If it's there, I set it to null or -1.  If it's not there, then I spit out an error message??
0

Author Comment

ID: 10911016
Okay, I updated my main method so you can see what I'm trying to do.
---------------------------------------------------------------------------------
http://www2.hawaii.edu/~flam/CarAgency.java
0

Author Comment

ID: 10911193
Alrighty!  I found this code in a book.  This is the hash table, but I don't quite get this method:

/**
* getIndex --- use the hash function to obtain the array position of the key.
*
*@param  key  reference to object to be hashed
*@return      array index of element corresponding to key
*/
private int getIndex(Object key) {
return Math.abs(key.hashCode() % tableSize);
} // getIndex()

----------------------------------------------------------------------------------------------------------------
It compiles, but I don't see a hashCode() anywhere.  The hash function I want to use is:

hashKey = serialNumber % tableSize;

Why does it compile??

I wrote another method in my CarInventor.java that creates the hash function:

/**
* hashFunction --- the hash function
*
* @return int, hash function
* @param n int
*/
private int hashFunction(int serialNumber){
return serialNumber % size;
} // end hashFunction()

I guess basically I need help with my main method.  How do I add a Car object to the hash table?

-----------------------------------------------------------
Updated Codes:
-----------------------------------------------------------
1. http://www2.hawaii.edu/~flam/Car.java <------------------ constructor class
2. http://www2.hawaii.edu/~flam/CarAgency.java <---------- main method
3. http://www2.hawaii.edu/~flam/CarInventor.java <--------- don't know what to do with this one... should I delete it??
4. http://www2.hawaii.edu/~flam/HashTableLinear.java <--- the hash table
0

LVL 30

Expert Comment

ID: 10911231
>> It compiles, but I don't see a hashCode() anywhere

Because that method is defined in the Object class, from which every class inherits.
0

LVL 86

Assisted Solution

CEHJ earned 50 total points
ID: 10912308
>>return Math.abs(key.hashCode() % tableSize);

Less expensive would be

return (key.hashCode() & Integer.MAX_VALUE) % tableSize ;
0

Author Comment

ID: 10914479
CEHJ,

>Less expensive would be

As in, takes less memory??
0

Author Comment

ID: 10914508
So, to add a Car object to the hash table is this what I do in the main method?
------------------------------------------------------------------------------------------

private static final int TABLE_SIZE = 10; // size of the hash table

private static int count = 0; // number of cars added
private static int pos = 0; // position in hash table

public static void main(String[] arg) throws Exception {

Car[] car = new Car[TABLE_SIZE]; // creates array with 2 cars

// or should I create a new hash table instead
// HashTableLinear hashTable = new HashTableLinear(); // creates hash table with 11 positions
...
while((pos < TABLE_SIZE) && (car[pos]!=null)) { // do not exceed # of elements
pos++;
} // end while
if(pos < TABLE_SIZE) {
car[pos] = new Car(serialNumber, makeInput, year);
car[pos].setSerial(serialNumber);
System.out.println("\n__________________________________________\n");
System.out.println("The following was added:\n" + car[pos].toString());
System.out.println("__________________________________________\n\n\n\n\n\n");
count++;
} // end if
...
} // end main()
0

Author Comment

ID: 10914521
I need to hash the element to add.  The following is my put method.  Is this where I would write my hash function?  Or does my hash function go in the main method?
----------------------------------------------------------------------------------------------------------------------------------------------

/**
* put --- put a key/value pair into the table.  Hashes the key to get the array
*         position to start probing (by calling a private helper method).  If an
*         existing element with same key is found, then it's overwriten.  Else,
*         add element in next empty slot (either null or DELETED entry).
*
* @param  key  object reference to key
* @param  val  object reference to data
*/
public void put(Object key, Object value) {
int index = findEntry(key, true);
Entry entry = data[index];
if((entry == null)||(entry == DELETED)) {
data[index] = new Entry(key, value);
} // end if
else {
entry.value = value;
} // end else
} // end put()
0

Author Comment

ID: 10914799
mayankeagle,

>> It compiles, but I don't see a hashCode() anywhere
>
>Because that method is defined in the Object class, from which every class inherits.
--------------------------------------------------------------------------------------------------

Okay, I understand the inherits part... but is there a specific code that it inherits?
0

Author Comment

ID: 10914857
Comment from rama_krishna580
Date: 04/24/2004 04:43PM HST

see here..all you can get u r answer..
http://www.cs.rit.edu/~ats/java-2000-1/html/skript-23.html
--------------------------------------------------------------------------------------------------------------------------------------------

Thank you for your comment, but I understand how arrays work.  I just don't know how to use the hash function with an array.
____________________________________________________________________________________________________
Example:
____________________________________________________________________________________________________

1. What is the car you would like to add:
12345, Toyota, 2004  // (int serialNumber, String makeModel, int year)

2. Get serialNumber and put into hash function:
int hashKey = serialNumber % TABLE_SIZE;  // where TABLE_SIZE = 10
So, int hashKey = 1234;  // hmm... but my table only has 11 positions.  Does it keep hashing till hashKey = 1?

3. Insert the car object into array position found by hashKey.

4. What is the car you would like to delete:
12345

5. Search array position one-by-one until getSerial() = 12345.  If found, set position = null.  Spit error if not found.

6.  etc...

0

Author Comment

ID: 10914868
OMG!!  I'm sorry!  I did my hash calculations wrong!

12345 % 10 = 5  // not 1 like I said in my previous comment

0

Author Comment

ID: 10914918
Hmm... let's write a pseudocode!
------------------------------------------------------------------------------------------------------------------------------------------

int hashKey = serialNumber % TABLE_SIZE;
while(array[hashKey]!=null && hashKey < TABLE_SIZE+1) { // while not null, and within table range
hashKey++; // go to next position
} // end while
if(array[hashKey]==null) {
array[hashKey] = serialNumber;
} // end if
else {
System.out.println("There's no more room to add a new car.  Please remove a car.");
} // end else

public Car remove(int serialNumber) {
int hashKey = serialNumber % TABLE_SIZE;
while(array[hashKey]!=serialNumber && hashKey < TABLE_SIZE+1) { // while not serialNumber, & within table range
hashKey++; // go to next position
} // end while
if(array[hashKey]==serialNumber) {
array[hashKey] = null; // remove it: set hashKey position to null
return Car removed; // how should I return this??  <<<<<<<<
} // end if
else {
} // end else
return Car removed; // how should I return this??  <<<<<<<<
} // end remove
0

Author Comment

ID: 10915296
Updated Codes:
-----------------------------------------------------------
1. http://www2.hawaii.edu/~flam/Car.java <------------------ constructor class
2. http://www2.hawaii.edu/~flam/CarAgency.java <---------- main method
3. http://www2.hawaii.edu/~flam/CarInventor.java <--------- hash table
0

LVL 30

Expert Comment

ID: 10915403
>> Okay, I understand the inherits part... but is there a specific code that it inherits?

If it inherits the class, it means that it inherits all the methods that class has. So the hashCode () method is defined for it (and accessible, because it is not private in the super-class).
0

Author Comment

ID: 10915410
public static void main(String[] arg) throws Exception {
...
Car[] car = new Car[TABLE_SIZE]; // TABLE_SIZE = 10
CarInventor hash = new CarInventor();
...
int hashKey = 0;
while((hashKey < TABLE_SIZE) && (car[hashKey]!=null)) { // do not exceed # of elements
hashKey++;
} // end while
if(hashKey < TABLE_SIZE) {
int arrayPos = hash.insertKey(serialNumber);
System.out.println("\n__________________________________________\n");
System.out.println("The following was added:\n" + car[arrayPos].toString());
System.out.println("__________________________________________\n\n\n\n\n\n");
count++;
} // end if
...
} // end main()

************************************************

/**
* toString --- returns a printable version of the Person object.
*/
public String toString() {
String s = "\n" + " Serial no: " + this.serialNumber;
s = s + "\nMake/Model: " + this.makeModel;
s = s + "\n      Year: " + this.year + "\n";
return s;
} // end toString()

--------------------------------------------------------------------------------------------------------------------------------------------
When I run my program, I get this error:

at CarAgency.main(CarAgency.java:94)

Line 94 is:   System.out.println("The following was added:\n" + car[arrayPos].toString());

Is it because of the car[arrayPos]??  How can I fix this error?
0

Author Comment

ID: 10915413
Comment from mayankeagle
Date: 04/25/2004 06:44PM HST

>> Okay, I understand the inherits part... but is there a specific code that it inherits?

If it inherits the class, it means that it inherits all the methods that class has. So the hashCode () method is defined for it (and accessible, because it is not private in the super-class).
-------------------------------------------------------------------------------------------------------------------------------------------

Ah!  I get it now.  Thank you for explaining!
0

LVL 30

Expert Comment

ID: 10915414
>> array[hashKey] = null; // remove it: set hashKey position to null
>> return Car removed; // how should I return this??  <<<<<<<<

You should first hold the object in a temporary reference like:

Car temp = array[hashKey] ;
array[hashKey] = null ;
return temp ;

BTW, that becomes a waste, actually. Why do you have to follow this array approach?

>> return Car removed; // how should I return this??  <<<<<<<<

In the second return statement, when the car was not found, you should return null.
0

Author Comment

ID: 10915422
Actually, I don't think I'm going to use that code.  Please see my updated ones... they probably don't make sense either :)

Updated Codes:
-----------------------------------------------------------
1. http://www2.hawaii.edu/~flam/Car.java <------------------ constructor class
2. http://www2.hawaii.edu/~flam/CarAgency.java <---------- main method
3. http://www2.hawaii.edu/~flam/CarInventor.java <--------- hash table
0

LVL 30

Expert Comment

ID: 10915424
>> car[arrayPos].toString

Yes, then car[arrayPos] is null.
0

Author Comment

ID: 10915444
Comment from mayankeagle
Date: 04/25/2004 06:51PM HST

>> car[arrayPos].toString

Yes, then car[arrayPos] is null.
-------------------------------------------------------------

That's what I figured.  I don't think my code is actually adding a "car" to the hash table.  Is my assumption correct?
0

Author Comment

ID: 10915452
Sorry, forgot to put my insertKey() up.  Here it is:

/**
* insertKey --- inserts key in hash table if possible.
*
* @param int key the key to be inserted in the table
*/
public int insertKey(int key) {
boolean keyFound = false;  // indicate key already exists
boolean locationFound = false;  // indicate empty location found

// set probe to the location returned by the hash function

probe = hashFunction(key);

while(!locationFound) {
if (array[probe]==key) { // examine this location
keyFound = true;   // key already exists
System.out.println("There is already a car in this position.");
} // end if
else {
if (array[probe]==EMPTY) {
locationFound = true;  // found an empty location
} // end if
else {
// try next location in table, linear search, wrap if need be
probe = (probe + 1) % size;
count++;

if (count > size) { // tried all locations but no space in table
} // end if
} // end else
} // end else
} // end while

array[probe] = key; // everything A.OK!!  Insert!!
return probe; // returns the array position key was stored in
} // end insertKey()
0

LVL 30

Expert Comment

ID: 10915457
Your assumption is probably correct. I guess the arrayPos is either referring to the wrong position, or that the object is not being added at all. But if arrayPos was outside the limits of the array, it should throw an ArrayIndexOutOfBoundsException.
0

Author Comment

ID: 10915501
I think it's your second guess -- the object is not being added.  Here's my problem.

I have:

(1) Car[] car = new Car[TABLE_SIZE]; // creates array of cars
(2) CarInventor hash = new CarInventor();

My CarInventor creates the array to be used:

private static final int TABLE_SIZE = 10; // size of the hash table
private static final int EMPTY = -1; // constant representing empty spaces
private static int array[]; // array of integers

public CarInventor() {
size = TABLE_SIZE;
array = new int[size];

//initialize array to empty values
for (int i=0; i<size; i++) {
array[i] = EMPTY;
} // end for
} // end default constructor
-------------------------------------------------------------------------------
Looking at it now, I see that all positions are EMPTY.  But, my main method calls on car[arrayPos].toString()...
So, how do I add a car object to my array hash table?

I'm confusing myself @_@
0

LVL 30

Expert Comment

ID: 10915542
What is the purpose of the int array? And why should it be static?
0

Author Comment

ID: 10915570
I have a bunch of array[] such as:

array = new int[size];
array[probe]==key
etc...

If I take that out, my program will not compile :(
0

LVL 30

Expert Comment

ID: 10915579
You should not add useless things to your program just like that. Why will it not compile if you remove the int array from simply everywhere? Are you effectively using it anywhere or is it just a dummy? Don't remove it just like that - keep a backed-up copy of the current codes also, and try to remove the compilation errors - be sure to remove only those things which you don't need.
0

Author Comment

ID: 10915607
In my insertKey method, I use the array[probe]==key to see if the location in the array[probe] has the value of key:

public int insertKey(int key) {
boolean keyFound = false;  // indicate key already exists
boolean locationFound = false;  // indicate empty location found

// set probe to the location returned by the hash function

probe = hashFunction(key);

while(!locationFound) {
if (array[probe]==key) { // examine this location
keyFound = true;   // key already exists
System.out.println("There is already a car in this position.");
} // end if
else {
if (array[probe]==EMPTY) {
locationFound = true;  // found an empty location
} // end if
else {
// try next location in table, linear search, wrap if need be
probe = (probe + 1) % TABLE_SIZE;
count++;
if (count > TABLE_SIZE) { // tried all locations but no space in table
} // end if
} // end else
} // end else
} // end while

array[probe] = key; // everything A.OK!!  Insert!!
return probe; // returns the array position key was stored in
} // end insertKey()

***********************************
This is the hashFunction method:

private int hashFunction(int serialNumber){
return serialNumber % TABLE_SIZE;
} // end hashFunction()

----------------------------------------------------------------------------------------------------------------------------

I'm assuming that this counts as using it effectively.  Please let me know otherwise.

----------------------------------------------------------------------------------------------------------------------------
Back to my other question:

How do I add to the array?  Is it because of this method (shown above) that it is not adding?  Or is it because I'm not adding correctly from the main method?
0

Author Comment

ID: 10915610
Comment from mayankeagle
Date: 04/25/2004 07:26PM HST

...Don't remove it just like that - keep a backed-up copy of the current codes also, and try to remove the compilation errors - be sure to remove only those things which you don't need.
-------------------------------------------------------------------------------------------------------------------------------------

Very true.  Always keep a backup.  I learned it the hard way one time.  I cried.  T_T
0

LVL 30

Expert Comment

ID: 10915619
>>  Please let me know otherwise.

Yeah, that's ok. Will have to go through your updated codes once.
0

Author Comment

ID: 10915628
Thank you! =^^=
0

LVL 30

Expert Comment

ID: 10915855
Luna,

Are the codes at those links updated? The first thing that I saw in your Car.java file is that the members serialNumber, makeModel and year are static - THEY SHOULD NOT BE!! They are specific to each car, hence they should not be static.

Mayank.
0

Author Comment

ID: 10915909
Ooo!!  Sorry about that!  It's fixed now :)
0

LVL 30

Expert Comment

ID: 10915920
0

Author Comment

ID: 10915928
Updated Codes:
-----------------------------------------------------------
1. http://www2.hawaii.edu/~flam/Car.java <------------------ constructor class
2. http://www2.hawaii.edu/~flam/CarAgency.java <---------- main method
3. http://www2.hawaii.edu/~flam/CarInventor.java <--------- hash table

Sorry!! =^^=
0

LVL 30

Expert Comment

ID: 10916034
In the default constructor CarInventor (), int size = TABLE_SIZE hides the class-member size. You should use:

size = TABLE_SIZE ; // or this.size = TABLE_SIZE ; - to refer to the class-member

Also, count perhaps holds the number of cars so it should be static. Also make getNumberCars () as static, and call it everywhere as CarInventor.getNumberCars (). In every constructor that you have, you should increment the value of 'count' by 1.

More comments after I read through the rest of the code ;-)
0

LVL 30

Accepted Solution

Mayank S earned 400 total points
ID: 10916089
Since you have a private size member, you should change the name of the public method size () to something else. Maybe something like getSize ().

Also - it should return the value of size rather than TABLE_SIZE because 'size' specifies the maximum number of objects that you can have and it need not be equal to TABLE_SIZE (since you have a parameterized constructor for it).

Perhaps that way, wherever you have:

>> probe = (probe + 1) % TABLE_SIZE;
>> if(accesses > TABLE_SIZE) {
>> if (count > TABLE_SIZE) {

They'd better be:

probe = ( probe + 1 ) % size ;

if ( accesses > size ) {

if  ( count > size ) {
0

Author Comment

ID: 10916102
>count perhaps holds the number of cars so it should be static

Ah, I see what you mean.  I didn't notice that one.  ty!

--------------------------------------------------------------------------------------------------------------
>In every constructor that you have, you should increment the value of 'count' by 1.

How come I need to count++ in the constructor?  Shouldn't I only count++ after I add a car??
0

Author Comment

ID: 10916118
Comment from mayankeagle
Date: 04/25/2004 09:20PM HST
--------------------------------------------------------------------------------------------------

Okay, I updated my code.  The only TABLE_SIZE I left was the one in my hash function since that's what I want the hash function to be  :)

private int hashFunction(int serialNumber){
return serialNumber % TABLE_SIZE;
} // end hashFunction()

Should I wait till you're done looking at my code before I upload my updated version?
0

Author Comment

ID: 10916288
Gasp!!  I think I got the add thing to work!

Here's my updated code:
-------------------------------------------------------------------------------------------
1. http://www2.hawaii.edu/~flam/Car.java <------------------ constructor class
2. http://www2.hawaii.edu/~flam/CarAgency.java <---------- main method
3. http://www2.hawaii.edu/~flam/CarInventor.java <--------- hash table

0

Author Comment

ID: 10916411
Aww, man!  My code's not checking for duplicates.  I mean, it's not adding them to the array... but how do I check for dups?

Idea:

In the main method, need to see

System.out.println("There is already a car with this serial number.  Please try again.");
} // end if
else {
if(arrayIsFull) {
System.out.println("There is no room to add a new car.  Please remove a car.");
} // end if
else { // array still has room
} // end else
} // end else

Also, need to check

0

Author Comment

ID: 10916416
>Also, need to check

Please disregard that.  I forgot to erase when I posted.  :)
0

Author Comment

ID: 10916465
Okay, working on my viewCar method:

/**
* viewCar --- retrieves the car information without removing it from the hash table.
*             Used to check if a car is available.
*/
public int viewCar(int key) {
boolean keyFound = false;  // indicate key already exists
boolean locationFound = false;  // indicate empty location found

// set probe to the location returned by the hash function

probe = hashFunction(key);

while(!locationFound) {
if (array[probe]==key) { // examine this location
keyFound = true;   // key found
return probe;
} // end if
else {
// try next location in table, linear search, wrap if need be
probe = (probe + 1) % size;
count++;
if (count > size) { // tried all locations but did not find it
System.out.println("Could not find serial number: " + key);
return -1;
} // end if
} // end else
} // end while
return probe;
} // end viewCar()
0

Author Comment

ID: 10916466
k, going to take a quick shower.  Be back in a bit  =^^=
0

LVL 13

Expert Comment

ID: 10916549
>> but how do I check for dups?
0

LVL 30

Expert Comment

ID: 10916593
>> Shouldn't I only count++ after I add a car??

Yeah, if that's the logic, that is the way it should be done. Sounds fine. For a second I thought that you should do it in the constructor but I thought too fast. You many/ may not add cars. You should increment only after adding a car.
0

LVL 30

Expert Comment

ID: 10916611

It is be a long page. I didn't find it, BTW. Anyway, what I would do would be:

Write a method for: >> if(serialNumberToAdd == serialNumberInArray) {

- searching if a serial number is present in the array or not.

Also - these checks can all be done in the add () method itself rather than the main () method.
0

LVL 30

Expert Comment

ID: 10916615
>> It is be a long page

It is a long page ;-)
0

LVL 13

Expert Comment

ID: 10916649

<< Copy of my previous comment >>

Classic implementation of HashTable use an array of list.
Each list contains objects whose hashcode is the same and equals to the array index :

To add a car you can do :
And to remove it :
theCars[ hashKey(car) ].remove(car);
Testing if a car is in the hashtable :
theCars[ hashKey(car) ].contains(car);
For each list you can use java.util.Vector, or implement it yourself.

It's important to have a good hash function in order to avoid long lists. You can use the hashCode returned by all Objects instances:
int hashKey(Car car)
{
return car.hashCode() % theCars.length;
}

0

Author Comment

ID: 10916787
Comment from mayankeagle
Date: 04/25/2004 10:56PM HST
--------------------------------------------------------------------------

Should I write a separate method for the dup check, or should I include it in my add method?
0

Author Comment

ID: 10916849
Alright!  Got my duplicates figured out.  Now to work on the remove method...

btw, here are the updated codes:
--------------------------------------------------------------
1. http://www2.hawaii.edu/~flam/Car.java <----------------- constructor class
2. http://www2.hawaii.edu/~flam/CarAgency.java <--------- main method
3. http://www2.hawaii.edu/~flam/CarInventor.java <------ hash table
0

Author Comment

ID: 10916867
If I don't get it within 30 minutes, I'll be back tomorrow.  Need my beauty sleep :)
Till then, I'll be around.  =^^=
0

LVL 30

Expert Comment

ID: 10916962
>> Should I write a separate method for the dup check, or should I include it in my add method?

Writing a separate method makes it more re-usable. It can be accessed from anywhere, anytime you need it.
0

Author Comment

ID: 10916983
Yay!  I think I did it!  It took over 30 minutes, but I was in the groove!!
Can someone tell me if these are ok, or if there is something wrong??

Here are my updated codes:
--------------------------------------------------------------
1. http://www2.hawaii.edu/~flam/Car.java <----------------- constructor class
2. http://www2.hawaii.edu/~flam/CarAgency.java <--------- main method
3. http://www2.hawaii.edu/~flam/CarInventor.java <------ hash table
0

LVL 30

Expert Comment

ID: 10917008
>> Can someone tell me if these are ok, or if there is something wrong??

Well, if something is wrong, then you should know it ;-) is it running fine or not? I will download the codes, BTW, and see them.
0

Author Comment

ID: 10917009
Hmm... if this all works okay, I'll be crazy and try to make an applet.  Do I smell another question??  :)
0

Author Comment

ID: 10917020
Comment from mayankeagle
Date: 04/26/2004 12:20AM HST
-----------------------------------------------------------

Seems to be running fine.  Not throwing any ugly errors my way - which is a good thing :)  But then again, I'm tired and maybe didn't test everything.  Sorry for the trouble!!

-luna621 =^^=
0

LVL 30

Expert Comment

ID: 10917022
Maybe yes ;-)
0

LVL 30

Expert Comment

ID: 10917025
>> I'm tired and maybe didn't test everything

That's ok ;-) good night.
0

Author Comment

ID: 10917030
mayankeagle,

*yawn* me thinks it's time for beauty sleep.  I will be back tomorrow.  Thank you for everything!!!
Points to be awarded shortly :)
0

LVL 86

Expert Comment

ID: 10917038
>>
CEHJ,

>Less expensive would be

As in, takes less memory??
>>

You don't need the overhead of calling Math.abs, so it will be less expensive in terms of memory and also faster. It's not a major point of course - you'd probably not notice any difference unless you deliberately measured it
0

LVL 30

Expert Comment

ID: 10917050
>> Points to be awarded shortly

I like that fast attitude of yours, BTW. You're the most interactive and quick questioner I've seen. Keeps you on top of my questioners' list if you click on my profile and see it ;-)
0

Author Comment

ID: 10917056
:)  You're the best!!

Well, I'll probably be back tomorrow with a question regarding applets.  Thinking of title: Hash Table Applet
Or something to that extent.

Goodnight!

-luna621 =^^=

0

LVL 86

Expert Comment

ID: 10917059
:-)
0

LVL 30

Expert Comment

ID: 10917071
>> Hash Table Applet

Would wait for it to come tomorrow ;-)
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question