Implementare un insieme con tabelle hash e iteratori

di
javadoc
il
25 risposte
J
javadoc
Pochi posts
Iscritto da
mag, 2014
Messaggi:
15

Implementare un insieme con tabelle hash e iteratori

Salve a tutti,
sono nuovo e non molto esperto del linguaggio Java.
Per l'università ho da completare un progetto dove mi viene richiesto di implementare un insieme di interi mediante una tabella hash e degli iteratori.
Il progetto possiede un'interfaccia (che estende l'interfaccia Iterable e Cloneable), una classe di test e una classe dove devo implementare i vari metodi (possiede già il metodo che calcola la funzione hash).
Il punto su cui vorrei chiedervi una mano è questo:
qual è il collegamento tra la tabella hash e l'insieme contenente gli interi che andrò ad inserire?
Non è sufficiente inserire gli elementi nella tabella hash e utilizzare quella come insieme?
Come posso utilizzare gli iteratori su un problema del genere?
Grazie a chiunque vorrà darmi una mano

25 Risposte

  • J
    javadoc
    Pochi posts
    Iscritto da
    mag, 2014
    Messaggi:
    15

    Re: Implementare un insieme con tabelle hash e iteratori

    Altro dettaglio che mi manda in crisi è che non posso utilizzare strutture delle API di Java..
  • andbin
    andbin
    Super Famoso
    Iscritto da
    ott, 2013
    Messaggi:
    6270

    Re: Implementare un insieme con tabelle hash e iteratori

    Il nocciolo di tutto è quindi la "tabella hash". Ti è abbastanza chiaro il concetto e la struttura di una tabella hash? Non esiste in assoluto un unico modo per implementarla, dipende innanzitutto se serve per realizzare una "mappa" (chiavi->valori) o più semplicemente per un "insieme" di valori. E poi anche dai tipi di dato da gestire.
  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    5902

    Re: Implementare un insieme con tabelle hash e iteratori

    andbin ha scritto:

    Il nocciolo di tutto è quindi la "tabella hash". Ti è abbastanza chiaro il concetto e la struttura di una tabella hash? Non esiste in assoluto un unico modo per implementarla, dipende innanzitutto se serve per realizzare una "mappa" (chiavi->valori) o più semplicemente per un "insieme" di valori. E poi anche dai tipi di dato da gestire.
    E' ovvio: deve implementare un insieme e i dati sono interi: lo dice pure.

    Ma riassumendo:

    1) come hai implementato la funzione hash per gli interi?

    2) visto che si parla di insieme, quali sono le proprieta' di un insime? Piu' specificatamente, che cosa dovrebbe succedere se viene inserito nell'insieme due volte lo stesso valore intero?

    3) supponi di dover inserire nell'insieme i numeri 0, 1, 9223372036854775807 E 9223372036854775807 (tranquillo, questo e' un numero perfettamente rappresentabile in Java). Che cosa ti aspetteresiti?

    4) supponi di dover inserire nell'insieme 1.000.000 di numeri compresi tra 0 e 9223372036854775807, generati casualmente, e che quindi non e' necessariamente assicurata la loro univocita', come faresti?

    Inizia con pensare ad un'implementazione ovvia.

    Supponendo che la tua implementazione sia quella classica, questa presenta un grave diffetto.

    Per ovviare a tale diffetto serve la tabella hash.

    Ma ti serve capire perche'!

    Poi, l'implementazione di una tabella hash non e' per nulla banale. Il problema non e' il tipo di dati, ma le proprieta' della funzione hash, ed un'altro importante concetto: la collisione delle chiavi
  • J
    javadoc
    Pochi posts
    Iscritto da
    mag, 2014
    Messaggi:
    15

    Re: Implementare un insieme con tabelle hash e iteratori

    Si, le tabelle hash le ho chiare come concetto. Io dovrei implementare un insieme di interi non negativi con la tabella hash. utilizzando la scansione lineare (quindi, tutte le chiavi vanno in tabella e in caso di collisione di una chiave si procede con la scansione della tabella fino a quando non trovo una locazione libera, giusto?) Io avevo intenzione di implementare il tutto tramite array ed accedere direttamente alle locazioni in memoria mediante il valore restituito dalla funzione hash... ma non sono sicuro se sia efficiente e soprattutto non so bene da dove partire.
  • J
    javadoc
    Pochi posts
    Iscritto da
    mag, 2014
    Messaggi:
    15

    Re: Implementare un insieme con tabelle hash e iteratori

    Prima di tutto, grazie per l'interesse nel volermi aiutare
    Dunque il progetto è già impostato dal professore, devo solo pensare a gestire la struttura dati in maniera efficiente e a implementare i metodi dell'interfaccia. La funzione hash c'è già e associa ad un intero una posizione in tabella. Se volete posso postare le specifiche del progetto
  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    5902

    Re: Implementare un insieme con tabelle hash e iteratori

    Per ora, lascia perdere i problemi di efficienza: sono problemi molto subdoli e non hanno un'unica soluzione.

    Inoltre ci sono due tipi di efficienza: quella temporale (tempo di esecuzione) e quella spaziale (memoria allocata).

    Vanno a stretto braccetto: se migliori una, peggiori l'altra.


    Hai descritto tutto quello che ti server per una prima implementazione: ora devi solo completare il codice!
  • J
    javadoc
    Pochi posts
    Iscritto da
    mag, 2014
    Messaggi:
    15

    Re: Implementare un insieme con tabelle hash e iteratori

    Questa è l'interfaccia 
    import java.util.Iterator;
package ins;
public interface Insieme extends Iterable, Cloneable{
/**
* Svuota l’insieme
*/
void clear();
/**
* Verifica che l’insieme sia vuoto.
* @return true se l’insieme è vuoto false altrimenti.
*/
boolean isEmpty();
/**
* @return
*/
int size();
/**
* @return
*/
int max();
il numero di oggetti presenti nell’insieme
il massimo intero presente nell’insieme, -1 se l’insieme è vuoto/**
* @param x l'intero da cui partire.
* @return
l’intero presente nell’insieme successivo a x, -1 se non esiste
*/
int nextTrue(int x);
/**
* Inserisce un int nell’insieme
* @param x l'intero da inserire.
* @return
true se l’intero non era gia’ presente, false altrimenti
* @exception IllegalArgumentException se x<0
*/
boolean put(int x);
/**
* Controlla se un intero è presente
* @return true se l’intero e’ presente, false altrimenti
*/
boolean contains(int x);
/**
* Rimuove un int nell’insieme.
* @param x l'intero da rimuovere.
* @return
true se l’intero era presente, false altrimenti
*/
boolean remove(int x);/**
* Conversione in String
* Restituisce una String con gli elementi dell’insieme in ordine crescente
* racchiusi tra parentesi quadre e separati da blank
* @return la stringa
*/
String toString();
/**
* Conversione in array
* Restituisce un array di int con gli elementi dell’insieme in ordine crescente
* @return l'array
*/
int [] toArray();
/**
* clone
* @return un clone dell’insieme
* @throws CloneNotSupportedException
*/
Object clone() throws CloneNotSupportedException;
/**
* Restituisce un iteratore per scandire gli elementi dell’insieme in ordine
* crescente, il metodo remove non è implementato
* @return l'iteratore
*/Iterator iterator();
/**
* Unione
* l’insieme viene modificato inserendo gli elementi che stanno in y
* @param y il secondo insieme
*/
void unione (Insieme y);
/**
* Intersezione
* l’insieme viene modificato togliendo gli elementi che non stanno in y
* @param y il secondo insieme
*/
void intersezione (Insieme y);
/**
* Differenza
* l’insieme viene modificato togliendo gli elementi che stanno in y
* @param y il secondo insieme
*/
void differenza(Insieme y);
}

    Questa è la classe che implementa l'interfaccia e allegato c'è il seguente commento:
    // fornisce una implementazione parziale di Insieme come array di interi
    // con dimensioni massime limitate solo dalla memoria disponibile 
    package ins;
import java.util.*;
public class InsiemeHash implements Insieme {
// funzione hash associa ad un int la posizione nella tabella
final private int address(int x, int l) {
int hash = (new Integer(x)).hashCode();
return (hash & 0x7FFFFFFF) % l;
}
. . .
da completare . . .
public void differenza(Insieme y) {
throw new UnsupportedOperationException();
}
public void intersezione(Insieme y) {
throw new UnsupportedOperationException();
}public int max() {
throw new UnsupportedOperationException();
}
public int nextTrue(int x) {
throw new UnsupportedOperationException();
}
public boolean remove(int x) {
throw new UnsupportedOperationException();
}
public Object clone() throws CloneNotSupportedException {
throw new UnsupportedOperationException();
}
    Dalle specifiche io credo che basti rappresentare il tutto con un array... ma non so se mi sbaglio
    Ho un pò le idee confuse..
  • J
    javadoc
    Pochi posts
    Iscritto da
    mag, 2014
    Messaggi:
    15

    Re: Implementare un insieme con tabelle hash e iteratori

    migliorabile ha scritto:

    Per ora, lascia perdere i problemi di efficienza: sono problemi molto subdoli e non hanno un'unica soluzione.

    Inoltre ci sono due tipi di efficienza: quella temporale (tempo di esecuzione) e quella spaziale (memoria allocata).

    Vanno a stretto braccetto: se migliori una, peggiori l'altra.


    Hai descritto tutto quello che ti server per una prima implementazione: ora devi solo completare il codice!
    Quindi mi consigli di implementare il tutto tramite array per iniziare?
  • andbin
    andbin
    Super Famoso
    Iscritto da
    ott, 2013
    Messaggi:
    6270

    Re: Implementare un insieme con tabelle hash e iteratori

    migliorabile ha scritto:

    E' ovvio: deve implementare un insieme e i dati sono interi: lo dice pure.
    Lo so .... l'ho letto cosa voleva. Ma visti i dubbi iniziali ho solo e semplicemente voluto fare una premessa un po' più generale sulle tabelle hash!

    Se ritieni che solo le tue risposte siano utili e non le mie o di altri .... sei liberissimo di continuare tu nella discussione.
  • J
    javadoc
    Pochi posts
    Iscritto da
    mag, 2014
    Messaggi:
    15

    Re: Implementare un insieme con tabelle hash e iteratori

    Avrei un'altra domanda da farvi, forse mi sto perdendo in un bicchier d'acqua..
    Ho scritto un pò di codice, dichiarando la variabile array che conterrà gli elementi dell'insieme e il costruttore InsiemeHash() che creerà un array con i valori inizializzati a -1 
    

private int[] array; // Array che contiene interi non negativi
private static int diminiziale = 10; // dimensione iniziale dell' insieme
private int elementi; // contatore del numero di elementi inseriti nell' insieme

/* Costruttore che inizializza un array di dimensioni prefissate e imposta il 
 * valore delle celle a -1, per indicare che la locazione è libera e può essere
 * utilizzata 
 * 
 */

public InsiemeHash() {
	array = new int[diminiziale];
	for (int i = 0; i < array.length; i++)
		array[i] = -1;

	elementi = 0;
}
    Sperando di non aver scritto stupidaggini, il problema che ho al momento è con il metodo 
    
/**
* Unione
* l’insieme viene modificato inserendo gli elementi che stanno in y
* @param y il secondo insieme
*/
void unione (Insieme y);
}
    La mia domanda è questa: Come faccio a sapere che cosa contiene la variabile y per unirla all'insieme che ho già creato?
    Il tipo di dato "Insieme" devo implementarlo oppure lo ho già implementato col costruttore InsiemeHash()?
    Grazie in anticipo...
  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    5902

    Re: Implementare un insieme con tabelle hash e iteratori

    Ti faccio io un po' di domande:

    1) che cosa e' e a cosa serve un iteratore?
    2) che cosa e' e a che cosa serve un'interfaccia?
    3) che relazione c'e' tra una classe ed un'interfaccia?
    4) quali di queste affermazioni ha senso:

    a) una classe implementa un'interfaccia
    b) un'interfaccia implementa una classe

    Altra cosa: usa i termini in modo corretto. y non e' una variabile, ma un parametro.


    Teoricamente dovresti avere tutte le risposte, ma il tuo ultimo post indica che c'e' qualcosa che non hai capito.
  • J
    javadoc
    Pochi posts
    Iscritto da
    mag, 2014
    Messaggi:
    15

    Re: Implementare un insieme con tabelle hash e iteratori

    Scusa hai ragione, ho sbagliato a scrivere nella furia
    Un iteratore è un oggetto grazie al quale posso "scorrere" (spero che non sia il termine errato) una struttura dati, senza aver bisogno di sapere quale sia la sua implementazione (ad esempio non ho bisogno di sapere quale sia la dimensione della struttura se devo utilizzare un ciclo for per una determinata operazione).
    Un'interfaccia è "simile" a una classe, ma contiene solo metodi astratti, c'è solo l'intestazione e non l'implementazione dei metodi che spetta alla classe che la implementerà. Non contengono costruttori, variabili statiche o metodi statici. Sono utili per realizzare dei tipi di dato astratti. Una classe che implementa un'interfaccia deve fornire la realizzazione di tutti i metodi dell'interfaccia. Quindi ha senso dire che una classe implementa un'interfaccia.

    Cosa non ho capito?
  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    5902

    Re: Implementare un insieme con tabelle hash e iteratori

    Dalle risposte, non c'e' nulla che non hai capito!

    Questi sono i concetti. Ora devi fare!
  • J
    javadoc
    Pochi posts
    Iscritto da
    mag, 2014
    Messaggi:
    15

    Re: Implementare un insieme con tabelle hash e iteratori

    No allora non ho capito.. Continuo però a non sapere cosa contiene il tipo di dato Insieme che si aspetta come parametro il metodo.. cioè non ho ancora capito quale sia la risposta alla domanda di prima..
Devi accedere o registrarti per scrivere nel forum
25 risposte