ciao a tutti,
questa è la specifica del progetto:

Implementazione di insiemi
Il progetto riguarda la scrittura di una package ins che implementa gli insiemi di interi non
negativi mediante una tabella hash, scansione lineare, load factor massimo 0.75.

NOTE
• La struttura delle classi non può essere modificata.
• Le firme dei metodi non possono essere modificate.
• Gli iteratori possono usare strutture di appoggio.
• Gli iteratori devono lanciare in modo corretto ConcurrentModificationException e
NoSuchElementException; il metodo remove non deve venire implementato.
• Non si possono usare strutture delle API di Java
• La specifica “dimensioni massime limitate solo dalla memoria disponibile” significa
che il programma usa la memoria disponibile, come visto a lezione, senza limiti predefiniti.

QUESTA è L'INTERFACCIA :

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 il numero di oggetti presenti nell’insieme
*/
int size();
/**
* @return il massimo intero presente nell’insieme, -1 se l’insieme è vuoto
*/
int max();
/**
* @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 INVECE E' LA CLASSE CHE HO IMPLEMENTATO:

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;
}

private static int defaultdim = 2; // dimensione iniziale dell' insieme

private int[] tab; // Insieme di interi non negativi

private int nsize; // numero di elementi dell' insieme

public InsiemeHash() {
makeEmpty();

}

public void makeEmpty() {
tab = new int[defaultdim];
for (int i = 0; i < tab.length; i++)
tab[i] = -1;

nsize = 0;

}

private int[] resize(int[] a, int length) {
int[] nuovo = new int[length];

for (int i = 0; i < nuovo.length; i++)
nuovo[i] = -1;
int h = 0;
clear();
for (int i = 0; i < a.length; i++) {
if (a[i] > -1) {
h = address(a[i], nuovo.length);
while (nuovo[h] > -1) {

h++;
if (h >= nuovo.length)
h = 0;
}

nuovo[h] = a[i];
nsize++;
}
}
return nuovo;
}

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();
}

public void clear() {
nsize = 0;

}

public boolean contains(int x) {
if (isEmpty())
return false;
boolean found = false;

int h = address(x, tab.length);

while (tab[h] > -1 && !found) {

if (tab[h] == x)
found = true;
else {
h++;
if (h >= tab.length)
h = 0;
}
}

return found;
}

public boolean isEmpty() {
return nsize == 0;
}

public Iterator iterator() {
// TODO Auto-generated method stub
return null;
}

public boolean put(int x) {
if (x < 0)
throw new IllegalArgumentException();

if (contains(x))
return false;
if (nsize >= tab.length / 2)
tab = resize(tab, tab.length * 2);
int h = address(x, tab.length);
while (tab[h] > -1) {

h++;
if (h >= tab.length)
h = 0;
}

tab[h] = x;
nsize++;
return true;
}

public int size() {
return nsize;
}

public int[] toArray() {

int[] r = new int[tab.length];

for (int i = 0; i < r.length; i++) {

r[i] = tab[i];

}
Arrays.sort(r);

return r;
}

public void unione(Insieme y) {

int[] arr = y.toArray();

for (int i = 0; i < arr.length; i++) {
if (arr[i] > -1)
put(arr[i]);
}
}

public String toString() {

int[] arr = toArray();

String out = "[";

if (nsize == 0)
out += "]";
else {

for (int i = arr.length - nsize; i < arr.length; i++) {

if (arr[i] > -1 && i == arr.length - 1)
out += arr[i] + "]";
else if (arr[i] > -1)
out += arr[i] + " ";

}
}
return out;

}
}


Prima di tutto vorrei sapere se questa implementazione può andare bene. Il programma di test è questo:

PROGRAMMA DI PROVA:

import ins.*;
import java.util.HashSet;
import java.util.Random;

public class ProvaHash {
static Random R = new Random();

public static void main(String[] args) {
Insieme s1 = new InsiemeHash();
System.out.println(s1.toString() + " s1 deve essere []");
s1.put(3);
System.out.println(s1 + " s1 deve essere [3]");
s1.put(3);
s1.put(4);
s1.put(1);
s1.put(2);
System.out.println(s1 + " s1 deve essere [1 2 3 4] ");
Insieme s2 = new InsiemeHash();
s2.put(3);
s2.put(4);
s2.put(1);
s2.put(6);
System.out.println(s2 + " s2 deve essere [1 3 4 6] ");
s1.unione(s2);
System.out.println(s1 + " s1a deve essere [1 2 3 4 6] ");
System.out.println("\n------------------------------------------");
System.out.println("\n test esteso, max Memory = " + maxMemory()
+ " M ");
int n = 50000;
for (int i = 0; i < 4; i++) {
s1 = new InsiemeHash();
System.out.println("\n n = " + n);
initTime();
for (int j = 0; j < n; j++)
s1.put(17 * j);
System.out.println(" inserzioni " + askTime() + " sec.");
initTime();
for (int j = 0; j < n; j++)
s1.contains(R.nextInt(1000000));
System.out.println(" ricerche " + askTime() + " sec." + " memoria "
+ askMemory() + " M");
s1.contains(0);
System.out.println("\n Prova UNIONE ");
s1 = new InsiemeHash();
s2 = new InsiemeHash();
initTime();
for (int j = 0; j < n; j++) {
s1.put(2 * j + 1);
s2.put(2 * j);
}
System.out.println(" inserzioni " + askTime() + " sec., memoria "
+ askMemory() + " M");
initTime();
s1.unione(s2);
System.out.println(" unione " + askTime() + " sec., " + s1.size()
+ " deve essere " + 2 * n + " memoria " + askMemory()
+ " M");
s1.contains(0);
if (n < 50000000) {
System.out.println("\n test di riferimento di HashSet ");
HashSet<Integer> h1 = new HashSet<Integer>();
HashSet<Integer> h2 = new HashSet<Integer>();
initTime();
for (int j = 0; j < n; j++) {
h1.add(2 * j + 1);
h2.add(2 * j);
}
System.out.println(" inserzioni " + askTime()
+ " sec., memoria " + askMemory() + " M");
initTime();
h1.addAll(h2);
System.out.println(" unione " + askTime() + " sec., "
+ h1.size() + " deve essere " + 2 * n + " memoria "
+ askMemory() + " M");
h1.contains(0);
}
n *= 10;
}
System.out.println("\n------------------------------------------");
}

private static double time0;

private static Runtime Ru = Runtime.getRuntime();

public static void initTime() {
time0 = System.currentTimeMillis();
}

public static double askTime() {
return (System.currentTimeMillis() - time0) / 1000.;
}

public static int askMemory() {
Ru.gc();
return (int) ((Ru.totalMemory() - Ru.freeMemory()) / 1024. / 1024.);
}

public static int maxMemory() {
Ru.gc();
return (int) (Ru.maxMemory() / 1024. / 1024.);
}
}


Il programma di prova effettua in pratica 4 volte lo stesso test sempre con numeri più grandi.
Il mio problema è che all' ultimo test con n = 50000000 invece di metterci 4-5 sec. ad esempio me ce ne mette 1000 e più. Volevo sapere cosè che sbaglio nell'implementazione.

2° : E' giusto inizializzare l'array nel costruttore riempiendolo di -1 (casella vuota) ??...altrimenti non sapevo come far valere lo 0 con elemento.


grazie delle risposte