webForumDet fria alternativet

Hashtabell

Java

5 svar · 546 visningar · startad av Navegador

Medlem sedan jan. 200179 inlägg
Frågan#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.

------------------
Anfäkta och anamma

Navegador

Medlem sedan apr. 20007 588 inlägg
#2

Class Hashable not found

Du har missat ett t...

------------------
skaparen av allt som är mjukt och luktar lavendel

Medlem sedan jan. 200179 inlägg
#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.

------------------
Anfäkta och anamma

Navegador

Medlem sedan juni 20008 205 inlägg
#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( );
}

------------------
These are the cries of the carrots, the cries of the carrots! You see, Reverend Maynard, tomorrow is harvest day and to them it is the holocaust.

Medlem sedan jan. 200179 inlägg
#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]

Medlem sedan apr. 20007 588 inlägg
#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.

------------------
skaparen av allt som är mjukt och luktar lavendel

259 ms totalt · 4 externa anrop · v20260731065814-full.1dc6f849
123 ms — deklarationer (db)
0 ms — hämta statistik (cache)
132 ms — hämta tråd, inlägg och bilagor (db)
124 ms — ändringar (db)