Shinobi
20-01-2004, 12:55
ciao a tutti ho iniziato il corso di Fondamenti 2 e ahimè ho delle dimenticanze... questa è una consegna che ci è stata data in laboratorio ...
Laboratorio 1 - strutture dati - Esercizio Hash (Separate Chaining )
La classe HashTable implementa la struttura dati Hash con cui è possibile rappresentare il tipo di dato Dizionario, in questo caso un insieme di coppie (key, element). La classe risolve le collisioni mediante il metodo del "Separate Chaining".
La struttura dati interna è costituita da un array di liste concatenate semplici.
La funzione di hash è costruita avvalendosi della funzione di libreria hashCode di String.
Realizzare in Java i metodi :
- costruttori della classe interna Node e della classe HashTable;
- find, per il ritrovamento dell'elemento associato ad un valore di chiave;
- insert, per l'inserimento di una coppia chiave e elemento associato;
- remove, per la rimozione dell'elemento associato ad un determinato valore di chiave.
Costruire inoltre un programma di prova per verificare il corretto funzionamento dei metodi
della classe HashTable.
Come ulteriore esercitazione:
aggiungere alla classe hashTable il metodo void printAll() per la stampa di tutte le coppie (key, element) presenti nella tabella;
aggiungere il metodo private void reHash() per raddoppiare automaticamente le dimensioni della tabella di hash quando il fattore di carico supera un certo valore critico.
Per avere il codice seguente scaricare il file LezioLabJava1.java.
class HashTable {
//Classe interna statica
static class Node {
Object key;
Object elem;
Node next;
Node(Object k, Object el, Node nx) { /* . . .*/ }
}
//Var di istanza
private int dim;
private int ne; //numero elementi
private Node tab[];
//Costruttori
public HashTable( int d ) { /* . . .*/ }
public HashTable( ) { this(20); }
//Ritorna l'informazione associata alla chiave
public Object find ( Object skey ) {
String str = skey.toString();
int hcode = str.hashCode();
int k = hcode % dim;
// . . . . . . . .
}
//Inserisce un Item nel Dizionario
public void insert (Object key, Object inf) {
// . . . . . . . .
}
//Rimuove l'elemento associato alla chiave.
public Object remove(Object skey) {
// . . . . . . . .
}
} //end class
ora: che diavolo di variabile istanza è private Node tab[]; ? un riferimento ad un array? se sì perchè è stato indicato così e non con Node[] tab ?
Laboratorio 1 - strutture dati - Esercizio Hash (Separate Chaining )
La classe HashTable implementa la struttura dati Hash con cui è possibile rappresentare il tipo di dato Dizionario, in questo caso un insieme di coppie (key, element). La classe risolve le collisioni mediante il metodo del "Separate Chaining".
La struttura dati interna è costituita da un array di liste concatenate semplici.
La funzione di hash è costruita avvalendosi della funzione di libreria hashCode di String.
Realizzare in Java i metodi :
- costruttori della classe interna Node e della classe HashTable;
- find, per il ritrovamento dell'elemento associato ad un valore di chiave;
- insert, per l'inserimento di una coppia chiave e elemento associato;
- remove, per la rimozione dell'elemento associato ad un determinato valore di chiave.
Costruire inoltre un programma di prova per verificare il corretto funzionamento dei metodi
della classe HashTable.
Come ulteriore esercitazione:
aggiungere alla classe hashTable il metodo void printAll() per la stampa di tutte le coppie (key, element) presenti nella tabella;
aggiungere il metodo private void reHash() per raddoppiare automaticamente le dimensioni della tabella di hash quando il fattore di carico supera un certo valore critico.
Per avere il codice seguente scaricare il file LezioLabJava1.java.
class HashTable {
//Classe interna statica
static class Node {
Object key;
Object elem;
Node next;
Node(Object k, Object el, Node nx) { /* . . .*/ }
}
//Var di istanza
private int dim;
private int ne; //numero elementi
private Node tab[];
//Costruttori
public HashTable( int d ) { /* . . .*/ }
public HashTable( ) { this(20); }
//Ritorna l'informazione associata alla chiave
public Object find ( Object skey ) {
String str = skey.toString();
int hcode = str.hashCode();
int k = hcode % dim;
// . . . . . . . .
}
//Inserisce un Item nel Dizionario
public void insert (Object key, Object inf) {
// . . . . . . . .
}
//Rimuove l'elemento associato alla chiave.
public Object remove(Object skey) {
// . . . . . . . .
}
} //end class
ora: che diavolo di variabile istanza è private Node tab[]; ? un riferimento ad un array? se sì perchè è stato indicato così e non con Node[] tab ?