Home arrow static arrow Java Programming [Archive] - Need help: Own HashTable
Warning: Creating default object from empty value in /www/htdocs/w008deb8/wiki/components/com_staticxt/staticxt.php on line 51
Java Programming [Archive] - Need help: Own HashTable
5 Duke Stars available
This topic has 13 replies on 1 page.

Posts:3
Registered: 8/5/04
Need help: Own HashTable  
Aug 5, 2004 9:18 AM



 
I have two books and i have search on google but can't find the information i need.

It's a schoolproject (so why don't i just ask my teacher? -It's holiday...)

I just want some information so i can start...

I'm trying to do a car register with my own HashTable.
To start with i have these interfaces:

interface myHashTbl {   public void put(Hash v);   public Hash get(int key);}


interface Hash {   public int getTheKey();}


interface Cars {   public void setColor(String color);   public String getColor();   public void setMadeBy(String madeby);   public String getMadeBy();   public void setNr(int nr);   public int getNr();   public void setYear(int year);   public int getYear();}


Is it something like this or is it the other way around or am i on a fishingtrip?:

public class Register implements Cars,Hash{ 	        private MyHashTable[] ht;        private int size,used,year,nr,key;        private String color,madeby;                public Register(int size){              this.ht=new MyHashTable[size];              this.size=size;              this.used=0;        } 	        public void setColor(String color){this.color=color;}        public String getColor(){return color;}        public void setMadeBy(String madeby){this.madeby=madeby;}        public String getMadeBy(){return madeby;}        public void setNr(int nr){this.nr=nr;}        public int getNr(){return nr;}        public void setYear(int year){this.year=year;}        public int getYear(){return year;}        public int getTheKey(){return key;}   	         //----- MyHashTable ----         public class MyHashTable implements myHashTbl{                    //No idea what i'm doing here :)                    public void put(Hash v){// Do something}                    public Hash get(int key){//Return something}         }}
 

Posts:24,036
Registered: 2/3/03
Re: Need help: Own HashTable  
Aug 5, 2004 9:24 AM (reply 1 of 13)



 
Definite fishing trip.

You'll need a more basic understanding of Java before any explanations make sense. Otherwise, it's just going to be a case of someone writing code for you. There's no foul in not knowing this stuff - everyone must start somewhere. I highly recommend the following resources for beginner information:

http://java.sun.com/docs/books/tutorial/
http://java.sun.com/learning/new2java/index.html
http://javaalmanac.com
http://www.jguru.com
http://www.javaranch.com
Bruce Eckel's [url=http://mindview.net/Books/DownloadSites]Thinking in Java[/url]
Joshua Bloch's [url=http://www.amazon.co.uk/exec/obidos/Author=Bloch,%20Josh]Effective Java[/url]
Bert Bates and Kathy Sierra's [url=http://www.amazon.com/exec/obidos/tg/detail/-/0596004656?v=glance]Head First Java[/url]

Good luck!
 

Posts:274
Registered: 2/21/04
Re: Need help: Own HashTable  
Aug 5, 2004 9:31 AM (reply 2 of 13)



 
OK - I need an opinion. It's all related. You'll come to know when you email.

Just use your junk mail - I don't care what your real email is or who you are.

Privacy is the main concern here.
 

Posts:357
Registered: 8/5/04
Re: Need help: Own HashTable  
Aug 5, 2004 9:36 AM (reply 3 of 13)



 
**** this auto login!
 

Posts:24,036
Registered: 2/3/03
Re: Need help: Own HashTable  
Aug 5, 2004 9:38 AM (reply 4 of 13)



 
Yep. I figured.
 

Posts:24,036
Registered: 2/3/03
Re: Need help: Own HashTable  
Aug 5, 2004 9:42 AM (reply 5 of 13)



 
Too **** funny. Caught with your pants down.... LOL!
 

Posts:3
Registered: 8/5/04
Re: Need help: Own HashTable  
Aug 5, 2004 9:52 AM (reply 6 of 13)



 
Are the last posts some internal joke here?
Anyway thanks for the links yawmark!
I'll return when i'm back from my fishing trip ;-)
 

Posts:24,036
Registered: 2/3/03
Re: Need help: Own HashTable  
Aug 5, 2004 9:57 AM (reply 7 of 13)



 
Are the last posts some internal joke here?

RoboCop911 has quite a history around here of demanding help and abusing those who provide it. What you see here was a bumbling attempt at concealing hizzer identity in order to persuade me to start a private conversation for some mysterious (and wholly uninteresting) reason.

Anyway thanks for the links yawmark!

You're welcome.

I'll return when i'm back from my fishing trip ;-)

Good luck - when you go through the tutorials, make sure you actually DO them. It's how I got my start in Java, and a little research can go a long way. When you run into snags, come back and ask specific questions; e.g. something a little more tight than, "I have no idea how to do this"... :o)
 

Posts:37,103
Registered: 3/30/99
Re: Need help: Own HashTable  
Aug 5, 2004 9:58 AM (reply 8 of 13)



 
Are the last posts some internal joke here?

Sort of. Robocrap (a major annoyance on these forums of late) posted under the Analeater login in another thread asking yawmark for his email address. Yawmark refused in that thread, so he tried again here, not realizing that he was actually logged in as Robo instead of Anal.
 

Posts:5,965
Registered: 5/17/03
Re: Need help: Own HashTable  
Aug 5, 2004 10:16 AM (reply 9 of 13)



 
Why don't you do it step by step? Start by defining a Car class. This is what you want to store in the Register. How is a Car to be identified. By registration number, by owner, by color? Say registration number. This will be the key you use when you retreive a Car object from the Register, like
public class Car {   private int regNr;   public Car(int nr) { // constructor      regNr = nr;   }   public int getRegNr(nr) { // getter   }}//public class Register {   private final int CARS = 100; // max number of cars   private Car[] reg = new Car[CARS]; // holds cars   public void putCar(Car car) { // store Car   }   public Car getCar(int regNr) { retrieve Car with reg. nr   }   public Car remCar(int regNr) { remove Car with reg. nr   }}//Register r = Register();r.putCar(new Car(123));r.putCar(new Car(456));Car c = r.getCar(123);

With this minimal framework in place you can start figuring out how to turn reg into a hash table.

Hint: you define a hash function which transform the regNr into an index which fits into reg for example regNr % CARS. This number is then used to decide where to put the Car object with that regNr.

Questions: What to do if you get a collision(two different regNr's land at the same index?) How to remove objecs?
 

Posts:957
Registered: 3/31/04
Re: Need help: Own HashTable  
Aug 5, 2004 10:29 AM (reply 10 of 13)



 
if u are just keeping a list without the bells and whistles, u dont really need to extend a HashTable;

HasthTable register = new HashTable();register.add(car1);register.add(car2);register.add(car3);for(int cnt=0; cnt<register.size(); cnt++){  Car x = register.get(cnt);  System.out.println(x.getName());}


something like that. read the API because I cant remember if its get() or getElement() or whatnot.
 

Posts:24,036
Registered: 2/3/03
Re: Need help: Own HashTable  
Aug 5, 2004 11:15 AM (reply 11 of 13)



 
if u are just keeping a list without the bells and
whistles, u dont really need to extend a HashTable;

@talon747: <constructive-advice>it's generally a "Good Idea"™ - when possible - to compile and test your solution before posting</constructive-advice>

Also, I'm pretty sure the OP isn't trying to extend Hashtable (small 't'), but rather implement hizzer own version of a hash. If s/he were looking to use a hash with composition, it's also a "Good Idea"™ to direct them toward the newer HashMap rather than Hashtable.

HTH... :o)
 

Posts:3
Registered: 8/5/04
Re: Need help: Own HashTable  
Aug 5, 2004 2:01 PM (reply 12 of 13)



 
Thanks UlrikaJ, for trying to help me! (sorry yawmark for not giving up ;-)

Here is my basic beginning.
public class Register { //Register class			private int size,used; 	private Car[] arrCars;   		public Register(int size){arrCars = new Car[size];}//Set arraysize	public Register(){this(10);}//Size not specified then 10	public void setCar(int nr,int year,String color,String madeby) {		//index 0 just to try... 		arrCars[0]=new Car(nr,year,color,madeby);		used++; //To know when to rehash...	}   		public void getCar(int regNr) { 		Car car=null;		boolean flag=false;		for (int i=0;i<arrCars.length;i++){ 			if (arrCars[i]==null) break;			car = (Car)arrCars[i];			if (car.getNr()==regNr) flag=true;break;		}		if (flag)			System.out.print(car.toString()+"\n");		else			System.out.print("Not found!\n");	}	   	public Car remCar(int regNr) { 		Car removed=null;		for (int i=0;i<arrCars.length;i++){			if (arrCars[i]==null) break; 			removed = (Car)arrCars[i];			if (removed.getNr()==regNr){				arrCars[i]=null;				used--;				break;			}		}		return removed;	}		class Car { // Car class			private int nr,year;		private String color,madeby;				public Car(int nr,int year,String color,String madeby){			 this.nr=nr;			 this.year=year;			 this.color=color;			 this.madeby=madeby;		}				public void setColor(String color){this.color=color;}        		public String getColor(){return color;}        		public void setMadeBy(String madeby){this.madeby=madeby;}        		public String getMadeBy(){return madeby;}        		public void setNr(int nr){this.nr=nr;}        		public int getNr(){return nr;}        		public void setYear(int year){this.year=year;}        		public int getYear(){return year;}		public String toString(){			return madeby+", "+color+", "+year+", "+nr;		}	} // Car class: End} // Register class: End

Ok, here is my thoughts. I implement Cars and Hash in my Car class and MyHashTbl in my Register class. Correct so far?

If so, i should then delete remCar, setCar and getCar and then use the ones in the interface, put and get but it's here i'm way lost. get takes a int-key and returns an object that has Hash implemeted(?) and put takes a Hash object and returns a key?

I know i have to use modulo (carNumber % array.length) to get the indexnumber to put the object in and i also know that i can use linear probing (increase by 1) or quadratic probing if there is a collision.

And as yawmark said, I'm not looking for someone to do this for me i just looking for some explanation.

Thanks!
 

Posts:5,965
Registered: 5/17/03
Re: Need help: Own HashTable  
Aug 5, 2004 10:49 PM (reply 13 of 13)



 
Ok, here is my thoughts. I implement Cars and
Hash in my Car class and MyHashTbl in my
Register class. Correct so far?

I think the Car class should be declared as a separate class outside Register. It's the Car objects you store and retrieve from the register.

This is not totally obvious because Register can store Cars only. If you decide to keep Car inside Register then Car should be declared static. The effect is that Car logically belongs to Register but Car objects can be created and manipulated outside Register.

But for the sake of simplicity I suggest you move Car outside Register.

If so, i should then delete remCar, setCar and
getCar and then use the ones in the interface,
put and get but it's here i'm way lost.
get takes a int-key and returns an object that
has Hash implemeted(?) and put takes a Hash
object and returns a key?

I see no real use for interfaces in this design other than to fancy things up for its own sake -:)

Anyway you have used arrCars to store the Car objecs so far. The strategy has been to look for the first empty slot and then just put the object there.

The next step is to use arrCars as a hash table. You'll have to rewrite setCar, getCar and remCar for that. First define a hash function. It maps the key (regNr) to an index position in arrCars, like
private hashFunction(int regNr) {   return regNr % size;}

This function tells you where in arrCars to put a Car object with a specific regNr. So setCar and getCar becomes very simple, (I've used the methods as I defined them)
public void setCar(Car car) {   int index = hashFunction(car.getRegNr());   arrCars[index] = car;}public Car getCar(int regNr) {   int index = hashFunction(regNr));   return arrCars[index];}

That's it you now have a hash table implementation.

I know i have to use modulo (carNumber % array.length)
to get the indexnumber to put the object in and i also
know that i can use linear probing (increase by 1) or
quadratic probing if there is a collision.

When you get the above to work you'll have to deal with the hard part namely collisions and how to remove objects from the hash table.

When that works you can isolate the hash table specifc code in its own class Hash and move it outside Register. You can make it more general so it handles any Object and not just Cars, like
public class Hash {   int[] table;   public boolean put(int key, Object value) { // returns false if hash table full   }   public Object get(int key) {   }}

The program design technique I've skeched is called stepwise refinement. You start with a simple framework of the program. Then you start filling in details little by little and see to it that everything works all the time and you expand and abstract the design step by step. The idea is that you have a working program from start to finish.

Good luck.
 
This topic has 13 replies on 1 page.