Solved

Hash Table

Posted on 2004-04-23
87
2,820 Views
Last Modified: 2008-01-09
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
Comment
Question by:luna621
  • 54
  • 21
  • 4
  • +3
87 Comments
 

Author Comment

by:luna621
Comment Utility
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

by:luna621
Comment Utility
Sorry, #3 should be:

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

Assisted Solution

by:seanrowen
seanrowen earned 50 total points
Comment Utility
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

by:luna621
Comment Utility
>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

by:luna621
Comment Utility
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

by:luna621
Comment Utility
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

by:luna621
Comment Utility
Okay, I'm confusing myself.  In my CarInventory.java, I have:

addCar(int serialNumber, String makeModel, int year) {
...
} // end addCar()


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++;
} // end addCar()
0
 

Author Comment

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

Author Comment

by:luna621
Comment Utility
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

by:luna621
Comment Utility
Okay, it's getting late.  I will continue working on this tomorrow.  See you then!!

-luna621 =^^=
0
 
LVL 23

Expert Comment

by:rama_krishna580
Comment Utility
try here u wull get help...

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

best of luck..

R.,K
0
 

Author Comment

by:luna621
Comment Utility
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

by:luna621
Comment Utility
rama_krishna580,

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

Expert Comment

by:CEHJ
Comment Utility
The easiest way is to look at the source for the API Hashtable ;-)
0
 
LVL 1

Expert Comment

by:seanrowen
Comment Utility
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

by:Webstorm
Comment Utility
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 :
        theCars[ hashKey(car) ].add(car);
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

by:luna621
Comment Utility
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

by:rama_krishna580
Comment Utility
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

by:luna621
Comment Utility
rama_krishna580,

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

-luna621 =^^=
0
 

Author Comment

by:luna621
Comment Utility
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

by:luna621
Comment Utility
Opps!  Forgot the link    =^^=

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

Author Comment

by:luna621
Comment Utility
   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

by:seanrowen
Comment Utility
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

by:luna621
Comment Utility
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

by:luna621
Comment Utility
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

by:luna621
Comment Utility
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

by:mayankeagle
Comment Utility
>> 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

by:CEHJ
CEHJ earned 50 total points
Comment Utility
>>return Math.abs(key.hashCode() % tableSize);

Less expensive would be

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

Author Comment

by:luna621
Comment Utility
CEHJ,

>Less expensive would be

As in, takes less memory??
0
 

Author Comment

by:luna621
Comment Utility
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 {
        InputStreamReader keyboard = new InputStreamReader(System.in);
        BufferedReader input = new BufferedReader(keyboard);

        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

by:luna621
Comment Utility
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

by:luna621
Comment Utility
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

by:luna621
Comment Utility
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

by:luna621
Comment Utility
OMG!!  I'm sorry!  I did my hash calculations wrong!  

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

Sorry about that!!  =^^=
0
 

Author Comment

by:luna621
Comment Utility
Hmm... let's write a pseudocode!
------------------------------------------------------------------------------------------------------------------------------------------

public void addCar(int serialNumber) {
    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
}  // end addCar


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 {
        System.out.println(serialNumber + " was not found.  Please try again.");
    } // end else
    return Car removed; // how should I return this??  <<<<<<<<
} // end remove
0
 

Author Comment

by:luna621
Comment Utility
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

by:mayankeagle
Comment Utility
>> 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

by:luna621
Comment Utility
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:

Exception in thread "main" java.lang.NullPointerException
        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

by:luna621
Comment Utility
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

by:mayankeagle
Comment Utility
>> 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

by:luna621
Comment Utility
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

by:mayankeagle
Comment Utility
>> car[arrayPos].toString

Yes, then car[arrayPos] is null.
0
 

Author Comment

by:luna621
Comment Utility
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
6 Surprising Benefits of Threat Intelligence

All sorts of threat intelligence is available on the web. Intelligence you can learn from, and use to anticipate and prepare for future attacks.

 

Author Comment

by:luna621
Comment Utility
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
                       System.out.println("The array is full.  Please remove items before adding.");
                   } // 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

by:mayankeagle
Comment Utility
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

by:luna621
Comment Utility
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

by:mayankeagle
Comment Utility
What is the purpose of the int array? And why should it be static?
0
 

Author Comment

by:luna621
Comment Utility
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

by:mayankeagle
Comment Utility
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

by:luna621
Comment Utility
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
                       System.out.println("The array is full.  Please remove items before adding.");
                   } // 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

by:luna621
Comment Utility
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

by:mayankeagle
Comment Utility
>>  Please let me know otherwise.

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

Author Comment

by:luna621
Comment Utility
Thank you! =^^=
0
 
LVL 30

Expert Comment

by:mayankeagle
Comment Utility
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

by:luna621
Comment Utility
Ooo!!  Sorry about that!  It's fixed now :)
0
 
LVL 30

Expert Comment

by:mayankeagle
Comment Utility
Where are your updated codes?
0
 

Author Comment

by:luna621
Comment Utility
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

by:mayankeagle
Comment Utility
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

by:
mayankeagle earned 400 total points
Comment Utility
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

by:luna621
Comment Utility
>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

by:luna621
Comment Utility
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

by:luna621
Comment Utility
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

by:luna621
Comment Utility
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

if(serialNumberToAdd == serialNumberInArray) {
    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
        add the car;
    } // end else
} // end else

Also, need to check

0
 

Author Comment

by:luna621
Comment Utility
>Also, need to check

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

Author Comment

by:luna621
Comment Utility
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.
 * @return     the car information found, -1 if car not found.
 */
    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);
                   System.out.println("Please try again.\n");
                   return -1;
               } // end if
            } // end else
        } // end while
        return probe;
    } // end viewCar()
0
 

Author Comment

by:luna621
Comment Utility
k, going to take a quick shower.  Be back in a bit  =^^=
0
 
LVL 13

Expert Comment

by:Webstorm
Comment Utility
>> but how do I check for dups?
Read my previous comment about duplicates.
0
 
LVL 30

Expert Comment

by:mayankeagle
Comment Utility
>> 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

by:mayankeagle
Comment Utility
>> Read my previous comment about duplicates.

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

by:mayankeagle
Comment Utility
>> It is be a long page

It is a long page ;-)
0
 
LVL 13

Expert Comment

by:Webstorm
Comment Utility


<< 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 :
        theCars[ hashKey(car) ].add(car);
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

by:luna621
Comment Utility
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

by:luna621
Comment Utility
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

by:luna621
Comment Utility
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

by:mayankeagle
Comment Utility
>> 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

by:luna621
Comment Utility
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

by:mayankeagle
Comment Utility
>> 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

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

Author Comment

by:luna621
Comment Utility
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

by:mayankeagle
Comment Utility
Maybe yes ;-)
0
 
LVL 30

Expert Comment

by:mayankeagle
Comment Utility
>> I'm tired and maybe didn't test everything

That's ok ;-) good night.
0
 

Author Comment

by:luna621
Comment Utility
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

by:CEHJ
Comment Utility
>>
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

by:mayankeagle
Comment Utility
>> 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

by:luna621
Comment Utility
:)  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

by:CEHJ
Comment Utility
:-)
0
 
LVL 30

Expert Comment

by:mayankeagle
Comment Utility
>> Hash Table Applet

Would wait for it to come tomorrow ;-)
0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Java contains several comparison operators (e.g., <, <=, >, >=, ==, !=) that allow you to compare primitive values. However, these operators cannot be used to compare the contents of objects. Interface Comparable is used to allow objects of a cl…
Introduction This article is the last of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers our test design approach and then goes through a simple test case example, how …
This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …

728 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now