Newsgroup: it.comp.java
Titolo: hash table

Ciao a tutti devo creare una hash table per cui il codice dovrebbe essere 
questo giusto?
/** A hash table with linear probing and the MAD hash function */
import java.util.*;
public class HashTableMap<K,V> implements Map<K,V>
{ public static class HashEntry<K,V> implements Entry<K,V>
  { protected K key;
    protected V value;
    public HashEntry(K k, V v) { key = k; value = v; }
    public V getValue() { return value; }
    public K getKey() { return key; }
    public V setValue(V val)
    { V oldValue = value;
      value = val;
      return oldValue;
    }
    public boolean equals(Object o)
    { HashEntry<K,V> ent;
      try { ent = (HashEntry<K,V>) o; }
      catch (ClassCastException ex) { return false; }
      return (ent.getKey() == key) && (ent.getValue() == value);
    }
  }
  protected Entry<K,V> AVAILABLE = new HashEntry<K,V>(null, null); // marker
  protected int n = 0;   // number of entries in the dictionary
  protected int capacity; // capacity of the bucket array
  protected Entry<K,V>[] bucket;// bucket array
  protected int scale, shift;   // the shift and scaling factors
   /** Creates a hash table with initial capacity 1023. */
  public HashTableMap() { this(1023); }
  /** Creates a hash table with the given capacity. */
  public HashTableMap(int cap)
  { capacity = cap;
    bucket = (Entry<K,V>[]) new Entry[capacity]; // safe cast
    java.util.Random rand = new java.util.Random();
    scale = rand.nextInt(capacity-1) + 1;
    shift = rand.nextInt(capacity);
  }
  /** Determines whether a key is valid. */
  protected void checkKey(K k)
  { if (k == null) throw new InvalidKeyException("Invalid key: null.");
  }
  /** Hash function applying MAD method to default hash code. */
  public int hashValue(K key)
  { return Math.abs(key.hashCode()*scale + shift) % capacity;
  }
    /** Returns the number of entries in the hash table. */
  public int size() { return n; }
  /** Returns whether or not the table is empty. */
  public boolean isEmpty() { return (n == 0); }
  /** Returns an iterable object containing all of the keys. */
  public Iterable<K> keys() {
    PositionList<K> keys = new NodePositionList<K>();
    for (int i=0; i<capacity; i++)
      if ((bucket[i] != null) && (bucket[i] != AVAILABLE))
 keys.addLast(bucket[i].getKey());
    return keys;
  }
  /** Helper search method - returns index of found key or -(a + 1),
   * where a is the index of the first empty or available slot found. */
  protected int findEntry(K key) throws InvalidKeyException
  { int avail = -1;
    checkKey(key);
    int i = hashValue(key);
    int j = i;
    do
    { Entry<K,V> e = bucket[i];
      if ( e == null)
      { if (avail < 0)
   avail = i; // key is not in table
 break;
      }
      if (key.equals(e.getKey())) // we have found our key
 return i; // key found
      if (e == AVAILABLE)     // bucket is deactivated
      {
 if (avail < 0)
   avail = i; // remember that this slot is available
      }
      i = (i + 1) % capacity; // keep looking
    } while (i != j);
    return -(avail + 1);  // first empty or available slot
  }
  /** Returns the value associated with a key. */
  public V get (K key) throws InvalidKeyException
  { int i = findEntry(key);  // helper method for finding a key
    if (i < 0) return null;  // there is no value for this key
    return bucket[i].getValue();     // return the found value in this case
  }
  /** Put a key-value pair in the map, replacing previous one if it exists. 
*/
  public V put (K key, V value) throws InvalidKeyException
  { int i = findEntry(key); //find the appropriate spot for this entry
    if (i >= 0) //  this key has a previous value
      return ((HashEntry<K,V>) bucket[i]).setValue(value); // set new value
    if (n >= capacity/2)
    { rehash(); // rehash to keep the load factor <= 0.5
      i = findEntry(key); //find again the appropriate spot for this entry
    }
    bucket[-i-1] = new HashEntry<K,V>(key, value); // convert to proper 
index
    n++;
    return null;  // there was no previous value
  }
  /** Doubles the size of the hash table and rehashes all the entries. */
  protected void rehash()
  { capacity = 2*capacity;
    Entry<K,V>[] old = bucket;
    bucket = (Entry<K,V>[]) new Entry[capacity]; // new bucket is twice as 
big
    java.util.Random rand = new java.util.Random();
    scale = rand.nextInt(capacity-1) + 1;     // new hash scaling factor
    shift = rand.nextInt(capacity);   // new hash shifting factor
    for (int i=0; i<old.length; i++)
    { Entry<K,V> e = old[i];
      if ((e != null) && (e != AVAILABLE))   // a valid entry
      { int j = - 1 - findEntry(e.getKey());
 bucket[j] = e;
      }
    }
  }
  /** Removes the key-value pair with a specified key. */
  public V remove (K key) throws InvalidKeyException
  { int i = findEntry(key);   // find this key first
    if (i < 0) return null;   // nothing to remove
    V toReturn = bucket[i].getValue();
    bucket[i] = AVAILABLE;   // mark this slot as deactivated
    n--;
    return toReturn;
  }
  /** Returns an iterable object containing all of the entries. */
  public Iterable<Entry<K,V>> entries()
  { PositionList<Entry<K,V>> entries = new NodePositionList<Entry<K,V>>();
    for (int i=0; i<capacity; i++)
      if ((bucket[i] != null) && (bucket[i] != AVAILABLE))
 entries.addLast(bucket[i]);
    return entries;
  }
  /** Returns an iterable object containing all of the values. */
  public Iterable<V> values()
  { PositionList<V> values = new NodePositionList<V>();
    for (int i=0; i<capacity; i++)
      if ((bucket[i] != null) && (bucket[i] != AVAILABLE))
 values.addLast(bucket[i].getValue());
    return values;
  }
}
Perchč se la vado a compilare com'č mi dava prima 27 errori mettendo import 
java.util.Iterator; mentre aumentando l'import a tutta la classe del 
java.util cioč java.util.*; mi da 14 errori.
Mi potreste dire se il codice di cui sopra č giusto o se manca per caso 
qualcosa, e il xkč di questi errori in compilazione?
Ringrazio anticipatamente tutti coloro che sapranno rispondermi.
Ciao 


http://csvtosql.sf.net
E' meglio baciare un avocado che sostenere un combattimento con un
oritteropo.

 ci hai preso per un compilatore ?
era una semplice richiesta, se non ti va di rispondere o non ne sei in grado 
puoi anche farne a meno....
Mal che vada chiederņ al prof. 

> ci hai preso per un compilatore ?
L> era una semplice richiesta, se non ti va di rispondere o non ne sei
L> in grado puoi anche farne a meno....  Mal che vada chiederò al
L> prof.
Ci sono richieste e richieste. Prendiamo la tua:
"Perchè se la vado a compilare com'è mi dava prima 27 errori mettendo import 
java.util.Iterator; mentre aumentando l'import a tutta la classe del 
java.util cioè java.util.*; mi da 14 errori.
Mi potreste dire se il codice di cui sopra è giusto o se manca per caso 
qualcosa, e il xkè di questi errori in compilazione?
Ringrazio anticipatamente tutti coloro che sapranno rispondermi."
Le  prime tre  righe  hanno una  sola  risposta: 
             TORNA A STUDIARE IL MECCANISMO DELLE IMPORT.
E'  una  cosa  sulla  quale  non  puoi trovarti  a  fare  domande  del
genere. Io non mi presenterei nemmeno  dal professore e se fossi io il
professore ti chiederei perché diamine studi Java.
Non prendere l'IT per moda, fai male a te ed al pianeta. Non è che è il
caso di cambiare corso di studi finché si è in tempo ?
E guarda che sono dannatamente serio.
-- 
 /\            ___
/___/\__|_|\_|__|___Gian Uberto Lauri_____________________
  //--\ | | \|  |   Integralista GNUslamico  
\/		    e allevatore di bug da competizione


Stò studiando ingegneria informatica, sono al 2° anno e fin'ora abbiamo 
fatto solo un corso di informatica, questo è il secondo!
Per cui stiamo imparando tutti, con le nostre più o meno difficoltà, ora io 
continuerò a fare ingegneria informatica, non vado a mode, anche perchè 
altrimenti avrei al massimo fatto solo informatica dove avrei preso voti ben 
più alti, e senza sforzarmi più di tanto!
Oppure una di quelle facoltà dove ormai vanno tutti perchè fanno i telefilm 
alla tv.
Mi sa tanto, che siccome sono una ragazza mi dite di mollare, tutto qua!
Per quanto riguarda il discorso delle import il prof ce le ha spiegate così 
x es con import java.io.exception importi solo la classe di quell'eccezzione 
se al posto di exception ci metti * importi tutto il pacchetto del 
java.io
Ora non me ne frega se per voi va bene o meno quello che mi ha spiegato il 
prof, se per voi è un incompetente, ma io devo fare quello che mi dice il 
prof!Se no vado a casa.
inoltre la mia domanda era se l'hash table era giusta. ma vedo che qui non 
c'è voglia nè chiedo più di rispondere.
(inoltre ricordo che quel codice è stato fatto da roberto tamassia, autore 
del libro data structures & algorithms in java)
Bene non perderò più tempo a scrivere messaggi qui, nè farò perdere tempo a 
voi  , visto che le risposte sono, non seguire la moda, cambia lavoro, vai a 
casa tua...o cmq l'antifona è questa.
Arrivederci. 

 
A me han dato rispote puntuali e competenti.
Magari basta fare le domande giuste.

> 
L> Stò studiando ingegneria informatica, sono al 2° anno e fin'ora abbiamo 
L> fatto solo un corso di informatica, questo è il secondo!
So benissimo che  cosa è, l'avevo riconosciuto al  volo.  Ho tenuto un
corso simile in passato.
Ti ripeto,  sei sicura che  vuoi entrare nel mondo  dell'informatica ?
Non è più un bel mondo.
Oltretutto usualmente un ingegnere dovrebbe avere la responsabilità di
progettare  (ma perché  credi che  ti voglia  scoraggiare dall'entrare
nella IT italiana ?)
L> Mi sa tanto, che siccome sono una ragazza mi
L> dite di mollare, tutto qua!
Per nulla. Mia  moglie è un ingenere (telecomunicazionista,  ma Unix è
nato in AT&T...). 
Il discorso "sei  sicuro di voler diventare un  informatico" è "gender
independent".
L>  Per  quanto riguarda il  discorso delle  import il  prof ce  le ha
L> spiegate  così x es  con import  java.io.exception importi  solo la
L> classe  di quell'eccezzione  se al  posto di  exception ci  metti *
L> importi tutto il pacchetto del 
java.io
I  prof spiegano,  alcuni benissimo,  altri meno  bene. C'è  una sigla
nell'informatica che ti conviene prendere come massima numero 1:
                 RTFM
(Read The F[a_scelta] Manual), a_scelta può essere ine o ucking.
Quello che dovevi trovare sul libro (e che dovresti avere nel bagaglio
dal primo  corso) è  A COSA servono  gli statement di  importazione (o
inclusione).
Nel momento  in cui si va  a comporre una poesia  bisogna sapere molto
bene la lingua che si usa.
E checché dica chi  vuole ricondurre l'informatica alla "progettazione
di bielle" (casomai è analoga alla progettazione di cupole), scrivere
un programma è molto più vicino a scrivere una poesia.
(E ci sono esempi di codice che ti fanno provare analoghe sensazioni
 estetiche).
Nel momento in cui arrivi a scrivere una cosa come una hash table non
puoi permetterti di avere in testa domande come quelle che hai fatto.
L> Inoltre la mia
L> domanda era se l'hash table era giusta.
Scusa, ma questo lo devi determinare tu coi test. La cosa migliore è
trovare un collega di studi e testarvi il codice a vicenda.
Il test del software è una brutta bestiaccia. E' una brutta bestiaccia
perché,  al   contrario  di  quello   che  capita  in   altre  branche
dell'ingegneria, non c'è un supporto teorico.
O meglio, c'è un supporto  teorico molto scoraggiante che dice che non
puoi determinare meccanicamente che  un algoritmo è corretto, e questo
come derivazione del fatto che non puoi determinare se una macchina di
Turing si ferma.
L'ingegnere  che progetta  una biella  ha dietro  meccanica razionale,
scienza delle costruzioni e  qeuella dei materiali e quant'altro, alla
fine ha dei calcoli sulla carta  che gli dicono "la tua biella reggerà
lo sforzo". L'informatico no.
I consigli che posso darti sono:
- Fai in modo  di poter ispezionare lo stato  della struttura dati, in
  modo da verificare che evolva come atteso.
- Verifica le condizioni estreme e stressale (hash table vuota e piena)
L> inoltre ricordo che quel codice è stato fatto da roberto tamassia,
L> autore del libro data structures & algorithms in java
Ma non  era tuo  (peraltro, possono esserci  errori di stompa  o omis-
sioni :) ) ?
Ti consiglierei anche di prenderti il Gosling come libro.
