Tabelle di hash con indirizzamento aperto e scansione lineare

[hardok]

Ciao a tutti, avrei bisogno una mano nella risoluzione di questo esercizio, per nulla complicato ma che purtroppo non riesco a comprendere.

Si inseriscano i valori 15,25,34,20,12,36,44 in una tabella di hash di dimensione 9 usando l'indirizzamento aperto con una scansione lineare, ovvero la funzione di hash è definita come h(k,i) = (h'(k)+i) mod 9, dove h'(k)=k mod 9.

La teoria sulle tabelle di hash la conosco, cosi come l'indirizzamento aperto con la scansione lineare, però non so come creare un programma in java che faccia questo..

Potrebbe essere corretto un codice di questo tipo?
Oppure è meglio scrivere la tabella di hash su un file txt e poi farlo leggere dal programma?

import java.util.*;

public class hashTable {
public static void main(String[]arg) {
Hashtable ht = new Hashtable(9);

int[]a={15,25,34,20,12,36,44};
for(int i=0;i<a.length;i++) {
boolean b=false;
int k=a[i]%9;
Enumeration en = ht.keys();
while(ht.get(k)!=null) k++;
ht.put(k,a[i]);
}
Enumeration en = ht.keys();
while (en.hasMoreElements())
{ Object k = en.nextElement(); // chiave
Object v = ht.get(k); // valore
System.out.println(k+" "+v);
}
}
}

Grazie

[@DI3GO@]

Ponendo i presupposti che non conosco il lato teorico della cosa e se se fosse possibile ( anche brevemente ) per interesse personale tu la potessi spiegare ne sarei felice, Il salvataggio o meno su file non è specificato e quindi penso che la tabella di hash tu la possa gestire a tuo piacimento, anche come hai fatto nel codice sopra riportato ( e sopprattutto i tag code in modo da renderlo leggibile ).
Alla fine dei salvare il tuo hash creato con delle chiavi già presenti nella hash table. Giusto?

[Pastore12]

L'indirizzamento lineare non me lo ricoradavo proprio...

Questo mi ha rinfrescato le idee: http://www.dsi.unifi.it/~costa/lucid...entoAperto.pdf

Quindi, tu dovresti creare un vettore di 9 celle.
Quando vuoi inserire un elemento, la posizione di inserimento è data da h(k).
Ogni cella del vettore può contentere un solo elemento, quindi se la posizione h(k) = h(k,0) è già occupata si va alla posizione h(k,1). E avanti sino a trovare una posizione libera. In generale h(k,i).

Ora nasce un dubbio.. le HashMap prevedono solitamente coppie (chiave, valore). Nel caso specifico mi pare che chiave e valore siano la stessa cosa.

Detto questo, il tuo codice non mi pare affatto valido. Non ti conviene usare una HashMap perchè la funzione di hash devi creartela tu. Ti conviene creare un tuo oggetto MyHashMap che contenga il suo bel vettore di 9 elementi, e fornisca la funzione h(k,j).

Poi avrai un metodo main che istanzia MyHashMap e inseriche i valori.

Concordi? Ciao!

[hardok]

Ciao e grazie per la risposta.
Quello che ho postato è un'esercizio che abbiamo fatto in università e che potrebbe esser presente, in maniera simile, all'esame di Algoritmi.
Non trovando in rete dispense che mostrassero tutto il procedimento ho scritto il mio codice ma non ho riscontro se esso possa esser giusto o meno.

Il testo penso mi chieda di inserire i valori riportati in una tabella di hash per quello ho usato la classe hashtable e il comando put per inserire i valori.

Non ho capito bene la tua ultima domanda, cioè dici di tener le chiavi di default della hash table
senza riscriverle?

Ciao e grazie

[hardok]

Ciao,
Quindi tu dici di creare un vettore di 9 celle, ricavo posizione degli elementi con mod 9, (posizione = valore % 9) e se trova la cella occupata vado alla posizione h(k,1).
In questo caso non so se chiave e valore siano la stessa cosa, cioè in questo caso penso dovrei avere la chiave che indica la posizione (0-8) e come valore uno di quello proposti.
MyHashMap come funziona? come potrei implementare nello stesso il vettore creato? Perchè mi sembra una buona soluzione quella che hai proposto.
Tu scrivi che in HashMap dovrei crearmi io la funzione, quindi non è sufficiente una volta istanziato un oggetto HashMap inserirvi i valori con il metodo put ?

Ciao e grazie per l'attenzione

[Pastore12]

Non ho voglia di scartabellare tutta la documentazione della HashMap... però se anche ti riuscisse di usare un oggetto HashMap ci guadagneresti i metodi:
- put
- get
mentre dovresti comunque realizzare (o sovrascrivere)
- il metodo hash
- la struttura della HashMap

In particolare non credo che sia possibile vincolare la struttura della HashMap ad un vettore di 9 elementi.

D'altra parte, se costruisci una tua classe, totalemente indipendente da HashMap, devi fornire anche i metodi put e get, ma trattandosi di un vettore di 9 elemeni, diventa una faccenda abbastanza banale, credo.

MyHashMap come funziona? come potrei implementare nello stesso il vettore creato?

Inizialmente MyHashMap è il più desolato e vuoto degli oggetti. Nessun implements, nessun extends..

deve avere sicuramente un vettore di 9 celle come campo privato. Diciamo un bel

private int [] vettore;

magari nel costruttore della classe avrai

... MyHashTable (int capacity)
{
vettore = new int [capacity];
}

giusto per far le cose carine e dinamiche. oppure semplicemente

... MyHashTable ()
{
vettore = new int [9];
}

che tanto è questo che il testo richiede.

alla classe aggiungerai qualche metodo pubblico:
- int get (int key)
- void put (int key)
- remove (? dal testo dell'esercizio sembra non essere necessario)

e il metodo privato:
- hash (int k, int i)

Magari ci fai anche il main, così in un unico file hai tutto il necessario per testare se la cosa funziona.

public static void main (String [] arg)
{
MyHashTable ht = new MyHashtable();
ht.put(15);
ht.put(25);
...
}

e magari condisci il tutto con qualche System.out per vedere di volta in volta come viene riempito il vettore.

Per semplicità suppongo che chiave e valore siano uguali. se anche non fosse così non cambia molto, almeno ai fini didattici.

hash (k, i) implementa il calcolo dell'hash.

put riceve la chiave e il valore (il valore è la chiave stessa!), chiama hash (k, 0) per vedere dove inserire il valore. Se la posizione fornita da hash è libera, inserisce. Altrimeni chiama hash (k, 1). E così via. Quante volte può essere chiamata la hash per la stessa chiave? Se la funzione di hash è furba non dovrebbe fornire due volte la stesso risultato per la stessa chiave (al variare di i). Controlla, e se è così sai che puoi imporre un limite a i ed evitare che vada in loop.

get riceve la chiave, e fa un lavoro analogo a put. di volta in volta verifica che la chiave sia giusta nella posizione fornita da hash (k, i), altrimenti passa a hass (k, i+1).

Ora un'idea dovresti averla... ciao!

[hardok]

Ci provo! grazie mille