Hashtabell

5 svar · 561 visningar · startad av Navegador 13 maj 2001

NavegadorMedlem sedan jan. 200179 inlägg

Trådstart13 maj 2001 20:48#1

Uppgift:

Implementera en klass Dictionary som stödjer operationerna insert och lookup. Följer några av raderna i Dictionary
-klassen. Ta för givet att du har en hashtabell-klass.

public class Dictionary {

// några av metoderna
void insert(Hashable key, Object definition);
Object lookup(Hashable key,) throws ItemNotFound;

}

Så här ser det ut i ett fungerande pgm:

public final class TestHashTable {
public static void main( String [ ] args ) {
HashTable h = new QuadraticProbingTable( );

    h.insert( new MyString( new String( "Becky" ) ) );
    
}

...

}

Jag vill istället:

public final class TestDictionary {

public static void main( String \[ \] args ) {

	Dictionary d = new Dictionary();
	
	// Nyckeln är "cykel"
	// String är object för "tvåhjuligt fordon"
    d.insert( new MyString( new String( "cykel" ) ), new String("Tvåhjuligt fordon") );
    
}

}

I Dictionary:

public class Dictionary {

private Object definition;

// Konstruktor
public Dictionary () {

	// Hash tabell konstrueras	
	HashTable h = new QuadraticProbingTable( );

}

void insert (Hashable key, Object definition) {

	this.definition = definition;	
	h.insert( key );
	        
}

}

Resultat:
/../TestDictionary.java:16: Class Hashable not found in void main(java.lang.String[]).
d.insert( new MyString( new String( "cykel" ) ), new String("Tvåhjuligt fordon") );
^
/../Dictionary.java:18: Class Hashable not found in type declaration.
void insert (Hashable key, Object definition) {
^
/../Dictionary.java:23: Undefined variable or class name: h
h.insert( key );
^
...

7 errors
Done

Undefined variable or class name: h
- varför då? Jag har ju skapat Hashtabellen i konstruktorn.

Allting importeras på liknande sätt som i det fungerande pgm:et.

sgtpepperMedlem sedan apr. 20007 588 inlägg

13 maj 2001 21:48#2

Class Hashable not found

Du har missat ett t...

NavegadorMedlem sedan jan. 200179 inlägg

13 maj 2001 22:00#3

Nej. Key måste vara Hashable.

/**
* Protocol for Hashable objects.
* @author Mark Allen Weiss
*/
public interface Hashable
{
/**
* Compute a hash function for this object.
* @param tableSize the hash table size.
* @return (deterministically) a number between
* 0 and tableSize-1, distributed equitably.
*/
int hash( int tableSize );
}

Vad är Hashtabeller bra för? Jo, man får ungefär linjär åtkomsttid oavsett storlek.

spangoMedlem sedan juni 20008 205 inlägg

14 maj 2001 08:41#4

<font size="1" face="Verdana, Arial, Helvetica, sans-serif">Kod:<font size="1" face="Verdana, Arial, Helvetica, sans-serif" color="#666600">public Dictionary () {
// Hash tabell konstrueras
HashTable h = new QuadraticProbingTable( );
}

Du måste lägga deklarationen av h utanför konstruktorn, annars är den lokal i den.
<font size="1" face="Verdana, Arial, Helvetica, sans-serif">Kod:<font size="1" face="Verdana, Arial, Helvetica, sans-serif" color="#666600">
private HashTable h;
public Dictionary () {
h = new QuadraticProbingTable( );
}

NavegadorMedlem sedan jan. 200179 inlägg

14 maj 2001 21:01#5

I main:

try {
result = (String) d.lookup( new MyString( "fel" ) );
System.out.println( "Found " + result );
}
catch ( ItemNotFound e ) {
System.out.println( "Cykel not found" );
}

I annan klass: Dictionary

Object lookup (Hashable key) throws ItemNotFound {

try {
	h.find (key);
	return this.definition;
}
catch( ItemNotFound e ) { 
	return null;
}

}

Resultat: "Found null" Inte riktigt vad jag tänkt mig. Vad är god programmeringsstil i
sådana här fall? Hur skickas felet vidare från catch i Dictionary uppåt i hierarkin?

[Redigerat av Navegador den 15 maj 2001]

sgtpepperMedlem sedan apr. 20007 588 inlägg

15 maj 2001 00:19#6

Varför deklarerar du att du slänger undantaget ItemNotFound när du i själva verket fångar det i metoden?

Om du inte fångar undantaget så kastas ju det till den anropande metoden där du kan ta hand om det, vilket du redan gör. Alltså: fimpa try-catch i lookup() så skall det funka.